First, implementing the lock and condition variable functions is not the hard part of this assignment. You should be able to draw heavily on the existing semaphore implementation, and should be able to complete this part in one coding session. (Assuming of course you have prepared adequately by answering the code reading questions and understand what each of these functions needs to do.)
I have had some questions about the use of the argument to thread_sleep/thread_wakeup. OS/161 keeps all sleeping threads on a single list, so we need some way to associate a thread with the synchronization object (a semaphore, lock, or condition variable) that it is waiting for. If every object has a unique "key" value, we can store that "key" with the sleeping thread, and search the list of sleepers for threads that match the "key" when we want to wake up a thread waiting for that object. Since each object has a unique location in memory, we can use the address of the object as our "key" value. In C, the value of a pointer to an object is the address of that object.
Implement and test the lock code fully before starting on the condition variables.
Write the pseudocode for lock_do_i_hold(), lock_acquire() and lock_release(). Remember that these operations are logically atomic functions, just like the semaphore P() and V() operations. How does the semaphore implementation guarantee that P() and V() are atomic?
Think about correct use of locks and use assert() statements to catch situations where they are being used incorrectly. Think about how the use of locks differs from the use of semaphores. For example, a semaphore can be signalled by any thread, but a lock should only be released by the thread that is the "owner" or "holder" of the lock.
Remember you always have a pointer to the currently-executing thread in the global "curthread" variable.
For testing your implementations, take a look at the built-in synch tests ("sy1" at the OS/161 menu tests the semaphore implementation, "sy2" tests the lock implementation and "sy3" tests the condition variable implementation). These are implemented in kern/test/synchtest.c. You should look at this code and make sure you understand how they are testing the various synchronization objects. Try running "sy2" and "sy3" without any implementations for locks and condition variables to see what happens when the tests fail.
When you have a correct implementation of locks, the "sy2" test is very quiet. It takes about 10 seconds to complete if everything goes well. If it takes much longer and you get no output, you probably have a deadlock and need to re-examine your lock implementation.
Existing bootstrap code (particularly in the dev_bootstrap routines) uses locks. If you have a problem with your lock implementation, your kernel may not make it past the bootstrapping to the menu routine at all. If this happens, attach the debugger, set breakpoints at the lock_acquire and lock_release functions and step through them line-by-line, paying attention to how and when you are changing the lock state and making threads wait.
For reference, not counting "assert" statements, and the code to disable/restore interrupts, my lock implementations are less than 10 lines of code.
The original idea behind a condition variable is to allow a thread to suspend itself while executing in a monitor until some boolean condition is satisfied. "Executing in a monitor" implies that the thread is holding some lock, which must be passed as an argument to the cv_wait function. Threads that call cv_wait() always block, and it is important that they release the lock before doing so. Before returning from cv_wait(), the thread must re-acquire the lock. Thus, the lock is held when cv_wait() is called, and is held when cv_wait returns, but must be released while the thread sleeps.
The pseudocode for cv_wait() is given below:
cv_wait(struct lock *lock, struct cv *cv) {
// Atomically, do the following:
// 1. release the lock
// 2. put the thread to sleep on the condition variable "cv"
// 3. re-acquire the lock
}
The "signal" operation on a condition variable allows a thread executing in a monitor (which implies it must be holding the same lock that the waiting thread was holding when it called cv_wait) to notify a waiting thread that the thing it was waiting for has happened. The cv_signal() function should wake up exactly one thread waiting on the address "cv". If no threads are waiting, then a cv_signal() has no effect. A read of the thread_wakeup() function (used by the semaphore V() code) shows that it does not have the desired behavior for condition variable signals. You will need to implement a new function that does what you want.
The cv_broadcast operation is identical to signal, except that it should wake up all threads waiting on the cv.
Run the "sy3" test from the OS/161 menu. The thread numbers will print out in reverse order, several times, if everything is correct.
For reference, my implementations of the condition variable functions (not counting assert() statements, disabling/restoring interrupts, or the new thread_wakeone function) are less than 10 lines of code.