6.824 2001 Lecture 4: Coordination

Would Example 1 work in the simple threading package?
  Yes -- no pre-emption, only one CPU.

What could go wrong in a more involved environment?
  The problem: lines E and F must execute atomically.
  Interrupt or signal.
  Pre-emption (explain: timer interrupt, thread switch).
  Multiple CPUs.
  The program might want to yield during an atomic section.
    E.G. for memory allocation.

How can we provide atomic sequences?
  Does Example 2 work?
    We want TestAndSet to return 0 if not locked, 1 if already locked.
    But race between ret = *p and *p = 1.
    Two threads could simultaneously read the old value of 0.
    Or could be a context switch after ret = *p.
    No good against interrupts, pre-emption, multiple CPUs.
  Turn off interrupts.
    Side effect is to prevent pre-emption via timer interrupts.
    Not good in user mode, or multi-processor.
  Kernel emulation:
    System call to turn of interrupts around test-and-set.
    What does it do on a multi-processor?
  test-and-set-locked
    Works with interrupts, pre-emption, multi-CPU.

Test-and-set-locked instruction:
  TSL mem, R:
    R <- [mem]  /* load value at address mem */
    [mem] <- 1  /* set value at mem to 1 */
  Hardware locks the memory system around the two sub-operations.
  [Picture of CPUs, bus, arbitrator, memory system]
  Operates at motherboard clock rates, not CPU.
  Much slower than cached load/store.
  Prevents other uses of the bus.
  We can wrap an interface around TSL as in Example 3.

Example 3 works badly on a uniprocessor or with long critical sections.
  So put a thread_yield() in the acquire() while loop.

Table of techniques:
  Technique  Time      Uni?  Multi?
  mask intrs ?         yes   no
  Kern Emul  v. slow   yes   no (?)
  TSL        fast      yes   yes

Are locks enough?
  No: producer/consumer requires some kind of sleep / wakeup.
  Don't want to busy wait.
  Look at Example 4.

What's wrong with Example 4?
  Need to keep data structures consistent.
  Need to avoid race between
    while(full == 0) sleep();
    and
    full = 1; wakeup();
  Want each pair to execute atomically; how about:
    lock(l);
    while(full == 0) sleep();
    unlock(l);
  Can't hold the lock while sleep()ing!
  We want sleep() to hold the lock long enough to mark us as sleeping,
    then release the lock to the other process.
  So sleep/wakeup is not orthogonal to locking.
  Can we come up with a good abstraction?

Look at Example 5 and its use in Example 6.

Condition variable rules:
  You must be holding the lock when you call wait().
    Otherwise while(full == 0) wait(c, l); has a race.
  You must be holding the lock when you call signal().
    Otherwise while(full == 0) signal(c); has a race.
  wait() returns with the lock held.
    Since it's always used in that way.