Lecture Notes for Concurrent Programming

30 July 2002 - Synchronization Utilities

Synchronization Utilities

• Semaphores

• Latches

• Exchangers

• Condition Variables

Semaphores

• Counting semaphores are useful for resource management.

  • More than one stone in the bowl.

  • Available resource count equals available stone count.

• Semaphore uses.

  • Resource pools.

  • Bounded buffers.

    • Two resources: empty and full slots.

  • Synchronous channels.

    • Like a no-slot buffer.

Semaphore Implementation

 
 class Semaphore

   private Mutex mtx(false), waitq(false)
   private int count, waiters = 0

   Semaphore(int count) { this.count = count }

   void down() throws InterruptedException
     mtx.lock()

     while count < 1
       waiters++
       mtx.unlock()

       try { waitq.lock() }
       catch (InterruptedException ie)
	 synchronized (this) { waiters-- } ; throw ie 

       try mtx.lock()
       catch (InterruptedException ie)
	 synchronized (this) { waiters-- } ; throw ie 
       waiters--

     count--
     mtx.unlock()

   void up()
     try mtx.lock()
     catch (InterruptedException ie) return
     count++
     if (waiters > 0) waitq.unlock()
     mtx.unlock()
 

Latches

• A binary variable that changes state at most once.

  • Threads block, waiting for the change.

  • No more blocking once the change occurs.

• Latches are good for 1-to-m synchronization.

  • m threads waiting for data initialization to finish.

• Latches are good for (1-out-of-m)-to-1 synchronization.

  • A boss waiting for the first of m workers to finish.

• Latches are not good for m-to-1 synchronization.

  • They can't count past one.

• Latches are not good for barrier synchronization.

  • A barrier provides repeated synchronization.

Latch Implementation

 class Latch

   // Invariant:  ready implies the wait set is empty.

   private boolean ready = false

   synchronized void block() 
   throws InterruptedException
     try { while (!ready) wait() }
     catch (InterruptedException ie) 
       throw ie

   void unblock()
     if !ready
       ready = true
       notifyAll()

• block() must be synchronized. Why?

  • A spin lock eliminates mutual exclusion.

    void block() 
      while (!ready) yield()
    

  • It's expensive, though.

Exchangers

• Two threads synchronize by exchanging instance references.

  • A producer and consumer exchanging empty and full buffers.

    

• This is not like remote procedure calls.

  • Or Ada's rendezvous.

  • The exchange is instantanious, no time for computation.

• It's also not like opposing one-way channels.

  • The reference exchange is synchronized.

• Exceptions need to be exchanged as well.

  • One side should know the other side's gone.

Exchanger Implementation

 class Exchanger

   private Object fst, snd
   private boolean interrupted = false

   synchronized Object exchange(Object o) 
   throws InterruptedException

     if interrupted
       interrupted = false
       throw new InterruptedException()

     if fst != null
       snd = o
       notify()
       return fst

     fst = o
     try { while (snd == null) wait() }
     catch (InterruptedException ie)
       fst = null
       interrupted = true
       throw ie

     return snd

• Reuse after an interrupt is probably dumb.

Single Wait Sets

• Each class instance has one wait set.

• All conditions look the same.

• Have to release all waiters when any condition changes.

  class NSlotBuffer
  
    private final boolean Full = false
    private final boolean Empty = true
    private final Object[] buffer = new Object[N]
  
    synchronized public void put(Object o)
      while full wait()
      // Add o to the buffer.
      full = buffer.size == N
      empty = false
      notifyAll()
  
    synchronized public Object get()
      while empty wait()
      // Take o from the buffer.
      empty = buffer.size == 0
      full = false
      notifyAll()
      return o
  

Condition Variables

• A condition variable is a wait set independent of class instance.

  class ConditionVariable
  
    private final Mutex mutex
  
    ConditionalVariable(Mutex lock) { mutex = lock }
  
    public void pause()
  
    public boolean tryPause(long delay) 
  
    public void proceed()
  
    public void proceedAll()
  

• The mutex represents the per-instance lock.

  • Several condition variables may share a mutex.

Condition Variable Example

• Using Mutex to implement conditional synchronization.

  class NSlotBuffer
  
    private final Mutex mutex = new Mutex()
    private final CondVar notFull = new CondVar(mutex)
    private final CondVar notEmpty = new CondVar(mutex)
    private final Object[] buffer = new Object[N]
  
    public void put(Object o)
      mutex.lock()
      try
        while (buffer full) notFull.pause()
        // Add o to the buffer.d
        notEmpty.proceed()
      finally mutex.unlock()
  
    public Object get()
      mutex.lock()
      try
        while (buffer empty) notEmpty.pause()
        // Take o from the buffer.
        notFull.proceed()
      finally mutex.unlock()
      return o
  

Condition Variable Implementation

 public class ConditionVariable

   public void pause() throws InterruptedException

     if Thread.interrupted() 
       throw new InterruptedException()

     try
       synchronized this
	 mutex.unlock()  // It's locked coming in.
	 try wait() 
	 catch (InterruptedException ex)
	   notify()
	   throw ex
     finally
       boolean interrupted = false
       while true
	 try
	   mutex.lock()
	   break
	 catch (InterruptedException ex)
	   interrupted = true
       if interrupted
	 Thread.currentThread().interrupt()

   public synchronized void proceed()
     notify()

Points to Remember

• Use the right tool for the job.

  • Use the simplest tool for the job.

• You may have to roll your own tools.

  • Your concurrency toolkit should help you.

This page last modified on 8 August 2002.