From owner-freebsd-smp Sun Jun 27 22:21:21 1999 Delivered-To: freebsd-smp@freebsd.org Received: from smtp01.primenet.com (smtp01.primenet.com [206.165.6.131]) by hub.freebsd.org (Postfix) with ESMTP id 8D905150D9 for ; Sun, 27 Jun 1999 22:21:15 -0700 (PDT) (envelope-from tlambert@usr04.primenet.com) Received: (from daemon@localhost) by smtp01.primenet.com (8.8.8/8.8.8) id WAA07042; Sun, 27 Jun 1999 22:21:15 -0700 (MST) Received: from usr04.primenet.com(206.165.6.204) via SMTP by smtp01.primenet.com, id smtpd007015; Sun Jun 27 22:21:07 1999 Received: (from tlambert@localhost) by usr04.primenet.com (8.8.5/8.8.5) id WAA27383; Sun, 27 Jun 1999 22:21:05 -0700 (MST) From: Terry Lambert Message-Id: <199906280521.WAA27383@usr04.primenet.com> Subject: Re: high-efficiency SMP locks - submission for review To: bakul@torrentnet.com (Bakul Shah) Date: Mon, 28 Jun 1999 05:21:05 +0000 (GMT) Cc: julian@whistle.com, dillon@apollo.backplane.com, freebsd-smp@FreeBSD.ORG In-Reply-To: <199906272253.SAA04385@chai.torrentnet.com> from "Bakul Shah" at Jun 27, 99 06:53:30 pm X-Mailer: ELM [version 2.4 PL25] MIME-Version: 1.0 Content-Type: text/plain; charset=US-ASCII Content-Transfer-Encoding: 7bit Sender: owner-freebsd-smp@FreeBSD.ORG Precedence: bulk X-Loop: FreeBSD.org > 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