I can't comment on this much more without looking at the documents that
describe the computation methods or I can talk out of my a$$.  I'll try
the former. 

Please give us a pointer to the IBM Database Document.  While many
database system issues are fundamentally the same, it would be also
interesting to see a reference on using the methods in OS
systems/subsystems.  Are there any such documents?

Regards,


Mike

On Mon, 15 Jul 1996, Terry Lambert wrote:

> > > > Solaris kernel also has a debugging feature, it's called "deadman".
> > > > Every so often a timer based callout runs which runs down all the
> > > > mutex/semaphore/spinlock holder lists in the kernel and panics if any
> > > > circular and/or deadlock cases are found.
> > > 
> > > The IBM database design manual indicates several methods of fast
> > > computation of transitive closure over acyclic directed  graphs
> > > which make this kind of kludge unnecessary.  IMO, deadlock
> > > avoidance beats deadlock detection any day of the week.  Consider
> > > the issue of a two context deadly embrace for a resource: how do
> > > you unwind state so you don't lose already processed context?  In
> > > the deadlock detection case, the anser is "you probably don't".  Or
> > > you go to some overly complicated cruft, like the system call
> > > interrupt code in the trap, using a longjmp to unwind the stack.
> > 
> > How is this different from implementors carefully following a set of rules
> > in terms of performance?  Are there just too many permutations that it
> > just isn't reasonable to expect to be able to avoid deadlocks without
> > computing transitive closure across directed graphs?
> 
> IMO, the implementors should carefully follow a set of rules, in all
> cases.  This is simply a requirement if effective engineering.
> 
> The transitive closure computation should occur for several reasons,
> not just debugging and having a built-in failsafe.
> 
> The primary reason for computing transitive closure across the
> graph is to allow asynchronus entry of a lock cycle: you want this
> to increase concurrency, apart from any other reasons.
> 
> A nice secondary reason is to implement thread anonymity in the
> kernl multithreading and SMP cases: a processor, or a kernel thread
> is a preemptible context which holds resources.  If you support
> kernel preemption (either through another processor entering the
> kernel or through allowing simultaneous threads of control to coexist
> and switch at other than tsleep/quantum expiration), then you need
> to support the concept of deadlock resoloution (detection or avoidance)
> in the thread context in the kernel itself.
> 
> Microkernels tend to punt on this, stating that "servers" (threads
> outside the scope of the microkernel itself) operate in a seperate
> protection domain.  In the primary protection domain, the issue is
> ignored, and you are back to your user/kernel seperation, with a
> single kernel thread of control.
> 
> 
> 					Terry Lambert
> 					terry@lambert.org
> ---
> Any opinions in this posting are my own and not those of my present
> or previous employers.