Condition Variables (HINT!)

[Oliver Steinmeier]

It seems that some teams still have problems with condition variables.
That's no big deal, though -- this message might help you find the
solution :-)

I got questions asking why the following solution will not work:

wait() {
numWaiters++; // count waiters
mutex->P(); // ensure mutual exclusion
lock->release(); // release lock
condition->P(); // wait for signal
mutex->V(); // allow next thread access
lock->acquire(); // reacquire lock
numWaiters--;
}

signal() {
if (numWaiters) condition->V();
}

(note that this is just C++-style pseudo-code... I just want you to
understand the idea -- it doesn't work anyway ;-) )

I explained in class that release of the lock and the waiting at the
semaphore require mutual exclusion. Well, the above solution does
ensure this through the additional semaphore mutex. The solution is
simple, obvious -- and unfortunately wrong. As I said in class, this
solution will easily cause a deadlock. Think about what happens if
one thread calls wait() and blocks at the condition->P() statement, and
if then another thread calls wait() for the same condition variable.
It will block at the mutex->P() statement, because it can't get access
to the critical section. At this time the second thread will still
hold the lock. And since the lock is needed in order to do a signal(),
these processes will never wake up...

Here is hint that might help you understand how to implement condition
variables:

Assume you are asked to implement the following two functions:

sleep()

A thread calls sleep() to block until it is woken up by some other
thread. This could be implemented by doing a P() on a semaphore
that is initialized with 0.

wakeup(tid)

A thread calls wakeup(tid) to wake up another thread that called
sleep before wakeup was called. The caller specifies the thread
to be woken up by giving the wakeup() function the thread ID tid
as a parameter. wakeup() should only wakeup the specified thread,
and it should do it in a simple an elegant fashion.

You may assume that there is a finite number of threads, say N, in
the system at the same time.

I don't ask you to really implement it. Just think about how you'd
do it. What data structures would you use? You'd probably let the thread
sleep on a semaphore. How do you make sure wakeup() wakes up the desired
thread?

Once you have the solution to this problem, it really isn't all that hard to
solve the actual condition variable problem. It is very similar, because
you have to wake up a certain thread when you do signal()...

Hope this helps.

Oliver