Roadmap 2: Synchronization

In this road map, we study

Start by studying the files threads/list.*. List.h defines two classes - ListElement and List whereas list.cc implements the associated member functions. Here is a few lines of code from list.h.

class ListElement {
   public:
     ListElement(void *itemPtr, int sortKey);	// initialize a list element

     ListElement *next;		// next element on list, 
				// NULL if this is the last
     int key;		    	// priority, for a sorted list
     void *item; 	    	// pointer to item on the list
};

class List {
  public:
    List();			// initialize the list
    ~List();			// de-allocate the list

    void Prepend(void *item); 	// Put item at the beginning of the list
    void Append(void *item); 	// Put item at the end of the list
    void *Remove(); 	 	// Take item off the front of the list
    ...
  

  private:
    ListElement *first;  	// Head of the list, NULL if list is empty
    ListElement *last;		// Last element of list
};
    ...

Note

From studying the above code, you will notice that the List class refers to a linked list which contains elements of type ListElement. You should be able to create a mental picture of the list data structure, and it should look something as follows. Later on, we will be using threads to manipulate data in linked lists.

	|-----------------|			|-----------------|
	|       Next    --|--> 			|       Next    --|-->
	| Pointer to next |			| Pointer to next |
	| element in list |			| element in list |
	|-----------------|			|-----------------|
	| Key (priority   |	............	| Key (priority   |
	| of sorted list) |			| of sorted list) |
	|-----------------|			|-----------------|
	|       item    --|--> 			|       item    --|-->
	| Pointer to some |			| Pointer to some |
        | item on list    |			| item on list    |
	|-----------------|			|-----------------|


		^					^
		|					|
		|					|
	      First   				      Last
	(pointer to first list element)		 (pointer to last list element)

Note

Make sure you review list.cc to understand the operations which can be performed on list (e.g. Prepend(), Append(), Remove(), SortedInsert(), etc.)

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 semaphores, locks and conditions - the three types of synchronization. However only Semaphore is implemented. Carefully read the comments and the implementation of semaphore because it will help you to understand how 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?

Make sure you read the comments at the end of synch.cc. The stub functions which you are supposed to implement are listed there. In addition, read threads/synchlist.* to examine how the functions that you will be developing are utilized. That is, look at how synchlist uses lock and conditions.

// The following class defines a "semaphore" whose value is a non-negative
// integer.  The semaphore has only two operations P() and V():
//
//	P() -- waits until value > 0, then decrement
//
//	V() -- increment, waking up a thread waiting in P() if necessary
// 
// 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*
    
  private:
    char* name;        // useful for debugging
    int value;         // semaphore value, always >= 0
    List *queue;       // threads waiting in P() for the value to be > 0
};

Note

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. You are supposed to implement lock and condition following the comments.

// 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
};

Note

// 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
};

Note

//----------------------------------------------------------------------
// Semaphore::P
// 	Wait until semaphore value > 0, then 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()
{
    IntStatus oldLevel = interrupt->SetLevel(IntOff);	// disable interrupts
    
    while (value == 0) { 			// semaphore not available
	queue->Append((void *)currentThread);	// so go to sleep
	currentThread->Sleep();
    } 
    value--; 					// semaphore available, 
						// consume its value
    
    (void) interrupt->SetLevel(oldLevel);	// re-enable interrupts
}

One point to note in the above code is the call to Sleep() which is made if the semaphore is not available. This is done to avoid busy waiting, so that the thread does not repeatedly use CPU time to poll the value of the semaphore.

Think about:

//----------------------------------------------------------------------
// Semaphore::V
// 	Increment semaphore value, waking up a waiter if necessary.
//	As with P(), this operation must be atomic, so we need to disable
//	interrupts.  Scheduler::ReadyToRun() assumes that threads
//	are disabled when it is called.
//----------------------------------------------------------------------

void
Semaphore::V()
{
    Thread *thread;
    IntStatus oldLevel = interrupt->SetLevel(IntOff);

    thread = (Thread *)queue->Remove();
    if (thread != NULL)	   // make thread ready, consuming the V immediately
	scheduler->ReadyToRun(thread);
    value++;
    (void) interrupt->SetLevel(oldLevel);
}

// Dummy functions -- so we can compile our later assignments 
// Note -- without a correct implementation of Condition::Wait(), 
// the test case in the network assignment won't work!
Lock::Lock(char* debugName) {}
Lock::~Lock() {}
void Lock::Acquire() {}
void Lock::Release() {}

Condition::Condition(char* debugName) { }
Condition::~Condition() { }
void Condition::Wait(Lock* conditionLock) { ASSERT(FALSE); }
void Condition::Signal(Lock* conditionLock) { }
void Condition::Broadcast(Lock* conditionLock) { }

//----------------------------------------------------------------------
// Thread::Sleep
// 	Relinquish the CPU, because the current thread is blocked
//	waiting on a synchronization variable (Semaphore, Lock, or Condition).
//	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 ()
{
    Thread *nextThread;
    
    ASSERT(this == currentThread);
    ASSERT(interrupt->getLevel() == IntOff);
    
    DEBUG('t', "Sleeping thread \"%s\"\n", getName());

    status = BLOCKED;
    while ((nextThread = scheduler->FindNextToRun()) == NULL)
	interrupt->Idle();	// no one to run, wait for an interrupt
        
    scheduler->Run(nextThread); // returns when we've been signalled
}

Note

What are the differences between Sleep() and Yield()?

// 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

class SynchList {
  public:
    SynchList();                // initialize a synchronized list
    ~SynchList();               // de-allocate a synchronized list

    void Append(void *item);    // append item to the end of the list,
                                // and wake up any thread waiting in remove
    void *Remove();             // remove the first item from the front of
                                // the list, waiting if the list is empty
                                // apply function to every item in the list
    void Mapcar(VoidFunctionPtr func);

  private:
    List *list;                 // the unsynchronized list
    Lock *lock;                 // enforce mutual exclusive access to the list
    Condition *listEmpty;       // wait in Remove if the list is empty
};