Operating Systems Lecture Notes

13 February 2012 • Synchronization

---

Outline

• A common pattern and its problems.
• Critical sections and controlled access.
• Mutual Exclusion
• Mutexes
  • Pthreads and Java mutexes.
  • Implementing mutexes.

A Common Pattern

• The producer-consumer pattern.
  • Simplifies structure, decouples rates.

  queue buffer producer() while true buffer.put( makeWidget()) consumer() while true munge(buffer.get())

What Could Go Wrong?

queue.put(w):
  if size < n
    size++
    b[tail] = w
    tail = (tail + 1) mod n

queue.get():
  if size > 0
    size--
    w = b[head]
    head = (head + 1) mod n
  return w

An Unfortunate Sequence

• Suppose the queue’s empty (size = 0).

  consumer		producer
  		buffer.put(w)
  		if size < n
  		size++
  context switch
  w = buffer.get()
  if size > 0
  size--
  w = b[head]

Another One

• Suppose size < n - 2 with two producers.

  producer1		producer2
  		buffer.put(w)
  		if size < n
  		size++
  		b[tail] = w
  context switch
  buffer.put(w)
  if size < n
  size++
  b[tail] = w

What Went Wrong?

• Each individual thread did nothing wrong.
• Several threads aren’t necessarily the problem.
  • An orderly sequence of put() and get() calls.
• However, arbitrary context switches can disrupt orderly call sequences.
• These circumstances lead to a race condition (or data race).

Critical Sections

• A critical section (or critical region) is a section of code that
  • manipulates shared state, and
  • can potentially be accessed concurrently.
• Critical sections flag code that can cause race conditions.
• Avoid race conditions by correctly managing critical sections.

Critical Section Example

queue.put(w):
  if size < n
    size++
    b[tail] = w
    tail = (tail + 1) mod n

queue.get():
  if size > 0
    size--
    w = b[head]
    head = (head + 1) mod n
  return w

• critical section code

How Did It Go Wrong?

• A recipe for race conditions:
  1. A shared resource.
  2. Unrestrained concurrent access.
  3. Potential context switches.
• These are necessary conditions.
  • Removing any one of them removes the race condition.
• How can race conditions be dealt with?

No Sharing

• No shared resources, no race conditions.
  • But shared resources are anywhere from nice to necessary.
  • The OS contains resources shared with a processes.
• A related design objective: minimize sharing.
  • Doesn’t prevent race conditions.
  • Makes them easier and less expensive to manage.

No Interrupts

• No interrupted execution, no race conditions.
• Ignore interrupts. But
  • Interrupts carry important information.
  • Interrupts help implement OS resources.
  • Interrupts support required system characteristics.
• Ignore interrupts, but not too much.
  • Keep critical sections short and fast.

No Interrupts Example

queue.put(w):
  disableinterrupts()
  if size < n
    size++
    b[tail] = w
    tail = (tail + 1) mod n
  ensableinterrupts()

queue.get():
  disableinterrupts()
  if size > 0
    size--
    w = b[head]
    head = (head + 1) mod n
  ensableinterrupts()
  return w

Are We Done?

• Alas, no.
  • Ignoring interrupts is dangerous.
  • Ignoring interrupts is too strong.
    • A non-sharing thread interruption is fine.
  • Multi-CPU systems still have race conditions.
• Interrupts solve the problem, but are way too big a hammer to use in general.

Controlled Access

Access Control

• A thread must “hold the key” whenever it’s in a critical section.
• The thread “returns the key” when it exits the critical section.
  • But not when it gets context switched out.
• This protocol enforces a one-thread max policy for a critical section.
• The “one-thread max” policy is known as mutual exclusion.

Providing Mutual Exclusion

• A mutex is a lock-and-key data structure for mutual exclusion.
  • mutex.lock() - get the key, lock the mutex. Block if the key’s not available.
  • mutex.unlock() - Unlock the mutex, return the key. Wake up a thread blocked during a lock.
• There may be (usually are) other operations on a mutex.

Mutex Transitions

• A mutex is usually created open.
• The blocked→locked transition is triggered by the locked→open unlock().
  • If there’s a blocked thread.
  • Which blocked thread is unblocked depends on the mutex.

Mutex Illustrated

• Threads compete over the mutex.
  • Which is designed to resolve competition.
• The winner goes on to the buffer.

  

Mutex Example

mutex buffermutex  // unlocked to start
queue buffer        // empty to start

