Date: Mon, 28 Jun 1999 05:21:05 +0000 (GMT) From: Terry Lambert <tlambert@primenet.com> To: bakul@torrentnet.com (Bakul Shah) Cc: julian@whistle.com, dillon@apollo.backplane.com, freebsd-smp@FreeBSD.ORG Subject: Re: high-efficiency SMP locks - submission for review Message-ID: <199906280521.WAA27383@usr04.primenet.com> In-Reply-To: <199906272253.SAA04385@chai.torrentnet.com> from "Bakul Shah" at Jun 27, 99 06:53:30 pm
next in thread | previous in thread | raw e-mail | index | archive | help
> IMHO any use of NBS would likely result in a redesign rather > than an addition of yet another way to synchronize so it is > not for the faint of heart. This is an understatement. Most implementations which I am aware of require that you use the Djikstra soloution to the Bankers Algorithm, either explicitly (reservation of all needed resources as a single call, where no locks are granted if none are), or implicitly (you guarantee that your order of operation will never be inverted in order to avoid the possibility of deadlock. I am rather fond of incrementally precomputing the Warshall's on the lock graph, and then doing deadlock detection by implying an edge between the thing you are proposing to lock and the root of the graph (thus implying a Hamiltonian cycle if allowing the lock would result in a deadlock, with only a single traversal from the terminal object to the root being required to detect that a dealock would occur -- usually no more than 8 pointer dereferences for an average graph depth of 8). I also have a slight problem with relying on a test-and-set instruction any more complicated than that which can be implemented with P/V semaphores. Many processors (e.g. MIPS) don't have an atomic test and set, and you'd want to avoid architecting against them ever working. 8-(. > Henry Massalin's thesis on the Synthesis kernel would also be > useful reading. It is full of so many interesting ideas I am > amazed no one has stolen most of them as yet! Thanks for the referemce! I'm going digging now... Terry Lambert terry@lambert.org --- Any opinions in this posting are my own and not those of my present or previous employers. To Unsubscribe: send mail to majordomo@FreeBSD.org with "unsubscribe freebsd-smp" in the body of the message
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?199906280521.WAA27383>