This is not the current version of the class.

Synchronization Supplement 1: Organizing time


In this supplemental lecture, we discuss how synchronization relates to organizing time.

Full notes on synchronization

Programming organizes state

Complete isolation is useless, overisolation is inefficient

Multithreaded programming must organize time

Thanksgiving example

Stalk of Brussels sprouts

Separated Brussels sprout leaves

Our procedures

Me Marilyn
  1. Cut bottom from sprout
  2. Separate sprout into leaves
  3. Put leaves in bowl
  4. If bowl is full, put it somewhere and get clean bowl
  5. Goto 1
  1. Find unattended container
  2. Check if it contains garbage
  3. If so, throw out garbage, clean container
  4. Goto 1

Conflict 1: Data race

Conflict 2: Invariant-violating conflicts

Horrifying real-world example of invariant-violating conflict


Mutual exclusion and locks

Mutual exclusion synchronization objects

Lock interface



Compare-exchange (compare-and-swap)