Time and time again I find myself having to explain why people shouldn’t take a gung-ho approach to locking, or, more often, what a deadlock is. Simple explanations being the best, the following is the stock answer I came up with for these situations.
The first parable of the bathroom
Imagine a typical office, with two office workers. We’ll call these people Mr. A and Mr B.
Mr. A spills some coffee, and wants to wipe it up. He goes to the bathroom, grabs the toilet roll, and starts mopping up the spill.
While Mr. A is busy, Mr. B goes to answer the call of nature, and goes into the bathroom. Mr. B obviously likes his privacy, so he locks the bathroom door so that no one can enter while he’s using it.
Now, both A and B are stuck. When A finishes mopping up the coffee, he cannot replace the toilet roll because B has locked the door. On the other hand, B cannot finish before he uses the toilet roll, which he cannot do because the toilet roll simply isn’t in the room.
This is a typical deadlock situation – two workers are waiting for each other to finish, which will never happen because their end conditions are interdependent.
The second (unimproved) parable of the bathroom
Now, some forms of locking provided by .Net allow the developer to specify a timeout. This tells the worker to give up if it is unable to acquire a lock within the given time. In our example, this would looks something like this:
A goes into the bathroom. (A locks the bathroom)
A gets the toilet roll (A locks the toilet roll)
A leaves the bathroom (A releases the bathroom)
B enters the bathroom (B locks the bathroom)
B tries to get hold of the toilet roll (B tries to lock the toilet roll)
Of course, the lock on the toilet roll is still held by A, so B will give up trying to get the lock. Depending on how B is coded, it will either fail with an exception, or simply go ahead, unlock the bathroom, and continue working. Both situations are undesirable; in the first case, it means that B is not doing the work it was meant to do. In the second case, B continues working in a possibly inappropriate state (It left the bathroom without using the toilet roll).
Timeouts on locks are, in general, a BAD idea; so much in fact that the recommended locking syntax in C#, the lock statement, does not even give you an option to specify one.
The third (possibly improved, possibly not) parable of the bathroom
This still leaves us with a deadlock though. One way to get past it is to lock more aggressively, which may not be the ideal solution in most cases. It certainly works, but the chances are that it’s going to put the hurt on performance.
A more aggressive lock would be something like this:
A goes into the bathroom (A locks the bathroom)
A gets the toilet roll (A locks the toilet roll)
A leaves the bathroom, but keeps the key (A is still holding the lock to the bathroom)
B tries to get into the bathroom, and starts waiting for A to unlock it.
A returns the toilet roll. (A releases the toilet roll)
A returns the key to the bathroom. (A releases the bathroom)
B finishes waiting and goes about its business.
In this case, we are considering that to finish a given task (returning the toilet roll), A depends on the availability of the bathroom; to make sure this is available when needed, we lock the bathroom for the duration of the task, so a deadlock situation never arises – if A has the toilet roll, it also has exclusive access to the bathroom.
While this works, it is important to remember that locks should really be considered on a case by case basis. For example, while an aggressive lock as above may be acceptable if A has a brief task, it would not have been acceptable if the task had required a certain amount of time. Sometimes a reorganization of the code or the resources may be in order – again in the example above, it may not have been necessary to take out the entire toilet roll; perhaps taking a small part of it would have been enough.
Moral of the story
Handle locks with care, or you’ll end up in crap up to your eyeballs.
Brilliant stuff dude… never saw a post so easy to read and understand
Glad you liked it 🙂 Thanks Marlon.
B should have checked for paper availability before locking the door, after all we should’t make asumptions aboout resources in a public (shared) domain, which brings the the question into mind :
Should we lock before we get a hold on every needed resource or not?
and also:
some sorth of thread owned reference would be usefull, for example if a thead reads a reference all other theads tying to read it should get a null back until the first thread writes it back or block on the read until it becomes available.
and also #2 :
some sorth of wait mechanism that waits on multiple resources would be nice like B.WaitFor(bathroom, paper) in wich case a B is blocked untill all resources are available but say C waiting for bathrom only might not be blocked if it doesn’t need the paper.
Hi Cata, thanks for your observations 🙂 Your point about not making assumptions on public resources is eminently correct.
With regards to the thread owned reference, I’m not 100% certain I like the sound of that. A null may be a valid value in some circumstances; also I believe forcing the thread to wait for a lock would be cleaner than returning a “hang on, this thing is being used by someone else” value and allowing the caller to handle it as it wants to.
I agree with your second point; it makes a lot of sense in most circumstances, especially if you consider the code protected by the lock to be atomic. Then again, one would also need to see if you can afford the resources to be locked from the beginning, if you can still run some stuff while waiting for the rest of the resources to become available, and so on.
A little technique called lock-leveling [1] would have avoided this deadlock.
[1] http://msdn2.microsoft.com/en-us/magazine/cc163618.aspx#S3
Hi Peter, thanks for the reference.
As such, yes, the deadlock described can be avoided fairly easily with a number of techniques. The purpose of this post isn’t to show how to beat a deadlock, but to demonstrate how something that is apparently simple can blow up in one’s face.
The final solution is always to be very careful when designing the code, whatever technique is used. That said, thanks again for the reference; more options to play with 😀
4. A only locks the stall door, leaving the urinal available (lock granularity)
Also, Cata is spot on. B, holding a lock on the bathroom door, should further lock the toilet paper roll before committing to an action which will require it.
Hi mind,
Locking the stall door assumes there is a stall to lock, which is not implied in the example. However, what you suggest is a good example of reorganizing code and resources to reduce chances of a deadlock. We’d also be assuming that B only needs the urinal though, which may or may not be the case 😀
Regarding your second statement, B holding a lock on the door before the roll is available is what causes the deadlock in the first place, since A cannot release the roll without entering the bathroom.
Awesome… and not nearly as disgusting as I thought it might be 🙂
😀 Yes, it could have been, couldn’t it? 😀
Thanks Sam.
Great job dude,
It’s a good idea to use a lock because I can’t imagine A and B using the toilet paper at the same time 🙂
You might say if B timed out waiting for the lock on the toilet paper, B would be left in an ‘unclean state’.
Toilet humour is the cheapest kind.
AW: Very well put indeed 😀
Raffaele: Hi, really glad you liked it 🙂
Its really a well organized simple example to have a grip on locking concept. Thankx for this stuff man.