producer:
  while true
    widget w = makeWidget()
    buffermutex.lock()
    buffer.put(w);
    buffermutex.unlock()

consumer:
  while true
    buffermutex.lock()
    widget w = buffer.get()
    buffermutex.unlock()
    munge(w)

Pthreads Mutexes

pthread_mutex_t m

int pthread_mutex_lock(
  pthread_mutex_t *mutex)

int pthread_mutex_trylock(
  pthread_mutex_t *mutex)

int pthread_mutex_unlock(
  pthread_mutex_t *mutex)

• trylock() doesn’t block, but returns false when it tries to lock a locked mutex.

Java Mutexes

• Each Java object has a mutex, but it’s hidden.
• A synchronous method locks the mutex on method entry and unlocks it on method exit.
  • But not all methods need be synchronous.
• Basic Java concurrency semantics are ridiculous.
  • More modern concurrency libraries make things somewhat easier.

Java Example

class ProtectedQueue
  

  private Queue q;
  

  synchronous put(e)
    q.put(e)
  

  synchronous get()
    return q.get()

ProtectedQueue pbuffer
  

producer()
  while true
    pbuffer.put(makeWidget())
  

consumer()
  while true
    munge(pbuffer.get())

Implementing Mutexes

• Without looking too closely, mutexes are easy to implement:

  class mutex
  
    private bool locked
  
    void lock()
      if locked
        wait until unlocked
      lock = true
  
    void unlock
      lock = false
      if waiting threads
        wake one up

Oh Really?

• Suppose mutex m is unlocked.

  thread1		thread2
  		m.lock()
  		if locked
  context switch
  m.lock()
  if locked
  locked = true
  context switch
  		locked = true

The Cobbler’s Children

• The mutex code itself is a critical section.
  • The resource providing mutual exclusion needs mutual exclusion to work.
• In this case, disabling interrupts may be appropriate.
  • A small, well defined (?) critical section.
  • But even if correct, disabling interrupts doesn’t work on multi-processor machines.
    • The other processors have interrupts enabled.

Implementing Mutexes Redux

void lock()
  disableinterrupts()
  if locked
    wait until unlocked
  lock = true
  enableinterrupts()

void unlock()
  disableinterrupts()
  lock = false
  if waiting threads
    wake one up
  enableinterrupts()

• Does this work?

Needs More Interrupts

• A thread executing

  void lock()
    disableinterrupts()
    if locked
      wait until unlocked
    lock = true
    enableinterrupts()

• on a locked mutex blocks before it can re-enable interrupts.
  • At which point the game ends.

Implementing Mutexes Redux

void lock()
  disableinterrupts()
  if locked
    enableinterrupts()
    wait until unlocked
    disableinterrupts()
  lock = true
  enableinterrupts()

void unlock()
  disableinterrupts()
  lock = false
  if waiting threads
    wake one up
  enableinterrupts()

• Does this work?

Oh Really?

• Suppose thread₂ has locked mutex m.

  thread1		thread2		thread3
  m.lock()
  disable interrupts()
  if locked
  enable interrupts()
  wait
  context switch
  		m.unlock()
  context switch
  				m.locked()
  context switch
  disable interrupts()
  lock = true
  enable interrupts()

One More Time

void lock() disableinterrupts() while ¬locked enableinterrupts() wait until unlocked disableinterrupts() lock = true enableinterrupts() void unlock() disableinterrupts() lock = false if waiting threads wake one up enableinterrupts()

The unblocked thread rechecks the lock under mutual exclusion. Does this work now?

The Last Time

void lock() disableinterrupts() while ¬locked enableinterrupts() disableinterrupts() lock = true enableinterrupts() void unlock() lock = false

Waiting threads aren’t blocked, but constantly spin. This requires a pre-emptive scheduler.

• This is known as a spin lock.
  • Useful on system with processors to burn.

Summary

• Many common thread-interaction patterns share data structures.
• Concurrenty accessed shared data structures represent critical sections.
• Properly used, critical sections are accessed under mutual exclusion.
• The mutex data structure is the simplest providing mutual exclusion.
  • With a little discipline.

References

• Synchronization and Deadlocks, Chapter 4, in Operating Systems and Middleware by Max Hailperin, Thompson, 2007.

Credits

• My Room Key, Fun Island by Bilal Mirza under a Creative Commons BY ND license.

---

This page last modified on 2012 February 13.