|
|
Threads-Devel : |
From: Kai Brüning (kai_at_[hidden])
Date: 2007-07-24 03:23:51
>Content-Type: multipart/signed; boundary="nextPart16239633.UlmSsX5Ehn";
> protocol="application/pgp-signature"; micalg=pgp-sha1
>Content-Transfer-Encoding: 7bit
>
>On Monday 23 July 2007 03:22, Anthony Williams wrote:
>> I have code for a mutex that checks for deadlock at runtime --- every
>> thread that tries to lock a checked mutex registers that it is waiting
>> for that mutex, and then when the lock is acquired it flags the mutex to
>> identify the owning thread. When a thread registers that it is waiting
>> on a mutex, the chain is followed --- which thread currently owns the
>> mutex? Is it waiting on another mutex? and so forth, until we either
>> reach a thread that is not waiting (we're fine), or a thread that is
>> waiting on a mutex owned by the original thread (deadlock).
>
>That seems like a complementary idea. It doesn't detect deadlocks unless
>they actually occur, but can immediately produce information on exactly
>how the deadlock happened.
>
>> I also have an incomplete prototype of a "levelled" mutex --- each mutex
>> is assigned a level, and threads may only lock a mutex with a higher
>> level than any currently locked. This enforces an ordering on mutex
>> locks, which will therefore prevent deadlock. It is not something that
>> is usable in every situation, though.
>
>That would avoid the potentially large overhead of analyzing my directed
>graph for cycles. I wonder if there's a good way to dynamically assign
>levels to mutexes as they are added to the graph.
If I am not mistaken, dynamically assigning the levels changes the nature of this approach substantially.
With statically assigned levels, the programmer has to structure the locking needs of the code in levels based on his knowledge of program structure. While not bullet proof without 100% test coverage, I consider this idea a deadlock avoidance approach. I'd consider a level conflict more a bug than a normal runtime event - level checking might even be switched off in release mode.
With dynamically assigned levels I'd expect that any change in the flow of control can result in a level conflict somewhere. This makes it hard to be confident that testing eliminated all potential deadlocks, which makes this more a deadlock detection approach in my eyes. That is, code will have to be able to recover from a would-be deadlock situation, e.g. by throwing an exception.
On the other side, the dynamic approach will typically be less restrictive than statically assigned levels in the allowable flow of control scenarios.
Makes sense?
Kai