Recitation 20: Concurrency, locks, and monitors
(Outline)

1. Concurrent programs
   1. Needed for multi-processors, multi-cores, communication with human users, communication with slow devices, distributed systems, etc. Underlying issue: Performance
2. Initial Warning: Emphasize correctness over performance. It's easier to make a correct program efficient than an efficient program correct.
3. Kinds of concurrency:
   1. Shared memory: Concurrent components communicate by reading and writing memory locations
   2. Message passing: ...by sending and receiving messages
   3. Some people claim that message passing is easier to reason about (and thus write correct programs), whereas shared memory is more efficient
4. Threads
   1. A thread is [imperatively] a sequential flow of control, or [functionally] a single expression to be evaluated
   2. Multithreading: more than one flow of control, or more than one expression evaluated simultaneously
   3. Threads share a single address space
   4. Threads are lightweight: Creation, maintenance, destruction is (or should be) cheap
   5. Basic design for modern threads comes from language Modula-2+, circa mid-1980s.
   6. Creation: fork
   7. Destruction: reach end of control flow, or evaluation. Sometimes libraries provide ways to aggressively terminate threads, but this is dangerous.
   8. Example: Race condition on bank account balance
   9. Real world race conditions: THERAC-25, Mars Rover, NE blackout '03
5. Synchronization
   1. Three techniques: Mutexes, condition variables, monitors
   2. Mutexes
      1. Acquire, release, lock
      2. Rules
         1. All shared mutable data MUST be associated with some mutex (1 mutex -> 1 or more shared data)
         2. That association MUST be documented
         3. Shared mutable data MUST NOT be accessed unless its associated mutex is locked
         4. Any invariant (e.g., RI) of the shared data MUST be true whenever the mutex is unlocked
      3. Deadlock example. One solution: impose order on mutex acquisition
   3. Condition variables
      1. Wait, signal, broadcast
      2. Producer/consumer buffer example
      3. Not covered in recitation:
         1. Hoare vs Mesa semantics
         2. Naming convention: why you wait vs why you wake up
         3. How many? As many as reasons you might wait. Or, Java and C#: only 1
         4. Documenting: Mutex protected by, assertion for when it should be awakened
         5. Since wait releases mutex, must ensure invariants hold before waiting
   4. Monitors
      1. Shared data + 1 mutex + 1 or more condition variables
      2. Often a language construct, sometimes a pattern
      3. Java and C#: monitors with 1 implicit mutex and condition variable
6. Final Warning: Emphasize correctness over performance. It's easier to make a correct program efficient than an efficient program correct.