Skip site navigation (1)Skip section navigation (2)
Date:      Thu, 18 May 2000 23:40:17 +0000 (GMT)
From:      Terry Lambert <tlambert@primenet.com>
To:        cp@bsdi.com (Chuck Paterson)
Cc:        wes@softweyr.com (Wes Peters), dfr@nlsystems.com (Doug Rabson), arch@FreeBSD.ORG
Subject:   Re: A new api for asynchronous task execution
Message-ID:  <200005182340.QAA11883@usr06.primenet.com>
In-Reply-To: <200005181557.JAA05148@berserker.bsdi.com> from "Chuck Paterson" at May 18, 2000 09:57:19 AM

next in thread | previous in thread | raw e-mail | index | archive | help
> }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




Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?200005182340.QAA11883>