Re: three locks and lock order reversal?

From: John Baldwin <jhb_at_FreeBSD.org>
Date: Fri, 6 Feb 2004 13:49:43 -0500
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.

-- 
John Baldwin <jhb_at_FreeBSD.org>  <><  http://www.FreeBSD.org/~jhb/
"Power Users Use the Power to Serve"  =  http://www.FreeBSD.org
Received on Fri Feb 06 2004 - 10:26:03 UTC

This archive was generated by hypermail 2.4.0 : Wed May 19 2021 - 11:37:42 UTC