Exam 2 topics

This is intended to give you a sense of what I think is important from the course so far, and what I will be thinking of when creating the exam.

I hate disclaimers, but here are some anyway. This is not a contract. I may have inadvertently left something off this list that ends up in an exam question. I make no guarantees that the exam will be 100% limited to items listed below. Moreover, I will not be able to test all of this material given the time limitations of the exam. I will have to pick and choose some subset of it.

You are permitted one 8.5 x 11 sheet of paper with notes (both sides) for use as a reference during the exam.

Students should be able to…

• Define deadlocks, detect them in code, interpret or create a schedule demonstrating if a deadlock can occur in a particular program. Rewrite code to avoid deadlocks. (Reading: Grossman's "Sophomoric Introduction")
• Define and interpret reentrant locks, reader/writer locks and condition variables (wait/notify). Be able to predict the output, or be able to write, pseudocode that uses them. (Reading: Grossman's "Sophomoric Introduction")
• Explain and justify the value of software transactional memory. Answer specific questions about how STM is being implemented in our assignment, and why. (Reading: Wikipedia article linked on Moodle page)
• Look at pseudocode or Java code of the style presented in the style of the locking algorithms we've looked at (the two warmups to Peterson's algorithm, Peterson's algorithm itself, the Filter algorithm, and the Bakery algorithm), and be able to assess whether critical sections satisfy mutual exclusion, deadlock freedom, and starvation freedom. Some of the proofs that we did in class might be a bit complex to work out for an exam question, but simpler arguments of its type would be reasonable. Being able to work with \(read_A \rightarrow write_B\) notation is reasonable. (Reading: see Chapter 2 of The Art of Multiprocessor Programming)
• Describe and evaluate variations for these parallel linked list approaches: (Reading: see Chapter 9 of The Art of Multiprocessor Programming)
  • Coarse-grained synchronization
  • Fine-grained synchronization (hand-over-hand)
  • Optimistic synchronization
  • Lazy synchronization
  • non-blocking synchronization
• Be able to interpret and predict output of Java stream examples similar to the style that we've done in class. (Reading: Java Streams tutorial from Oracle linked on Moodle page)