Jon's article on threading: Waiting and Pulsing

[Bruce Wood]

Maybe it's just late in my day, but I'm reading Jon's article on
threading, in particular how to use Monitor.Wait() and Monitor.Pulse(),
and there's something that's not sinking in. The code in question
looks like this:

public class ProducerConsumer
{
readonly object listLock = new object();
Queue queue = new Queue();

public void Produce(object o)
{
lock (listLock)
{
queue.Enqueue(o);
if (queue.Count==1)
{
Monitor.Pulse(listLock);
}
}
}

public object Consume()
{
lock (listLock)
{
while (queue.Count==0)
{
Monitor.Wait(listLock);
}
return queue.Dequeue();
}
}
}

What I don't understand is why the code in the Consume() method is
enclosed in a lock (listLock)? Won't this create a deadlock? I.e.:
Consume acquires a lock on listLock, then calls Monitor.Wait to wait
for a pulse. Produce() then attempts to produce something, but gets
stuck waiting on its "lock (listLock)" test, waiting for Consume() to
release its lock on listLock, which, of course, it will never do,
because it's waiting for Produce() to pulse it.

I know that Jon runs tests his own code so I know that this works,
but I can't see how it could work.

Could someone please explain?

 

[Michael S]

Maybe it's just late in my day, but I'm reading Jon's article on
threading, in particular how to use Monitor.Wait() and Monitor.Pulse(),
and there's something that's not sinking in. The code in question
looks like this:

public class ProducerConsumer
{
readonly object listLock = new object();
Queue queue = new Queue();

public void Produce(object o)
{
lock (listLock)
{
queue.Enqueue(o);
if (queue.Count==1)
{
Monitor.Pulse(listLock);
}
}
}

public object Consume()
{
lock (listLock)
{
while (queue.Count==0)
{
Monitor.Wait(listLock);
}
return queue.Dequeue();
}
}
}

What I don't understand is why the code in the Consume() method is
enclosed in a lock (listLock)? Won't this create a deadlock? I.e.:
Consume acquires a lock on listLock, then calls Monitor.Wait to wait
for a pulse. Produce() then attempts to produce something, but gets
stuck waiting on its "lock (listLock)" test, waiting for Consume() to
release its lock on listLock, which, of course, it will never do,
because it's waiting for Produce() to pulse it.

I know that Jon runs tests his own code so I know that this works,
but I can't see how it could work.

Could someone please explain?

Yes.

This is why Jon have made such an effort in writing on 'padlocks' or a
listLock in this case..
As he has a readonly listLock, it is (somewhat) static and will lock (and
queue) any thread that tries to call any methods.

Or so I understand it... What am I missing?

Oh, You got a mail somewhere in your spam...

- Michael S

 

[Brian Gideon]

Bruce,

Monitor.Wait will release the lock before it blocks. It will reacquire
the lock before returning to the caller. The lock is not held during
the time the thread is waiting.

Though I have since learned, I had a much more difficult time
understanding the need for the while loop. Can everybody see it?

Brian

 

[Bruce Wood]

Umm... no. But lack of understanding holds me up in only a few cases.

 

[Mike Schilling]

Bruce,

Monitor.Wait will release the lock before it blocks. It will reacquire
the lock before returning to the caller. The lock is not held during
the time the thread is waiting.

And, in fact, it's illegal to do a wait when you don't already hold the
lock.

Though I have since learned, I had a much more difficult time
understanding the need for the while loop. Can everybody see it?

Suppose there are multiple consumers, all waiting on the lock. If more than
one is awakened, it's possible that some will find the queue empty by the
time they check it, and need to wait some more.

 

[William Stacey [MVP]]

In Consume, Monitor.Wait() releases the lock and waits to be pulsed. As
multiple consumer threads could be waiting and Pulsed or woke up, you need
the while loop as one thread may get the last item and the others that run
inturn will need to check Count again so they don't try the Dequeue on an
empty queue. On the Produce side, there is a "live lock" issue. The
monitor never gets pulsed unless count is 1, so if count gets greater then
1 - no consumers will ever get pulsed (i.e. live-locked). A safer solution
is to use PulseAll() if Count > 0. For full blocking queue patter, check
out my blocking one-lock queue on the codeproject at
http://www.codeproject.com/csharp/boundedblockingqueue.asp

--
William Stacey [MVP]

