From owner-freebsd-current@FreeBSD.ORG Fri Feb 6 14:45:12 2004 Return-Path: Delivered-To: freebsd-current@freebsd.org Received: from mx1.FreeBSD.org (mx1.freebsd.org [216.136.204.125]) by hub.freebsd.org (Postfix) with ESMTP id 6110C16A4CE; Fri, 6 Feb 2004 14:45:12 -0800 (PST) Received: from dragon.rutgers.edu (dragon.rutgers.edu [128.6.25.118]) by mx1.FreeBSD.org (Postfix) with ESMTP id 91B9843D31; Fri, 6 Feb 2004 14:45:08 -0800 (PST) (envelope-from bohra@cs.rutgers.edu) Received: by dragon.rutgers.edu (CommuniGate Pro PIPE 4.1) with PIPE id 11587199; Fri, 06 Feb 2004 17:45:06 -0500 X-Spam-Status-LCSR: dragon spam scanned Received: from [128.6.171.146] (account bohra HELO cs.rutgers.edu) by dragon.rutgers.edu (CommuniGate Pro SMTP 4.1) with ESMTP id 11586182; Fri, 06 Feb 2004 16:53:33 -0500 Message-ID: <40240C7F.9040106@cs.rutgers.edu> Date: Fri, 06 Feb 2004 16:51:59 -0500 From: Aniruddha Bohra User-Agent: Mozilla/5.0 (X11; U; FreeBSD i386; en-US; rv:1.5) Gecko/20031024 X-Accept-Language: en-us, en MIME-Version: 1.0 To: John Baldwin References: <20040206020616.12702.qmail@web60606.mail.yahoo.com> <200402061349.43213.jhb@FreeBSD.org> In-Reply-To: <200402061349.43213.jhb@FreeBSD.org> Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit X-Spam-Checker-Version: SpamAssassin 2.61 (1.212.2.1-2003-12-09-exp) on spamfilter.rutgers.edu X-Spam-Level: X-Spam-Status: No, hits=-4.9 required=5.0 tests=BAYES_00 autolearn=ham version=2.61 cc: popsong old cc: freebsd-current@freebsd.org Subject: Re: three locks and lock order reversal? X-BeenThere: freebsd-current@freebsd.org X-Mailman-Version: 2.1.1 Precedence: list List-Id: Discussions about the use of FreeBSD-current List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Fri, 06 Feb 2004 22:45:12 -0000 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 <>< 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