Re: How to programmatically avoid deadlock?
- From: David Hopwood <david.nospam.hopwood@xxxxxxxxxxxxxxxx>
- Date: Fri, 30 Jun 2006 15:12:06 GMT
Vladimir Frolov wrote:
David Hopwood wrote:
In an event-loop model, threads never hold onto a resource *while* waiting
for another. In the case you describe, the thread will be guaranteed to
have released the 'one' resource (even if it subsequently reacquires it)
before the wait for the 'other' resource is resolved. It is not important
whether waits are cancellable.
You broke condition of undistributed resources here. It means that the
most part of work with resource 'one' can be lost while waiting
resource 'two' because all other threads will have write access to
'one'.
This is not a problem in practice.
In any concurrent system, it is essentially always a design error to depend
on acquiring exclusive, uninterruptible access to a resource for a potentially
unbounded length of time.
The important thing is to make the points at which a resource might be
affected by other threads explicit. This is what makes it feasible to
implement an extended operation (one that takes place over several
turns, in the case of E) with confidence that it always has the intended
effect, even though it can be interrupted.
Note that large changes to the state of a program can be effected atomically
by adopting a mostly-functional style: instead of making incremental changes
to a data structure, we can snapshot it and make changes to the copy, then
atomically replace the root of the structure.
[In the event-loop model used by E and described in the thesis [*], this
property is ensured by assigning each object (resource) to a "vat", and
splitting computation in a vat into "turns" which occur in response to
asynchronous messages, so that a turn has synchronous access to all the
objects in the vat. Each turn should be short, so that the vat remains
responsive to external messages. However, note that this is only one
possibility that guarantees deadlock-freedom. The *reason* for E's model
being deadlock-free is essentially just that there are no blocking
synchronization constructs, and generalizations of the model are possible
without losing deadlock-freedom.]
You broke condition of waiting here. Each "turn" will hold whole "vat"
so that you lose ability to hold some vat, made a part of work on it
and then decide which other vat has to be held also. Then make some
other part of work with both vats while first vat is inaccessible by
any other event-loop thread.
Designs that require simultaneous exclusive access to objects in more
than one vat are not directly expressible in this model. This is a
deliberate decision in order to make reasoning about the concurrent
behaviour of programs more tractable.
The assignment of objects to vats has to be done in such a way that
objects that need to be simultaneously accessed exclusively will be in
the same vat. This is rarely difficult.
(Note that, although an object cannot literally migrate between vats,
an effect that is almost identical for most purposes can be achieved by
changing an object's behaviour to forward messages to a new copy of the
object in another vat. If this technique is used, then the assignment of
'logical' objects to vats does not need to be fixed at the object's
creation. This is probably not the simplest way to translate a design
which would have used locking of multiple objects in a shared-state
model, but it demonstrates that there is no fundamental loss of
expressiveness.)
BTW: Stress-flow methodology (see http://www.stressflow.com/) designed
as universal, versatile parallel programming technique helps me to
understand that deadlock situation is fully natural, so that it is not
so easy to build generic technique which will be oriented to escape
deadlocks or analyze where deadlock may happens, at least such a
technique has to be artificial (not natural).
I don't know why you would assume that because Stress-flow cannot
eliminate the possibility of deadlock, it is not possible for other
models (that are also universal) to do so.
Stress-flow program
doesn't operate on threads or synchronization primitives manually; it
is operate on stress-flow atoms, but even in this case stress-flow atom
can be deadlocked if all four conditions hold true.
In this case I'd prefer tool for static code analysis or application
profiler to find deadlocks instead of technique to escape it but with
strong drawbacks. So stress-flow is good enough on this point.
You don't have sufficient experience with event-loop concurrency to be
asserting that it has "strong drawbacks".
--
David Hopwood <david.nospam.hopwood@xxxxxxxxxxxxxxxx>
.
- References:
- How to programmatically avoid deadlock?
- From: youpak2000
- Re: How to programmatically avoid deadlock?
- From: Vladimir Frolov
- Re: How to programmatically avoid deadlock?
- From: David Hopwood
- Re: How to programmatically avoid deadlock?
- From: Vladimir Frolov
- Re: How to programmatically avoid deadlock?
- From: David Hopwood
- Re: How to programmatically avoid deadlock?
- From: Vladimir Frolov
- How to programmatically avoid deadlock?
- Prev by Date: Re: How to programmatically avoid deadlock?
- Next by Date: Problems with output in a file
- Previous by thread: Re: How to programmatically avoid deadlock?
- Next by thread: Re: How to programmatically avoid deadlock?
- Index(es):
Relevant Pages
|
