Operating Systems Lecture Notes

2014 October 9 • Concurrency Managers

Outline

• Recap
• Better primitives.
  • Hardware assist.
• 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-set instruction.
  • The bowl is a boolean variable b.
  • If b = true, the bowl holds the stone.
  • If b = false, the bowl is empty.
• test-and-set is a non-interruptable, non-privileged instruction in modern architectures.
  • SPARC v9 ldstub instruction.

test-and-set

• The effect of test-and-set is

  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-set returns true and the bowl is empty.
  • Otherwise test-and-set returns false.

Test-and-Set Critical Sections

• A test-and-set critical section:

  bool bowl-csi = true
  
  enter csi
    while !test-and-set(bowl-csi) { }
  
  exit csi
    bowl-csi = true
  

• bowl is usually called lock.

Binary Semaphores

class BinarySemaphore

  BinarySemaphore(boolean b) 
    bowl = b

  void put()
    bowl = true

  void take()
    while test-and-set(bowl) { }

  private boolean bowl

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

• But what’s missing?

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

• stone in a bowl, with soap & occasional ice by greg under a Creative Commons BY ND license.
• pebble bowl by Leo Reynolds under a Creative Commons BY NC SA license.