| Maybe it's just late in my day, but I'm reading Jon's article on
| threading, in particular how to use Monitor.Wait() and Monitor.Pulse(),
| and there's something that's not sinking in. The code in question
| looks like this:
|
| public class ProducerConsumer
| {
| readonly object listLock = new object();
| Queue queue = new Queue();
|
| public void Produce(object o)
| {
| lock (listLock)
| {
| queue.Enqueue(o);
| if (queue.Count==1)
| {
| Monitor.Pulse(listLock);
| }
| }
| }
|
| public object Consume()
| {
| lock (listLock)
| {
| while (queue.Count==0)
| {
| Monitor.Wait(listLock);
| }
| return queue.Dequeue();
| }
| }
| }
|
| What I don't understand is why the code in the Consume() method is
| enclosed in a lock (listLock)? Won't this create a deadlock? I.e.:
| Consume acquires a lock on listLock, then calls Monitor.Wait to wait
| for a pulse. Produce() then attempts to produce something, but gets
| stuck waiting on its "lock (listLock)" test, waiting for Consume() to
| release its lock on listLock, which, of course, it will never do,
| because it's waiting for Produce() to pulse it.
|
| I know that Jon runs tests his own code so I know that this works,
| but I can't see how it could work.
|
| Could someone please explain?
|

 

[Bruce Wood]

On the Produce side, there is a "live lock" issue. The monitor never gets pulsed unless count is 1, so if count gets greater then 1 - no consumers will ever get pulsed (i.e. live-locked).

I believe that Jon's solution assumes only one consumer (correct me if
I'm wrong). I also believe that pulsing only if count is 1 is an
efficiency measure: it doesn't bother pulsing the other thread if the
other thread is already running. That test could be omitted and the
model would still work; it would just wake up the consumer sometimes
when there was nothing to consume, which would result in the consumer
waiting again. Am I right?

 

[William Stacey [MVP]]

For this simple example that is true. Ideally, you want it work for
multiple consumers and producers coming in any order. For example, you
produce 1 item and a consumer does some work and does not come back. Mean
while, other consumers came in and blocked on Wait. Then your producer
inserts 20 items. Once consumer gets free and goes away, but all other
waiting consumers are locked waiting for a pulse that will never come until
another consumer comes in and drains the queue and another producer comes in
after that to do a Pulse. Under certain weird conditions, you can end up
with blocked consumers and items still left in the queue. Or consumers that
really could be running doing useful work, but are blocked.

--
William Stacey [MVP]

|> On the Produce side, there is a "live lock" issue. The monitor never
gets pulsed unless count is 1, so if count gets greater then 1 - no
consumers will ever get pulsed (i.e. live-locked).
|
| I believe that Jon's solution assumes only one consumer (correct me if
| I'm wrong). I also believe that pulsing only if count is 1 is an
| efficiency measure: it doesn't bother pulsing the other thread if the
| other thread is already running. That test could be omitted and the
| model would still work; it would just wake up the consumer sometimes
| when there was nothing to consume, which would result in the consumer
| waiting again. Am I right?
|

 

