From owner-freebsd-arch Thu May 18 16:40:35 2000 Delivered-To: freebsd-arch@freebsd.org Received: from smtp05.primenet.com (smtp05.primenet.com [206.165.6.135]) by hub.freebsd.org (Postfix) with ESMTP id 3C08737BDF5 for ; Thu, 18 May 2000 16:40:27 -0700 (PDT) (envelope-from tlambert@usr06.primenet.com) Received: (from daemon@localhost) by smtp05.primenet.com (8.9.3/8.9.3) id QAA05722; Thu, 18 May 2000 16:40:33 -0700 (MST) Received: from usr06.primenet.com(206.165.6.206) via SMTP by smtp05.primenet.com, id smtpdAAALRaGil; Thu May 18 16:40:27 2000 Received: (from tlambert@localhost) by usr06.primenet.com (8.8.5/8.8.5) id QAA11883; Thu, 18 May 2000 16:40:18 -0700 (MST) From: Terry Lambert Message-Id: <200005182340.QAA11883@usr06.primenet.com> Subject: Re: A new api for asynchronous task execution To: cp@bsdi.com (Chuck Paterson) Date: Thu, 18 May 2000 23:40:17 +0000 (GMT) Cc: wes@softweyr.com (Wes Peters), dfr@nlsystems.com (Doug Rabson), arch@FreeBSD.ORG In-Reply-To: <200005181557.JAA05148@berserker.bsdi.com> from "Chuck Paterson" at May 18, 2000 09:57:19 AM X-Mailer: ELM [version 2.5 PL2] MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit Sender: owner-freebsd-arch@FreeBSD.ORG Precedence: bulk X-Loop: FreeBSD.ORG > }Wouldn't it make more sense to provide an inversion-proof semaphore? > }Or is that what they're doing? > > Not quite sure what you mean. The lock checking done > now is to detect without actually having to have the deadlock > occur the following > > thread 1 acquires lock "a" and then tries to acquire lock "b" > thread 2 acquires lock "b" and then tries to acquire lock "a" > > > There isn't really any automagic fix for this. Djikstra would disagree; this is the classic form for something to which he would apply his "banker's algorithm" and pre reserve both "a" and "b" for thread 1, before it ever became an issue. Deadlock avoidance is thus one way to deal with the problem. There are better soloutions that permit resource risk, however, but they require that you be able to back completely out of a partial transaction, and retry the whole thing, e.g. continuing: thread 2 gets EWOULDBLOCK thread 2 gifts lock "b" to thread 1 thread 2 sleeps _first in line_ to reacquire lock "b" thread 1 acquires lock "a" thread 1 completes thread 1 releases lock "b" thread 2 acquires lock "b" thread 2 attempts to acquire lock "a" ... > If you are talking about running processes in > order based on scheduling priority, this is propagated > though mutexs which have been blocked on. Resource priority (as shown above, when thread 2 gets to be first in line as a reward for not continuing to hold lock "b" when it was needed by thread 1) is a better model, since it avoids the "deadly embrace" deadlock. If we are talking RT priority, then there is always the resource preemption model; this also requires special coding and design practices, e.g.: A: thread 2 is higher priority thread 2 preempts lock "a" from the clutches of thread 1 thread 2 completes thread 2 does not free, but returns lock "a" to thread 1 B: thread 1 is higher priority thread 1 preempts lock "b" from the clutches of thread 2 thread 1 completes thread 1 does not free, but returns lock "b" to thread 2 There are better graphical soloutions which woild allow concurrent access; SIX locking is required to be able to implement these, and increases complexity, but the increase in concurrency is generally worth the effort. Terry Lambert terry@lambert.org --- Any opinions in this posting are my own and not those of my present or previous employers. To Unsubscribe: send mail to majordomo@FreeBSD.org with "unsubscribe freebsd-arch" in the body of the message