Locks and Condition Variables

Tom Kelliher, CS42

Oct. 7, 1996

Locks

// The following class defines a "lock".  A lock can be BUSY or FREE.
// There are only two operations allowed on a lock: 
//
// Acquire -- wait until the lock is FREE, then set it to BUSY
//
// Release -- set lock to be FREE, waking up a thread waiting
//    in Acquire if necessary
//
// In addition, by convention, only the thread that acquired the lock
// may release it.  As with semaphores, you can't read the lock value
// (because the value might change immediately after you read it).  

class Lock {
  public:
    Lock(char* debugName);       // initialize lock to be FREE
    ~Lock();            // deallocate lock
    char* getName() { return name; }   // debugging assist

    void Acquire(); // these are the only operations on a lock
    void Release(); // they are both *atomic*

    bool isHeldByCurrentThread();   // true if the current thread
               // holds this lock.  Useful for
               // checking in Release, and in
               // Condition variable ops below.

  private:
    char* name;            // for debugging
    // plus some other stuff you'll need to define
};

How does a lock compare to a semaphore?

Why not just use a semaphore?

Condition Variables

// The following class defines a "condition variable".  A condition
// variable does not have a value, but threads may be queued, waiting
// on the variable.  These are only operations on a condition variable: 
//
// Wait() -- release the lock, relinquish the CPU until signaled, 
//    then re-acquire the lock
//
// Signal() -- wake up a thread, if there are any waiting on 
//    the condition
//
// Broadcast() -- wake up all threads waiting on the condition
//
// All operations on a condition variable must be made while
// the current thread has acquired a lock.  Indeed, all accesses
// to a given condition variable must be protected by the same lock.
// In other words, mutual exclusion must be enforced among threads calling
// the condition variable operations.
//
// In Nachos, condition variables are assumed to obey *Mesa*-style
// semantics.  When a Signal or Broadcast wakes up another thread,
// it simply puts the thread on the ready list, and it is the responsibility
// of the woken thread to re-acquire the lock (this re-acquire is
// taken care of within Wait()).  By contrast, some define condition
// variables according to *Hoare*-style semantics -- where the signalling
// thread gives up control over the lock and the CPU to the woken thread,
// which runs immediately and gives back control over the lock to the 
// signaller when the woken thread leaves the critical section.
//
// The consequence of using Mesa-style semantics is that some other thread
// can acquire the lock, and change data structures, before the woken
// thread gets a chance to run.

class Condition {
  public:
    Condition(char* debugName);     // initialize condition to 
               // "no one waiting"
    ~Condition();       // deallocate the condition
    char* getName() { return (name); }
    
    void Wait(Lock *conditionLock);    // these are the 3 operations on 
               // condition variables; releasing the 
               // lock and going to sleep are 
               // *atomic* in Wait()
    void Signal(Lock *conditionLock);   // conditionLock must be held by
    void Broadcast(Lock *conditionLock);// the currentThread for all of 
               // these operations

  private:
    char* name;
    // plus some other stuff you'll need to define
};

Meaning

How are condition variables and locks used together?

1. Lock --- controls access to shared variables. Suppose thread needs to wait on some resource within critical section?

2. Condition variables --- Wait for a condition to be signaled, relinquishing lock in the meanwhile.

Usage Examples

Bounded Buffers

Global variables:

Buffer b;
Lock l;
Condition nonFull;
Condition nonEmpty;

Producer:

while (1)
{
   produce into next;
   l.lock();
   while (b.full())
      nonFull.wait(l);
   b.insert(next);
   nonEmpty.signal(l);
   l.release();
}

1. The critical section.

2. The wait loop.

3. Shouldn't we look before we signal?

Consumer:

while(1)
{
   l.lock();
   while (b.empty()
      nonEmpty.wait(l);
   next = b.remove();
   nonFull.signal();
   l.release();
}

Readers Writers Problem

1. Shared information.

2. Any number of threads can read simultaneously.

3. Only one thread can write (no reading during writing).

4. Writing has priority.

Global variables:

Lock l;
Condition wGo;
Condition rGo;
bool wantToWrite = FALSE;
int nReaders = 0;

Writer:

l.lock();
wantToWrite = TRUE;
while (nReaders > 0)
   wGo.wait(l);
write...
wantToWrite = FALSE;
rGo.broadcast(l);
l.release();

Reader:

l.lock();
while (wantToWrite)
   rGo.wait(l);
++nReaders;
l.release();
read...
l.lock();
--nReaders;
if (nReaders == 0)
   wGo.signal();
l.release();

1. Where do the readers wait while the writer writes?

2. Why does the reader release the lock before reading?

3. Why does the writer use broadcast?

4. Why don't all the readers signal wGo?

Implementation of Locks and Condition Variables