Outline
  
  -  Recap
  
-  Better primitives.
    
  
-  Higher-level managers.
    
    -  Stones, bowls and semaphores.
    
-  Operating systems assist.
    
 
-  Still higher-level managers.
    
    -  ADTs, classes, and monitors.
    
 
Where are We?
  
  -  Tame uncoordinated, concurrent, shared access.
  
-  Solve through concurrency, move to coordination.
  
-  Concurrency tamed by mutual exclusion in critical sections.
    
    -  Via user-land code or interrupt disabling.
    
 
What’s Wrong?
  
  -  Peterson’s algorithm.
    
    -  A spin lock.
    
-  Disconnected from the OS.
      
      -  Unwise scheduling decisions on both sides. 
      
 
 
-  Disabling interrupts.
    
    -  Touchy and inflexible. 
    
-  Monstrously difficult errors to find and fix.
    
 
-  Better mutual exclusion primitives. 
  
What’s Next?
  
Stones and Bowls
  
  -  Some rules for critical section cs:
    
    -  There’s a bowl at enter cs.
    
-  A thread in cs must hold the stone.
    
-  The thread at exit cs puts the stone in the bowl.
    
-  A thread at enter cs wanting into cs must take the stone from
    the bowl first.
    
 
-  These rules provide mutual exclusion, progress, and starvation.  And
    independence.  
  
Modern Stones and Bowls
  
  -  The modern version of the stone in a bowl is the
  test-and-setinstruction.
    -  The bowl is a boolean variable b. 
    
-  If b = true, the bowl holds the stone.
    
-  If b = false, the bowl is empty.
    
 
-  test-and-setis a non-interruptable, non-privileged instruction in
  modern architectures.
    -  SPARC v9 ldstubinstruction.
 
test-and-set
  
  -  The effect of test-and-setis
bool test-and-set(bool * bowl)
   
    | bool b = *bowl |  | *bowl = false |  | return b |  
 
 
     
    -  Set a variable to false and return the variable’s previous value. 
    
 
-  If the stone’s in the bowl, test-and-setreturns true and the bowl
  is empty.
    -  Otherwise test-and-setreturns false.
 
Test-and-Set Critical Sections
  
  -  A test-and-setcritical section:
bool bowl-csi = true
enter csi
  while !test-and-set(bowl-csi) { }
exit csi
  bowl-csi = true
 
   
-  bowlis usually calledlock.
Binary Semaphores
  
Binary Semaphore Example
widget q[N]
q-size = 0
head = tail = 0
BinarySemaphore bowl(true)
| p()
  loop
    w = f()
    while q-size ≡ N {}
    q[tail++] = w
    bowl.take()
      ++q-size
    bowl.put()
 
 | c()
  loop
    while q-size ≡ 0 {}
    w = q[head++]
    bowl.take()
      --q-size
    bowl.put()
    g(w)
 
   | 
Tucking in the Loose Bits
  
  -  The binary semaphore solution has a lot of machinery hanging out.
| p()
  loop
    w = f()
    while q-size ≡ N {}
    q[tail++] = w
    bowl.take()
      ++q-size
    bowl.put()
 
   |  
 
 
-  How can the details be neatened up?
  
Hummmm...
  
Counting Semaphores
  | class CountingSemaphore
  private unsigned bowl
  private BinarySemaphore mutex(true)
  CountingSemaphore(unsigned c) 
    bowl = c
 | 
|   void put()
    mutex.take()
      ++bowl
    mutex.put()
  unsigned count()
    return bowl
 |   void take()
    bool done = false
    while !done
      mutex.take()
        if bowl > 0
          --bowl
	  done = true
      mutex.put()
 | 
Counting Semaphore Example
widget q[N]
head = tail = 0
CountingSemaphore bowl(0)
| p()
loop
  while bowl.count() ≡ N {}
  q[tail] = f()
  bowl.put();
  tail = (tail + 1) mod N
 | c()
loop
  bowl.take()
  w = q[head]
  head = (head + 1) mod N
  g(w)
 
   | 
Waiting, Not Spinning
  
  -  Spinning wastes resources, usually.
  
-  Move semaphores into the operating system.
    
    -  Threads can now block (leave the CPU) instead of spin. 
    
 
-  Better CPU utilization, but higher overhead (system calls).
  
-  Usually known as blocking semaphores.
  
Blocking Semaphores
class BinarySemaphore
  BinarySemaphore(boolean b) 
    bowl = b
  void take()
    while true
      if bowl
	bowl = false ; break
      else
	pre-empt caller to waiters
  void put()
    bowl = true
    if !waiters.empty()
      schedule a waiter
  private boolean bowl
  private queue waiters
Are We Done?
  
  -   I dunno.  Does this look ok?
