From owner-freebsd-hackers Thu Dec 5 16:25:15 1996 Return-Path: Received: (from root@localhost) by freefall.freebsd.org (8.8.4/8.8.4) id QAA14568 for hackers-outgoing; Thu, 5 Dec 1996 16:25:15 -0800 (PST) Received: from phaeton.artisoft.com (phaeton.Artisoft.COM [198.17.250.211]) by freefall.freebsd.org (8.8.4/8.8.4) with SMTP id QAA14562 for ; Thu, 5 Dec 1996 16:25:11 -0800 (PST) Received: (from terry@localhost) by phaeton.artisoft.com (8.6.11/8.6.9) id RAA21037; Thu, 5 Dec 1996 17:03:18 -0700 From: Terry Lambert Message-Id: <199612060003.RAA21037@phaeton.artisoft.com> Subject: Re: clone()/rfork()/threads (Re: Inferno for FreeBSD) To: michaelh@cet.co.jp (Michael Hancock) Date: Thu, 5 Dec 1996 17:03:17 -0700 (MST) Cc: terry@lambert.org, bakul@plexuscom.com, julian@whistle.com, cracauer@wavehh.hanse.de, nawaz921@cs.uidaho.EDU, freebsd-hackers@FreeBSD.ORG In-Reply-To: from "Michael Hancock" at Dec 6, 96 08:53:00 am X-Mailer: ELM [version 2.4 PL24] MIME-Version: 1.0 Content-Type: text/plain; charset=US-ASCII Content-Transfer-Encoding: 7bit Sender: owner-hackers@FreeBSD.ORG X-Loop: FreeBSD.org Precedence: bulk > I wonder how DEC handles priority inversion. Do they use priority > lending? > > Computing Transitive Closure takes too much time doesn't it? How many > nodes are there in a typical system? Is there an algorithm that scales > well? Well, Warshall's method (S. Warshall, 1962) has O(V(E+V) for a sparse graph, and O(V^3) for a dense graph. V is the number of vertices. Floyd's algortihm is similar. You *could* actually keep the adjacency matrix for the graphs transitive closure up to date each time you modify the adjacency matrix for the the graph. This actually yields *very* good results, since once established, the lock hierarchy is not likely to change. This ends up leaving you with a series of unit vectors for the adjacency to the node you want to modify from the root. You could easily compute the closure to a depth N in O(N+1). For a blanaced graph (the lock hierarchies I've described aren't balanced, so this doesn't apply), N is log2(n)+1 for n total nodes. This is hinted at in chapter 32, "directed graphs" in: Algorithms in C++ Robert Sedgewick Addison-Wesley publishing ISBN 0-201-51059-6 The book is a little light in the loafers regarding actual C++ code to implement the algorithms, but is a good reference. O(log n/loglog n)... pretty darn good! http://www.brics.dk/~thore/Papers/lowerbounds.html There are also some nice algorithms located at: http://www.cs.hut.fi/~psu/VK94/node28.html Since a locking graph is a digraph: http://www.cs.hut.fi/~enu/thesis.html These should still show up in a Yahoo search, actually... And, of course, there's Knuth... Terry Lambert terry@lambert.org --- Any opinions in this posting are my own and not those of my present or previous employers.