Date: Tue, 12 Sep 2000 04:08:10 +0000 (GMT) From: Terry Lambert <tlambert@primenet.com> To: grog@lemis.com (Greg Lehey) Cc: tlambert@primenet.com (Terry Lambert), jhb@pike.osd.bsdi.com (John Baldwin), markm@FreeBSD.ORG (Mark Murray), FreeBSD-arch@FreeBSD.ORG Subject: Re: 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 random Message-ID: <200009120408.VAA19788@usr07.primenet.com> In-Reply-To: <20000912120815.I88615@wantadilla.lemis.com> from "Greg Lehey" at Sep 12, 2000 12:08:15 PM
next in thread | previous in thread | raw e-mail | index | archive | help
[ ... hierarchical locks with up front state costing ... ] > 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. I don't know what SGI does; that's one UNIX kernel I haven't been into the guts of yet. > The real issue I see here is that it will be *very* difficult to > establish the relationships between the locks. It's complex, but it's not really that difficult, given the correct structures. > > 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. That was 20,000 transactions a second in a user space process acting as a lock manager. The first attempt was a spinlock, followed by a heavier weight semaphore acquisition on a collision. > Can you come up with code to back this kind of strategy? So far, > nobody else has been able to. I have some code. It tries to optimize cycles by inheritance, when someone holds some locks, and goes onto a wait list for a lock held by someone else. This adds an additional dimension to the pot, resulting in a 5 dimensional graph, but it's not that hard. You just have to think in terms of things that can be locked, things that can do locking, groups of things that can do locking (as in multiple threads in a single process), the set of locks held by the group (an arc), and the base graph in which the hierarchy of lockables are created. Mostly, it's just pointer frobbing and some nasty data structures. > > SIX mode locking can further increase concurrency. [ ... bad example of where you would increase granularity ... ] > 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. OK, my example was bad, but the idea is sound; a better example would be a system wide and per processor resource pools that get filled/drained from/to the system pools for things like vnodes and other objects. The point was that the amount of real contention would be reduced. The "process" structure I described was really a per client state structure for a file server, in the work back in 1994, but I didn't want to complicate things. I guess it's best to stick with first principles... the pools example might have one processor stalling another in an 8 processor system in order to do page stealing, while the other 6 processors march merrily along. 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-arch" in the body of the message
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?200009120408.VAA19788>