Lecture Notes for Concurrent Programming

10 July 2003 - Locking

Locking

• Synchronization and Locking

• Custom Locks

  • The Lock Interface

  • The Mutex Lock

  • Unconditional Lock Acquisition

  • Conditional Lock Acquisition

  • Lock Retry

• General Mutex Use

  • A Mutex Method Adapter

  • A Mutex Template Pattern

• Higher-Level Use Patterns

  • Read-Write Locking

Synchronization

• What's wrong with synchronize?

  • Too simple locking semantics.

    • No testing, timeouts, or interruptions.

  • Fixed and weak lock semantics.

    • Reentrant, waiting fairness.

  • No access control.

    • Instance access provides lock access.

  • Block structured locks and unlocks.

    • No split binaries, no baton passing.

• If you want these, you have to make them.

Custom Locks

• What's wrong with making your own?

  • More cumbersome to use than synchronize.

    • But: use patterns to help.

  • Difficult to enforce correct use mechanically.

    • But: patterns again, and a positive discouragement.

  • Harder to optimize automatically.

    • But: built to exploit problem-specific features.

  • Missing features, such as wait sets.

    • But: you can make your own.

The Lock Interface

• A generic locking interface.

  • Lock a lock, blocking if necessary.

  • Unlock a lock.

  • Try to lock a lock.

    • Retry t times, waiting w msec between tries.

    • Return true iff the lock was acquired.

  interface Lock
  
    void lock()
    throws InterruptedException
  
    void unlock()
  
    boolean tryLock(int retries, long wait)
    throws InterruptedException
  

• Locking is interruptible.

The Mutex Lock

• A binary semaphore.

  class Mutex
  implements Lock
  
    private boolean locked
  
    public Mutex(boolean locked)
      this.locked = locked
  

• Lock release.

  public synchronized void unlock()
    locked = false
    notify()
  

  • notify() is unfair; use notifyAll() for fairness.

    • But notifyAll()'s expensive.

Unconditional Lock Acquisition

public void lock()
throws InterruptedException

  if (Thread.interrupted()) 
    throw new InterruptedException()

  synchronized (this)
    try
      while (locked) wait();
      locked = true
    catch (InterruptedException ie)
      notify()
      throw ie

• Pass along the thread-interrupt exception.

• Remember interrupts race with notify().

  • The interrupted thread could be the notified thread too.

  • Re-notify so as not to lose the original notify.

Conditional Lock Acquisition

public boolean 
tryLock(int retries, long delay) 
throws InterruptedException

  if (Thread.interrupted()) 
    throw new InterruptedException()

  boolean got_lock

  synchronized (this)

    if (!locked)
      locked = true
      return true

    if ((delay < 1) || (retries < 1))
      return false

    do got_lock = retry(delay)
    while (!got_lock && --retries > 0)

  return got_lock

Lock Retry

• Bound (sorta) the lock attempts.

  private boolean retry(long delay)
    try
      long startTime = 
        System.currentTimeMillis()
      long delayTime = msecs
  
      while true
        wait(delayTime)
        if !locked
  	locked = true
  	return true
        else
  	long now = 
  	  System.currentTimeMillis()
  	delayTime = 
  	  msecs - (now - startTime)
  	if (delayTime <= 0)
  	  return false
  
    catch InterruptedException ie
      notify()
      throw ie
  

• Notice the wait(long) object method.

General Mutex Use

• A mutex can take the place of a synchronized block.

  synchronize (lock) { /* whatever */ }
  
  try
    mutex.lock()
    try
      // whatever
    finally
      mutex.unlock()
  catch (InterruptedException ie)
    // cancellation behavior.
  

• This is painful syntax; ease the pain with layering.

  • Use method adaption, or template patterns.

A Mutex Method Adapter

• Given unsynchronized methods,

  class Unsynchronized
  
    private String [] records
  
    void op()
      // whatever
  
  

  wrap them in synchronized methods.

  class Synchronized
  extends Unsynchronized
  
    private mutex mtx
    
    void op()
      try
        try 
  	mtx.lock()
  	super.op()
        finally 
          mtx.unlock()
      catch InterruptedExecution
        Thread.currentThread().interrupt()
  

A Mutex Template Pattern

• The Template Pattern abstracts a repeated algorithm structure.

• A mutex template pattern abstracts the algorithm for safe mutex locking.

  abstract class MutexTemplate
  
    private Mutex mutex = new Mutex(false)
  
    void execute(Object o)
      try
        mutex.lock()
        function(o)
      catch (InterruptedException ie)
        interrupt(ie)
      finally { mutex.unlock() }
  
    abstract protected void 
    function(Object o)
  
    abstract protected void 
    interrupt(InterruptedException ie)
  

Example Matrix Template Use

• The template abstract methods provide customization.

  • function() does the work.

  • interrupt() does the clean-up.

  • Define the abstract members function() and interrupt() in a concrete subclass of the template class.

  class counter 
  extends MutexTemplate
  
    private int count = 0
  
    public void 
    addTo(int i)
      function(new Integer(i))
  
    protected void 
    function(Object o)
      count += ((Integer) o).intValue()
  
    protected void 
    interrupt(InterruptedException ie) { }
  

• A template pattern is finer grained than a method adaptor.

Higher-Level Use Patterns

• Capture higher-level locking behaviors.

  • Split-binary locking.

  • Read-write locking.

  • Hand-over-hand locking.

• Use patterns to make these behaviors generic.

• This is one way to start building a concurrency tool-kit.

• This is difficult to do, but the rewards are great.

  • There is much variation within particular behaviors.

  • The best pattern usually reveals itself slowly.

  • In the mean time, you've got all these variations.

Read-Write Locking

• Mutexes paired to provide reader-writer behavior.

  • Shared readers, exclusive writers; fairness and timely updates.

• Abstract the read-write locking behavior in an interface.

  interface RWLock
    Lock readLock()
    Lock writeLock()
  

• Implement readers and writers to the interface.

  class Writer
  implements Runnable
  
    private RWLock rwLock
  
    Writer(RWLock rwl)
      rwLock = rwl
  
    void run() 
      rwLock.writeLock.lock()
      // whatever
      rwLock.writeLock.unlock()
  

Points to Remember

• Sometimes you really can't live without synchronization.

  • And locking is the simplest form of synchronization.

• Consider rolling your own locks.

  • Better, more appropriate semantics can simplify things enormously.

• Although custom locks simplify, they can also complicate.

  • Looser host language integration requires more care in use.

• Ease the pain of using custom locks with software patterns.

  • The Mutex-Method Adapter and Mutex Template Pattern, for example.

• Capture your custom lock use in ever higher-level patterns.

  • And you're on your way to building your concurrency toolkit.

This page last modified on 17 July 2003.