Date: Tue, 12 Sep 2000 12:08:15 +0930 From: Greg Lehey <grog@lemis.com> To: Terry Lambert <tlambert@primenet.com> Cc: John Baldwin <jhb@pike.osd.bsdi.com>, Mark Murray <markm@FreeBSD.ORG>, FreeBSD-arch@FreeBSD.ORG Subject: SMP lock ordering (was: cvs commit: src/sys/conf files src/sys/sys random.h src/sys/dev/randomdev hash.c hash.h harvest.c randomdev.c yarrow.c yarro) Message-ID: <20000912120815.I88615@wantadilla.lemis.com> In-Reply-To: <200009120012.RAA25062@usr09.primenet.com>; from tlambert@primenet.com on Tue, Sep 12, 2000 at 12:12:52AM %2B0000 References: <20000912091705.O19431@wantadilla.lemis.com> <200009120012.RAA25062@usr09.primenet.com>
next in thread | previous in thread | raw e-mail | index | archive | help
On Tuesday, 12 September 2000 at 0:12:52 +0000, Terry Lambert wrote: >> [following up to -arch] > [ ... ] >> I've been wondering whether we shouldn't associate mutexes with data >> structures rather than code. It's possible that it would make it >> easier to avoid deadlocks. Thoughts? > > I think that deadlock detection and back-off beats deadlock > avoidance, particularly if you are trying to debug something hairy. > The ability to take an EWOULDBLOCK response and decide to print out > the cycle that would result in the deadlock, not only for the caller > trying to assert a new lock/mutex, but for the other player(s) in > the deadlock situation, is invaluable. I believe the WITNESS code does this. Take a look at sys/kern/kern_mutex.c. > To achieve this, you really want to associate all locks into an > overall hierarchical relationship. This lets you keep metadata on > the locks; if you are familiar with Sedgewick, what you will be > doing is keeping a running tally of the transitive closure of arcs > (one per locking thread) over a directed acyclic graph. > > When you want to assert a new lock, you imply an edge from the lock > location (as a leaf node) to the root. Then you can do a linear > traversal to the root; this will immediately point out any cycles > which would be caused by the new lock, should the assertion go > through. This is normally a small number of compares, equal to the > depth of your tree at the location where the new lock would be, plus > one. Effectively, this is an O(1) method of finding Hamiltonian > cycles in your proposed lock list. Right, approaches like this have been tried before. Doesn't SGI do it this way? Obviously you don't want an iterative approach to getting the lock, but ensuring that you don't get a lock of lower level than the ones you're currently holding should be OK. The real issue I see here is that it will be *very* difficult to establish the relationships between the locks. > Creation and deletion of lock objects in the graph is a rare event, > and so can be permitted to be relatively expensive (though it's on > the order of 20,000 transactions a second on a P60, per work done at > Novell in 1994). I'd guess that this would be acceptable. Of course, it's dangerous to make assumptions based on other operating systems. Can you come up with code to back this kind of strategy? So far, nobody else has been able to. > SIX mode locking can further increase concurrency. > > It's easy to see that you could have, for example, a process table > that you wanted to be able to simultaneously access. You could have > a top level "entrire process table" lock, and then divide the table > into 6 chunks with inferior locks hung off the top level lock. This > would let you traverse 5/6ths of the table without contention, with > one writer holding a lock for creation of a new table entry. You > could take this to a per slot locking granularity, if you felt it > were necessary for the task at hand. Take a look at the way BSD/OS does it (see my earlier message). I don't think that just arbitrarily chopping up the struct makes sense; this method would mean that you might need to get more than one of these locks because of the geographic location of the data. Greg -- Finger grog@lemis.com for PGP public key See complete headers for address and phone numbers To Unsubscribe: send mail to majordomo@FreeBSD.org with "unsubscribe freebsd-arch" in the body of the message
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?20000912120815.I88615>