[Jon Skeet [C# MVP]]

I believe that Jon's solution assumes only one consumer (correct me if
I'm wrong).

No, it can cope with multiple consumers with no change.

I also believe that pulsing only if count is 1 is an
efficiency measure: it doesn't bother pulsing the other thread if the
other thread is already running. That test could be omitted and the
model would still work; it would just wake up the consumer sometimes
when there was nothing to consume, which would result in the consumer
waiting again. Am I right?

I'll have to look closely to check. It could even be that it's
currently a bug. If two threads are waiting, one is woken up (but
doesn't run yet) and then a second item is added, that second item
addition *should* wake up the second thread. Oops.

I clearly need to work on this section a bit more - if only because if
it's not sufficiently obvious that calling Wait releases the lock, then
the article isn't doing its job. (It is mentioned, but not
highlighted.)

I'll see what I can do tonight...

 

[Jon Skeet [C# MVP]]

For this simple example that is true. Ideally, you want it work for
multiple consumers and producers coming in any order. For example, you
produce 1 item and a consumer does some work and does not come back. Mean
while, other consumers came in and blocked on Wait. Then your producer
inserts 20 items. Once consumer gets free and goes away, but all other
waiting consumers are locked waiting for a pulse that will never come until
another consumer comes in and drains the queue and another producer comes in
after that to do a Pulse. Under certain weird conditions, you can end up
with blocked consumers and items still left in the queue. Or consumers that
really could be running doing useful work, but are blocked.

Yes - thinking about it further, I'm pretty sure it is a bug. I'll fix
it tonight - or earlier if I can.

Bad Jon!

 

[Jon Skeet [C# MVP]]

In Consume, Monitor.Wait() releases the lock and waits to be pulsed. As
multiple consumer threads could be waiting and Pulsed or woke up, you need
the while loop as one thread may get the last item and the others that run
inturn will need to check Count again so they don't try the Dequeue on an
empty queue. On the Produce side, there is a "live lock" issue. The
monitor never gets pulsed unless count is 1, so if count gets greater then
1 - no consumers will ever get pulsed (i.e. live-locked). A safer solution
is to use PulseAll() if Count > 0. For full blocking queue patter, check
out my blocking one-lock queue on the codeproject at
http://www.codeproject.com/csharp/boundedblockingqueue.asp

I don't think there's any need to call PulseAll() - there's no
advantage to waking up multiple threads as far as I can see.

However, I've removed the rest of the bug, as it were - I *always* call
Pulse() now. I've added comments within the code and emphasised that
calling Wait() releases the lock.

If anyone fancies casting their eyes over the new version, I'd
appreciate it. Same URL as before:
http://www.pobox.com/~skeet/csharp/threads/deadlocks.shtml

Jon

 

[Brian Gideon]

Bad Jon!

I know how you feel. Everytime I think I have synchronization issues
figured out I get a big dose of reality.

Brian

 

[William Stacey [MVP]]

I'm with ya brother.

--
William Stacey [MVP]

|
| Jon wrote:
| >
| > Bad Jon!
| >
|
| I know how you feel. Everytime I think I have synchronization issues
| figured out I get a big dose of reality.
|
| Brian
|

 

[Jon Skeet [C# MVP]]

I know how you feel. Everytime I think I have synchronization issues
figured out I get a big dose of reality.

A. Maslow considers there to be four stages of learning:

<quote>
- Unconscious incompetence, where you are not aware that you don't
know much and
you don't mind
- Conscious incompetence, where you become aware of your lack of skills
and don't
enjoy it
- Conscious competence, where you are skillful but need to continue to
put conscious
effort into developing your skills
- Unconscious competence, where your skills work well without regular
reflection
</quote>

As far as I've seen in real life, the fourth stage is a myth when it
comes to multi-threading...

Jon

 

[Bruce Wood]

Thanks, Jon. That makes a lot more sense now.

 

[William Stacey [MVP]]

| I don't think there's any need to call PulseAll() - there's no
| advantage to waking up multiple threads as far as I can see.

Hi Jon. I guess it depends on what your trying to do with it. If your 4
consumer threads are monsters in your new game, you may want all 4 monsters
to start "monstering" instead of just one.

Also note, a PulseAll does not mean all blocks threads start, it means that
are moved to the Monitor's Ready queue and "can" be run. The OS scheduler
uses some smarts here. Threads in the ready queue are not gaureenteed to
run FIFO. If a thread could not obtain the monitor because the Monitor is
already held (which it has knowledge of) it may not release the thread or
pick a different one based on some rules I am not clear on. Also, the
monitor is held for a very short period, so the first ready queue thread
should be able to get in and do its dequeue within its' time slice and get
out - and the monitor should be free for the next thread in the ready queue
and so on. So the thread "hurding" issue should not be a major issue on
single cpu. On multi-cpu this gets more complicated to reason about.

Also, one also needs to reason about what the Queue should do with other
threads when SyncronizationException or ThreadInterruptedException occurs in
the Wait. Not sure there are a lot of great alternatives to this. Any
ideas? Cheers.
--wjs

 

[Jon Skeet [C# MVP]]

| I don't think there's any need to call PulseAll() - there's no
| advantage to waking up multiple threads as far as I can see.

Hi Jon. I guess it depends on what your trying to do with it. If your 4
consumer threads are monsters in your new game, you may want all 4 monsters
to start "monstering" instead of just one.

That's not the typical producer/consumer scenario, however - they can't
all consume the same job, after all. I deal with this a little bit at
the end of the article.

Also note, a PulseAll does not mean all blocks threads start, it means that
are moved to the Monitor's Ready queue and "can" be run.

Indeed.

The OS scheduler uses some smarts here. Threads in the ready queue
are not gaureenteed to run FIFO. If a thread could not obtain the
monitor because the Monitor is already held (which it has knowledge
of) it may not release the thread or pick a different one based on
some rules I am not clear on. Also, the monitor is held for a very
short period, so the first ready queue thread should be able to get
in and do its dequeue within its' time slice and get out - and the
monitor should be free for the next thread in the ready queue and so
on. So the thread "hurding" issue should not be a major issue on
single cpu. On multi-cpu this gets more complicated to reason about.

Well, even on a single CPU you've got potentially many threads to wake
up, reacquire the lock, check the queue, then go back to sleep. I don't
think there's any use in waking loads up when there's only one which
will be able to do any useful work.

Also, one also needs to reason about what the Queue should do with other
threads when SyncronizationException or ThreadInterruptedException occurs in
the Wait. Not sure there are a lot of great alternatives to this. Any
ideas? Cheers.

Not really, to be honest. There's even a nasty case where if a thread
is interrupted after it's been pulsed but before it's reacquired the
lock, you end up in the "lock" block without owning the lock

SynchronizationLockException shouldn't occur though, because by the
time we call wait we should *always* have the lock (due to the lock
block).