Date: Thu, 5 Dec 1996 17:03:17 -0700 (MST) From: Terry Lambert <terry@lambert.org> To: michaelh@cet.co.jp (Michael Hancock) Cc: terry@lambert.org, bakul@plexuscom.com, julian@whistle.com, cracauer@wavehh.hanse.de, nawaz921@cs.uidaho.EDU, freebsd-hackers@FreeBSD.ORG Subject: Re: clone()/rfork()/threads (Re: Inferno for FreeBSD) Message-ID: <199612060003.RAA21037@phaeton.artisoft.com> In-Reply-To: <Pine.SV4.3.95.961206084725.29547A-100000@parkplace.cet.co.jp> from "Michael Hancock" at Dec 6, 96 08:53:00 am
next in thread | previous in thread | raw e-mail | index | archive | help
> 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.
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?199612060003.RAA21037>