Re: Deadlock resolution

["Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de>]

On Wed, 28 Jul 2004 14:53:02 +0100, Nick Roberts wrote:

> My current design for the AdaOS kernel is as follows. The kernel
> counts the time that each thread (task) is blocked waiting for
> another thread (in the same workstation). If the count reaches a
> certain threshold (possibly about 10 minutes) for a thread, the
> kernel performs a traceback on the chain of threads it is waiting
> on; this chain breaks if any thread in it is waiting on I/O or a
> timer. If the chain doesn't break before the original thread is
> reached again, deadlock is detected.

Don't you have any protected objects a task might wait for? (except for
timer and I/O events, you have mentioned) So the only synchronization
mechanism is rendezvous with tasks?

> The current 'resolution' strategy is to select the youngest (most
> recently created) thread in the chain, and kill it (it gets a
> special Deadlock exception).

How does it differ from timed entry call from the perspective of the task
being killed? Except for waiting for a timer, I don't see much difference.
If so, then one can just claim that all calls are time bounded (say by 10
minutes).

> There are at least two weaknesses with this approach: (a) it takes
> at least 10 minutes (or whatever) to detect a deadlock; (b) any
> chain of deadlock that goes outside the workstation at all will
> not be detected by this mechanism.
> 
> I think (a) is unlikely to be a serious problem, in practice.
> 
> However, since AdaOS will be a fully distributed OS, (b) is very
> likely to happen, in practice. I believe that the kernel canot be
> expected to manage deadlocks in these cases, because it would be
> impractical to implement a mechanism that could be guaranteed
> immune to false intervention (to act only in cases of a genuine
> deadlock).

Theoretically you could navigate the chain of tasks across the whole
network... (:-))

> I therefore believe that super-kernel software which might be in
> communication with software executing on another workstation
> (and in AdaOS, that means most software) must be programmed to
> either: (1) eliminate (within reason) the possibility of
> deadlock; (2) detect and resolve potential deadlocks. I think
> (1) will be impractical in the majority of AdaOS programs.
> 
> When considering the likely AdaOS (actually CORBA) scenario of
> a menagerie of programs interacting in potentially deadlocking
> ways, I think considerations of deadlock management gain in
> importance. So, I'm pondering about the subject as it impacts
> the design of the AdaOS kernel (which is called 'Bachar').

It would be interesting to speculate whether some kind of profile (like
Ravenscar) plus a richer set of protected object operations could eliminate
deadlocks being enough powerful for an universal OS. For example, famous
philosophers wouldn't deadlock if two protected objects (forks) could share
one protected action. Just a guess.

-- 
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de