next up previous contents
Next: Multiprogramming Up: Experience With Nachos Assignments Previous: General Tips

Synchronization

Testing the correctness of the synchronization facilities is difficult if only Nachos threads are used because Nachos preempts threads only at well defined points (e.g., when disabling or re-enabling interrupts). Thus, many incorrect solutions tend to work on the simple test cases students use. Fear not, later assignments test the synchronization facilities extensively and will uncover problems. Here are some suggestions for simplifying later debugging:

  1. For the locking routines, have Acquire verify that the caller does not already hold the lock via an ASSERT statement. One common problem occurring in later assignments involves nested locking, where a thread already holding a lock attempts to acquire it again. Nachos can't always detect this deadlock condition itself (e.g, if the Console device is in use) and students with deadlocked programs spend a long time not knowing where to look before they realize they've deadlocked.

Another most common mistake students made while implementing locks is failing to understand their semantics (even having covered them in class). Specifically, students tended to have a flag or counter associated with condition variables. The following explanation will hopefully clarify this point and explain why a condition variable cannot have a value.

Semaphores have a count associated with them. This count is a ``memory'' that allows a semaphore to ``remember'' how many times the semaphore has been signalled (via P) relative to the number of times it has been signalled (via V). Semaphores are useful as gatekeepers that must limit the number of persons (threads) allowed to be in a room simultaneously. Threads enter the room enter through one door (the P operation) and leave through a second door (the V operation). The semaphore's value keeps track of the number of threads in the room at any given time. If the semaphore's initial value is 1, only one thread may be in the room at a time, whereas an initial value of 100 allows the room to hold 100 threads.

In contrast, a condition variable has no value associated with it. If a thread invokes Wait, it blocks no matter what! Specifically, it blocks regardless of how many previous Signal operations were performed. In contrast, the semaphore P operation blocks only when the count is non-positive, with the current value dependent on the initial counter and the number of V operations that have been performed. One uses a semaphore (and its counter) only when the number of P's and V's must balance each other. Note also that the condition Signal operations wakes up one blocked thread (if one is waiting on the condition), but has no effect otherwise. If there are no threads waiting on a condition, executing Wait one time has the same effect as executing it 1,000 times (e.g., no effect). Compare this behavior with the semaphore V operation. Even when no threads are waiting on the semaphore, the V operation increments the semaphore's value, which influences P's behavior later.

There are times when a thread may wish to wait for some future event, but the conditions necessary that define the event can't be described with a simple count. For example, a thread may wish to wait for two resources to become available simultaneously, but does not wish to hold one while it is blocked waiting for the other. In this case, a thread might wait on a condition variable, with another thread issuing a Signal when the necessary condition (both resources available simultaneously) becomes true. Note that only the code that calls Signal and Wait know what the exact conditions are. Thus, the condition variable itself cannot hold a meaningful value.

Finally, note that Nachos intends condition variables to have ``Mesa-style'' semantics. In brief, when a Signal operation releases a thread, that thread can not assume that the condition that it waited for is now true. It must first reassert that the necessary condition still holds (e.g., it must test the condition in a while loop, calling Wait again whenever the condition is false). This is necessary because another thread may be scheduled and execute between the time of Signal and the running of the waiting thread. That intermediate thread may change the state of the system so that the waited-on condition no longer holds.


next up previous contents
Next: Multiprogramming Up: Experience With Nachos Assignments Previous: General Tips

Thomas Narten
Mon Feb 3 15:00:27 EST 1997