Confused over locking, waiting, pulsing etc

Question

I understand the basics of threading and how a deadlock occurs. I understand that you want to take out locks in a specific order to help ensure you don't get yourself into a circular firing squad.

What my brain is having trouble with is how that order is guaranteed and exactly how wait and pulse (pulseall) assist.

Don't answer with a link to skeet's article on multithreading as that is where I am coming from. I also googled So and came up with this post.

In Jon's tutorial the methods Produce() and Consume both lock on listlock and I don't see how an order is maintained. Regardless of order one beats the other to the punch so how can the other get a lock? It doesn't right...so the last thread to attempt lock sits there blocking until the first gets to the pulse or the wait depending?

So being unsure I looked for other articles and in the SO article above I took to gatopeich answer with a boss, a worker, and the locked object the phone.

The worker locks the phone while at work. When he has the lock (while)true) he unlocks??? the phone with the monitor.wait statement....???

Meantime the boss locks the phone...but wait how can he the employee got to work on time and locked the phone before the boss got there....?

Jon points out that if you don't understand this you'll think it is going to deadlock which is exactly where I am at:

Just to repeat: calling Wait unlocks the monitor you're waiting on. This is an important point, because otherwise the code looks like it'll just deadlock!

So I am sorry for being so dense and seeing this as a chicken or the egg scenario. Clearly there must be something I am not understanding of how the threads interact when specifying the order of obtaining locks to avoid a deadlock.

Thank You for your help and patience.

Answer 1

There is no guaranteed order of who gets the lock. You don't need that to determine a deadlock. There are four conditions that, when all active, contribute to a deadlock.

1. Mutual Exclusion: There must be two resources that can't be shared (so you'll have to lock).

2. Hold and Wait: A process is locking one resource and requesting a lock for another.

3. No preemption: The OS cannot steal the lock from the processes that hold them (by restarting the processes, etc..)

4. Circular Wait: Thread A is locking C while waiting for D and Thread B is locking D while waiting for C.

If any of these conditions is not true, you cannot have deadlock. Yes, I mostly took this from Wikipedia.

There are not two resources in Jon's example. There is only one lock. There is no holding and waiting because there is not a second lock to attempt to lock. The third condition does hold I believe in Windows though. And circular wait cannot be upheld because there are not two locks. Therefore, there can't be a deadlock. Conditions 1, 2, and 4 don't hold. Yeah, the consumer could just start up an infinite loop and it would "deadlock", but nobody is going to do that.

Jon's example spawns only one consumer. Then every second or so (he randomized it so it's not always a second) the producer attempts to take the lock. Also every second or so the consumer attempts to take a lock. These two times are completely unrelated. They are on different threads with different random number generators with different seeds. You cannot graph a consistent relationship between them over multiple runs (eh, maybe you can because the seeds don't change).

When consume tries to take the lock, it checks if there is anything to be consumed. If there's not, it just waits (at which time it is not restarting the consuming process every second). This releases the lock and allows the producer to take it. So either it gets an object or it waits.

When the producer tries to take the lock, it blocks until no consumers hold the lock (and all consumers will quickly clear the way for the producer to take the lock if there's nothing to be consumed, so it will easily take the lock once everything is consumed). Then it gets the lock, puts an object in the queue, and wakes up the waiting consumer.

This continues indefinitely (or 10 times in Jon's case). Finite amount of consumers come in, leave when there's nothing in the queue (by waiting). Producer comes in when all consumers are waiting and puts an object in the queue. Then producer wakes up the consumer and blocks (by calling pulse). Then everything starts over.

Short answer: Why pulse and wait?

1. Pulse lets the consumer take over the lock and then the thread sleeps for long enough that the consumer gets the lock.
2. Wait, which is called by all consumers (1 in this case), releases the lock and blocks until the producer pulses, which will happen often in Jon's case.

The consumer thread is not selfish. If it can't do anything, it lets the producer thread play with the ball. Then the producer thread only plays with the ball long enough to put a sticker on it that it wants to show the consumer. It yells over to the consumer and says "hey check out this sticker", then runs away from the ball so the consumer can take a look and rip the sticker off the ball. Rinse and repeat (the ball may have germs on it now ;)).