BinarySemaphore bowl(true)
 
 
 | | \(\vdots\) |  | 
bowl.put()
  cs
bowl.take()
 |  | \(\vdots\) | 
 | | \(\vdots\) |  | 
bowl.put()
  cs
bowl.put()
 |  | \(\vdots\) | 
 |  
 
-  Semaphore programming is low-level.
    
    -  Hard to get right, hard to keep right, hard to debug.
    
 
Improvements
  
  -  Hide more machinery.
    
    -  No flags, or stones, or bowls.
    
 
-  Fool-proof what remains.
    
    -  No putting before taking, no taking with no putting.
    
 
-  Provide more meaningful interpretations for concurrent control.
    
    -  Concurrency solutions should look like the problem, not patches of
    mutual exclusion.
    
 
For Example
  
  -  The last producer-consumer solution.
queue<widget> q
 | p()
loop
  q.add(f())
 | c()
loop
  g(q.remove())
 
   |  
 
 
   
-  Can we get there?  How do we get there?
  
Hiding Shared State
  
  -  The first step is to hide shared state.
    
    -  Abstract details.
    
-  Protected and controlled access.
    
 
-  Abstract data types (ADTs) do this job nicely.
  
-  Second step: turn the ADT into a critical section.
    
    -  That is, provide mutual exclusion in the ADT. 
    
-  At most one thread in an ADT instance at any time.
    
 
Mutually Exclusive ADTs
ADT
  Shared private state
  private BinarySemaphore mutex(true)
  
| \(\vdots\) | 
| 
  operi(...)
    mutex.put()
      cs
    mutex.take()
 | 
| \(\vdots\) | 
  
  -  At most one operation is executing at any time.
  
Queue Example
ADT queue<T>
  T q[N]
  head = tail = 0
  q-size = 0
|   void add(T e)
    q[tail] = e
    tail = tail+1 mod N
    ++q-size
 |   T remove()
    T e = q[head]
    head = head+1 mod N
    --q-size
    return T
 | 
  
 
Strategic Waiting
  
  -  Adders need a non-full queue; removers need a non-empty queue.
  
-  Can’t semaphores take care of this?
  
ADT queue<T>
  T q[N] ; head = tail = 0 ; q-size = 0
  BinarySemaphore non-empty(false), non-full(true)
|   void add(T e)
    non-full.take()
    q[tail] = e
    tail = tail+1 mod N
    ++q-size
    non-empty.put()
 |   T remove()
    non-empty.take()
    T e = q[head]
    head = head+1 mod N
    --q-size
    non-full.put()
    return T
 | 
Deadlock!
  
  -  Waiting in a critical section ADT is a bad idea.
    
    -  The thread waiting inside can’t do anything. 
    
-  The threads outside can’t come in.
    
-  This is known as deadlock.
    
 
-  The idea is fine, but semaphores aren’t the right tool.
    
    -  Invoke the wait inside the ADT.
    
-  Wait outside the ADT.
    
 
Condition Variables
  
  -  Condition variables are modified binary semaphores.
    
    -  Waiting threads are moved outside the ADT. 
    
-  Also put()=signal(),take()=wait().
  
 
   
Monitors
  
  -  ADTs, mutual exclusion, and condition variables combine to form
  monitors.
    
    -  Synchronized classes in Java. 
    
 
-  Monitors have a wide range of semantics.
    
    -  For almost every part of the monitor. 
    
 
-  Unsurprisingly, monitors are not the last word.
  
Queue Monitor
monitor queue<T>
  T q[N]
  head = tail = 0
  q-size = 0
  condition qUnfull(true), qUnempty(false)
|   void put(T e)
    if q-size ≡ N
      qUnfull.wait()
    q[tail] = e
    tail = tail+1 mod N
    ++q-size
    qUnempty.signal()
 |   T get()
    qUnempty.wait()
    T e = q[head]
    head = head+1 mod N
    --q-size
    qUnfull.signal()
    return T
 | 
Summary
  
  -  Hardware provides fast, simple mutual exclusion.
  
-  Operating systems provide intelligent waiting.
  
-  Semaphores are the bottom of the management hierarchy.
  
-  Monitors provide higher-level concurrency management.
  
-  Even higher-level managers are needed.
  
References
  
  -  Process Scheduling and Unix Semaphores by Neil Dunstan and Ivan Fris in
  Software Practice and Experience, October 1995.
  
-  Java’s Insecure
  Parallelism by Per Brinch Hansen in ACM Sigplan Notices, April 1999.
  
-  Alphonse, Wait Here For
  My Signal! by Stephen Hartley in Proceedings of the Thirtieth SIGCSE
  Technical Symposium on Computer Science Education, March 1999.
  
Credits
  
  
  | This page last modified on 2014 October 9. | 
      |