Roadmap 2: Synchronization

In this road map, we study

  • Synchronization mechanisms: semaphore, lock and condition variables;
  • Atomic operations;
  • Solution to busy waiting;
  • Application of lock and condition to a synchronized list.

  • Start by studying the files utilities/list.*. In list.h, T is defined as a generic type for the items on a list. SortedList is a class derived from the base class List. Member functions provide the usual operations on a linked list, such as inserting and removing an item into and from a list.

    The next step is to review threads/synch.*. These routines contain the data structures and functions to implement synchronization mechanisms. It is well worth reading these two files carefully since they contain excellent documentation.

    You will notice that synch.h defines the data structures for semaphore, lock and condition, the three types of synchronization. Carefully read the comments and the implementations of semaphore, lock, and condition, because they will help you to understand how to use lower level synchronization mechanism to implement higher level semaphore and how to use semaphore to implement lock and condition. In addition think about the following questions:

    What is meant by an atomic operation?
    Why and where do we need atomicity?
    How is atomicity achieved?

    You may go ahead and read threads/synchlist.* to examine how lock and condition are used in a synchronized list.

     

     

    threads/synch.*

    
    // The following class defines a "semaphore" whose value is a non-negative
    // integer.  The semaphore has only two operations P() and V():
    //
    //	P() -- wait if value is not positive, otherwise decrement
    //
    //	V() -- wake up a thread waiting in P() if there is any,
    //             otherwise increment
    // 
    // Note that the interface does *not* allow a thread to read the value of 
    // the semaphore directly -- even if you did read the value, the
    // only thing you would know is what the value used to be.  You don't
    // know what the value is now, because by the time you get the value
    // into a register, a context switch might have occurred,
    // and some other thread might have called P or V, so the true value might
    // now be different.
    
    class Semaphore {
      public:
        Semaphore(char* debugName, int initialValue);    // set initial value
        ~Semaphore();   				     // de-allocate semaphore
        char* getName() { return name;}		     // debugging assist
        
        void P();	        // these are the only operations on a semaphore
        void V();	        // they are both *atomic*
        void SelfTest();    // test routine for semaphore implementation
        
      private:
        char* name;        // useful for debugging
        int value;         // semaphore value, always >= 0
        List<Thread *> *queue;
                           // threads waiting in P() for the value to be > 0
    };
    

    The data structures of a semaphore:

    
                 |------------|
                 |   name     |  solely for debugging purposes
                 |------------|
                 |   value    |
                 |------------|
                 |   queue    |  list of waiting threads
                 |------------|
    

     

     

    The following defines lock and condition variable. Again, read the comments carefully.

     

    threads/synch.*

    
    // 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(); {
                    return lockHolder == kernel->currentThread; }
                                    // return true if the current thread
                                    // holds this lock.
    
        // Note: SelfTest routine provided by SynchList
    
      private:
        char *name;                 // debugging assist
        Thread *lockHolder;         // thread currently holding lock
        Semaphore *semaphore;       // we use a semaphore to implement lock
    };
    

     

     

    Now, the structures of the condition variable.

    threads/synch.*

    
    // 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. The advantage to Mesa-style semantics
    // is that it is a lot easier to implement than Hoare-style.
    
    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;
        List<Semaphore *> *waitQueue;       // list of semaphores
    };
    

    The condition has a list of semaphores, each of which is associated with a waiting thread.

    We first study the implementations of the two semaphore operations.

     

     

    threads/synch.*

    
    //----------------------------------------------------------------------
    // Semaphore::P
    // 	Wait if semaphore value <= 0, otherwise decrement.  Checking
    //	the value and decrementing must be done atomically, so we
    //	need to disable interrupts before checking the value.
    //
    //	Note that Thread::Sleep assumes that interrupts are disabled
    //	when it is called.
    //----------------------------------------------------------------------
    void
    Semaphore::P()
    {
        Interrupt *interrupt = kernel->interrupt;
        Thread *currentThread = kernel->currentThread;
    
        // disable interrupts
        IntStatus oldLevel = interrupt->SetLevel(IntOff);
    
        if (value <= 0) {                   // semaphore not available
            queue->Append(currentThread);   // so go to sleep
            currentThread->Sleep(FALSE);
            // Thread that woke this thread has decremented value already
            // for this thread
        } else {
            value--;            // semaphore available, consume its value
        }
    
        // re-enable interrupts
        (void) interrupt->SetLevel(oldLevel);
    }
    

    We can see that in this implementation of semaphore the atomicity is achieved by turning off interrupts, a lower level mechanism. If the semaphore value is not positive, the calling thread moves to the waiting queue and calls Sleep(). The queue used here to avoid busy waiting.

    Think about:

    Why is atomicity necessary here?
    How does the thread relinquishes the control of the CPU? (Sleep())
    How is a sleeping thread awakened? (V())
    What is the difference between Sleep() and Yield()?
    How can an awakened thread regain the control of the CPU? (return from Sleep())
    Why in this implementation the awakened thread does not check th semaphore value?

     

     

    threads/synch.*

    
    //----------------------------------------------------------------------
    // Semaphore::V
    // 	Wake up a waiter if there is any, otherwise increment.
    //	As with P(), this operation must be atomic, so we need to disable
    //	interrupts.  Scheduler::ReadyToRun() assumes that interrupts
    //	are disabled when it is called.
    //----------------------------------------------------------------------
    void
    Semaphore::V()
    {
        Interrupt *interrupt = kernel->interrupt;
    
        // disable interrupts
        IntStatus oldLevel = interrupt->SetLevel(IntOff);
    
        if (!queue->IsEmpty()) { 
            // a thread waiting on the semaphore, make it ready
            // and give it the possession of the semaphore
            kernel->scheduler->ReadyToRun(queue->RemoveFront());
        } else {
            value++;
        }
    
        // re-enable interrupts
        (void) interrupt->SetLevel(oldLevel);
    }
    

    Questions

    How does the calling thread wake up a thread waiting on the queue?
    What happens to the awakened thread? Does it run immediately? When it runs, what is the first thing it does?
    In this implementation, if there are threads waiting in P(), how is the possession of the semaphore is passed from the calling thread to the awakened thread?

    Before studying lock and condition, we take a look at Sleep() called in P().

     

     

    threads/thread.*

    
    //----------------------------------------------------------------------
    // Thread::Sleep
    //      Relinquish the CPU, because the current thread has either
    //      finished or is blocked waiting on a synchronization
    //      variable (Semaphore, Lock, or Condition).  In the latter case,
    //      eventually some thread will wake this thread up, and put it
    //      back on the ready queue, so that it can be re-scheduled.
    //
    //      NOTE: if there are no threads on the ready queue, that means
    //      we have no thread to run.  "Interrupt::Idle" is called
    //      to signify that we should idle the CPU until the next I/O interrupt
    //      occurs (the only thing that could cause a thread to become
    //      ready to run).
    //
    //      NOTE: we assume interrupts are already disabled, because it
    //      is called from the synchronization routines which must
    //      disable interrupts for atomicity.   We need interrupts off
    //      so that there can't be a time slice between pulling the first thread
    //      off the ready list, and switching to it.
    //----------------------------------------------------------------------
    void
    Thread::Sleep(bool finishing)
    {
        Thread *nextThread;
    
        ASSERT(this == kernel->currentThread);
        ASSERT(kernel->interrupt->getLevel() == IntOff);
    
        DEBUG(dbgThread, "Sleeping thread: " << name);
    
        status = BLOCKED;
        while ((nextThread = kernel->scheduler->FindNextToRun()) == NULL)
            kernel->interrupt->Idle(); // no one to run, wait for an interrupt
    
        // returns when it's time for us to run
        kernel->scheduler->Run(nextThread, finishing);
    }
    

    Sleep() is similar to Yield(). Can you find the difference?

    Now, we study the implementations of lock and condition.

     

     

    
    //----------------------------------------------------------------------
    // Lock::Acquire
    //      Atomically wait until the lock is free, then set it to busy.
    //      Equivalent to Semaphore::P(), with the semaphore value of 0
    //      equal to busy, and semaphore value of 1 equal to free.
    //----------------------------------------------------------------------
    void
    Lock::Acquire()
    {
        semaphore->P();
        lockHolder = kernel->currentThread;
    }
    
    
    //----------------------------------------------------------------------
    // Lock::Release
    //      Atomically set lock to be free, waking up a thread waiting
    //      for the lock, if any.
    //      Equivalent to Semaphore::V(), with the semaphore value of 0
    //      equal to busy, and semaphore value of 1 equal to free.
    //
    //      By convention, only the thread that acquired the lock
    //      may release it.
    //---------------------------------------------------------------------
    void
    Lock::Release()
    {
        ASSERT(IsHeldByCurrentThread());
        lockHolder = NULL;
        semaphore->V();
    }
    

    In this implementation of lock, the atomicity is achieved by the semaphore atomic operations P() and V(). In the constructor of lock, the semaphore value is initialized to one equal to free. The threads waiting for the lock to become free waits on the semaphore queue. When a thread releases the lock, it wakes up a thread waiting on the semaphore queue.

     

     

    
    //----------------------------------------------------------------------
    // Condition::Wait
    //      Atomically release monitor lock and go to sleep.
    //      Our implementation uses semaphores to implement this, by
    //      allocating a semaphore for each waiting thread.  The signaller
    //      will V() this semaphore, so there is no chance the waiter
    //      will miss the signal, even though the lock is released before
    //      calling P().
    //
    //      Note: we assume Mesa-style semantics, which means that the
    //      waiter must re-acquire the monitor lock when waking up.
    //
    //      "conditionLock" -- lock protecting the use of this condition
    //----------------------------------------------------------------------
    void
    Condition::Wait(Lock* conditionLock)
    {
         Semaphore *waiter;
    
         ASSERT(conditionLock->IsHeldByCurrentThread());
    
         waiter = new Semaphore("condition", 0);
         waitQueue->Append(waiter);
         conditionLock->Release();
         waiter->P();
         conditionLock->Acquire();
         delete waiter;
    }
    
    //----------------------------------------------------------------------
    // Condition::Signal
    //      Wake up a thread waiting on this condition, if any.
    //
    //      Note: we assume Mesa-style semantics, which means that the
    //      signaller doesn't give up control immediately to the thread
    //      being woken up (unlike Hoare-style).
    //
    //      Also note: we assume the caller holds the monitor lock
    //      (unlike what is described in Birrell's paper).  This allows
    //      us to access waitQueue without disabling interrupts.
    //
    //      "conditionLock" -- lock protecting the use of this condition
    //----------------------------------------------------------------------
    void
    Condition::Signal(Lock* conditionLock)
    {
        Semaphore *waiter;
    
        ASSERT(conditionLock->IsHeldByCurrentThread());
    
        if (!waitQueue->IsEmpty()) {
            waiter = waitQueue->RemoveFront();
            waiter->V();
        }
    }
    

    Again, in this implementation of condition, the atomicity is achieved by semaphore atomic operations P() and V(). A condition must be associated with a lock. A condition has a list of semaphores. A thread waiting on the condition is blocked on a semaphore. The semaphore value is initialized to zero.

     

     

    Finally, we look at how lock and condition are used in an implementation of unbounded synchronized list. In addition to a list of items of generic type T, a synchronized list has a lock and condition variable.

     

     

    threads/synchlist.*

    
    // The following class defines a "synchronized list" -- a list for which
    // these constraints hold:
    //      1. Threads trying to remove an item from a list will
    //      wait until the list has an element on it.
    //      2. One thread at a time can access list data structures
    
    template <class T>
    class SynchList {
      public:
        ...
      private:
        List<T> *list;              // the list of things
        Lock *lock;                 // enforce mutual exclusive access to the list
        Condition *listEmpty;       // wait in Remove if the list is empty
    
        ...
    };
    

    Let's examine the implementations of Append() and RemoveFront() to see how lock and condition are used.

     

     

    threads/synchlist.*

    
    //----------------------------------------------------------------------
    // SynchList<T>::Append
    //      Append an "item" to the end of the list.  Wake up anyone
    //      waiting for an element to be appended.
    //
    //      "item" is the thing to put on the list.
    //----------------------------------------------------------------------
    template <class T>
    void
    SynchList<T>::Append(T item)
    {
        lock->Acquire();            // enforce mutual exclusive access to the list
        list->Append(item);
        listEmpty->Signal(lock);    // wake up a waiter, if any
        lock->Release();
    }
    
    //----------------------------------------------------------------------
    // SynchList<T>::RemoveFront
    //      Remove an "item" from the beginning of the list.  Wait if
    //      the list is empty.
    // Returns:
    //      The removed item.
    //----------------------------------------------------------------------
    template <class T>
    T
    SynchList<T>::RemoveFront()
    {
        T item;
    
        lock->Acquire();                    // enforce mutual exclusion
        while (list->IsEmpty())
            listEmpty->Wait(lock);          // wait until list isn't empty
        item = list->RemoveFront();
        lock->Release();
        return item;
    }
    
    A lock is used to ensure that one thread at a time can access the list. When the list is empty, threads trying to remove an item from the list are blocked on the condition listEmpty. After a thread puts an item on the list, it wakes up a thread blocked on the condition.