From owner-freebsd-hackers Mon Jul 15 19:53:55 1996 Return-Path: owner-hackers Received: (from root@localhost) by freefall.freebsd.org (8.7.5/8.7.3) id TAA20890 for hackers-outgoing; Mon, 15 Jul 1996 19:53:55 -0700 (PDT) Received: from parkplace.cet.co.jp (parkplace.cet.co.jp [202.32.64.1]) by freefall.freebsd.org (8.7.5/8.7.3) with ESMTP id TAA20871 for ; Mon, 15 Jul 1996 19:53:48 -0700 (PDT) Received: from localhost (michaelh@localhost) by parkplace.cet.co.jp (8.7.5/CET-v2.1) with SMTP id CAA15424; Tue, 16 Jul 1996 02:51:47 GMT Date: Tue, 16 Jul 1996 11:51:47 +0900 (JST) From: Michael Hancock To: Terry Lambert cc: dm@sgi.com, imp@village.org, bde@zeta.org.au, matt@lkg.dec.com, freebsd-hackers@freebsd.org, tech-kern@NetBSD.ORG Subject: Re: Some interesting papers on BSD ... In-Reply-To: <199607152101.OAA09285@phaeton.artisoft.com> Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Sender: owner-hackers@freebsd.org X-Loop: FreeBSD.org Precedence: bulk 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.