Monitor madness, part one

Locks are tricky; I thought today I'd talk a bit about some of the pitfalls of locking that you might not have seen before.

As you probably know, the lock statement in C# is a syntactic sugar for the use of a monitor, so I'll use the terms "lock" and "monitor" somewhat interchangeably. A monitor is an oddly-named data structure that gives you two basic operations: "enter" the monitor and "exit" the monitor. The fabulous thing about a monitor is that only one thread can enter a given monitor at a time; if threads alpha and beta both attempt to enter a monitor then only one wins the race; the other blocks at least until the winner exits. After the winner exits the monitor, the loser gets another chance to attempt to acquire the monitor; of course, there might be another race.

I give an example of a very very simple implementation of a monitor here, though of course you would never do this yourself; you'd just use the built-in support in the framework and the C# language.

The lock(x) { body } statement in C# is a syntactic sugar for

bool lockWasTaken = false;var temp = x;try { Monitor.Enter(temp, ref lockWasTaken); { body }}finally { if (lockWasTaken) Monitor.Exit(temp); }

The details of how the operating system implements (or fails to implement!) a system whereby every thread gets access eventually in some sort of fair manner is beyond the scope of what I want to talk about today. Rather, I want to talk about an advanced use of monitors. In addition to the straightforward "enter, do some work, exit" mechanism, monitors also provide a mechanism for temporarily exiting a monitor in the middle of a lock! That is, for the workflow:

• block until I enter the monitor
• do some work
• temporarily exit the monitor until something happens on another thread that I care about
• when the thing I care about happens, block until the monitor can be entered again
• do some work
• exit the monitor

Under what circumstances would we want to do this? The classic example is that we have a not-threadsafe finite-size queue of jobs to perform, and two threads called the producer and the consumer. The consumer thread sits there in a loop attempting to remove items from the queue so that the job can be performed. The producer thread runs around looking for work to do and puts it on the queue. Our code must have the following characteristics:

• if the consumer is attempting to modify the queue then an attempt by the producer to modify the queue must block
• and similarly vice versa
• if the producer is attempting to put work onto a full queue, it must block and allow the consumer to clear out space
• if the consumer is attempting to take work off of an empty queue, it must block and allow the producer to find more work

To achieve these goals, a monitor provides three operations in addition to enter and exit:

• "wait" causes the monitor to exit and puts the current thread to sleep. More specifically, it causes a thread to enter the "wait state".
• "notify" - which, oddly enough is called Pulse in .NET - allows the thread which is currently in the monitor to place a single waiting thread (of the runtime's choice) in the "ready" state. A ready thread is still blocked, but it is marked as ready to enter the monitor when the monitor becomes available. (There is no guarantee that it will do so; again, it might be racing against other threads.)
• "notify all" pulses every thread in the wait state that is waiting for a particular monitor.

Of course there are many other uses for these operations than producer-consumer queues, but as a canonical example we'll stick with that for the purposes of this series.

What does the code typically look like? On the producer we'd have something like:

while(true){ var someWork = FindSomeWork(); lock(myLock) { while (myQueue.IsFull) { Monitor.Wait(myLock); // We cannot do any work while the queue is full. // Put the producer thread into the wait state. // When someone pulses us, try to acquire the lock again, // and then check again to see if the queue is full. } // If we got here then we have acquired the lock, // and the queue has room. myQueue.Enqueue(someWork); // The queue might have been empty, and the consumer might be // waiting. If so, put the consumer thread in the ready state. Monitor.Pulse(myLock); // The consumer thread, if it was asleep, is now ready, but we // still own the lock. Let's leave the lock and give it a chance // to run. It might lose the race of course. }}

And on the consumer side we'd see something unsurprisingly similar. I won't labour the point with excessive comments here.

while(true) { Work someWork = null; lock(myLock) { while (myQueue.IsEmpty) Monitor.Wait(myLock); someWork = myQueue.Dequeue(); Monitor.Pulse(myLock); } DoWork(someWork);}

OK, I hope that is all very clear. This was a long introduction to what is a surprisingly not-straightforward question: why did I write a loop around each wait? Wouldn't the code be just as correct if written

 lock(myLock) { if (myQueue.IsEmpty) // no loop! Monitor.Wait(myLock); ...

Next time on FAIC: Yeah, what's up with that?