three locks and lock order reversal?

[Aniruddha Bohra]

John Baldwin wrote:
> On Thursday 05 February 2004 09:06 pm, popsong old wrote:
> 
>>>If one thread does A then B, another thread does B then C, and a third
>>>thread does C then A you can deadlock if each thread gets the first lock
>>>and blocks on the second lock.  Thread 1 wants B and holds A, thread 2
>>>holds B and wants C, and thread 3 wants A and holds C.  Thread 3 will not
>>>giveup C until it gets A.  Thread 1 holds A and won't give it up until it
>>>gets B.  Thread 2 holds B and won't give it up until it gets C which is
>>>held by thread 3. Hence, deadlock.
>>>
>>>--
>>>John Baldwin <jhb at FreeBSD.org>  <><  http://www.FreeBSD.org/~jhb/
>>>"Power Users Use the Power to Serve"  =  http://www.FreeBSD.org
>>
>>Thank you for the explanation! I only thought of two threads. So this bring
>>me another question: if the machine only have 2 CPUs, does it mean that
>>this kind of LOR is safe, provided there is no other sleep lock between A
>>and B, B and C, C and A?
> 
> 
> Default mutexes block instead of spin when they are contested, so you can have 
> a deadlock on a UP machine like so:
> 
> Thread 1 locks A and is preempted by an interrupt.  Thread 2 gets to run 
> before thread 1, locks B, and is preempted by an interrupt.  Thread 3 runs 
> next, locks C, and blocks on A.  It lends its priority to thread 1 which then 
> runs next and blocks on B.  Thread 2 then gets max(thread1, thread3)'s 
> priority and blocks on C.  Now you are deadlocked on a UP machine.
> 

This is a classical synchronization problem : the dining philosophers'
problem :

http://www.cs.mtu.edu/~shene/NSF-3/e-Book/MUTEX/TM-example-philos-1.html
http://en.wikipedia.org/wiki/Dining_philosophers_problem

Cheers
Aniruddha