Date: Fri, 06 Feb 2004 16:51:59 -0500 From: Aniruddha Bohra <bohra@cs.rutgers.edu> To: John Baldwin <jhb@FreeBSD.org> Cc: freebsd-current@freebsd.org Subject: Re: three locks and lock order reversal? Message-ID: <40240C7F.9040106@cs.rutgers.edu> In-Reply-To: <200402061349.43213.jhb@FreeBSD.org> References: <20040206020616.12702.qmail@web60606.mail.yahoo.com> <200402061349.43213.jhb@FreeBSD.org>
next in thread | previous in thread | raw e-mail | index | archive | help
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@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
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?40240C7F.9040106>