[concurrency-interest] Lock implementation

Boehm, Hans hans.boehm at hp.com
Thu Sep 28 15:03:28 EDT 2006


There are also other algorithms that need only O(N+M) memory for M locks
for N threads, which I suspect is a practical requirement.  See

``Implementing Multiple Locks Using Lamport's Mutual Exclusion
Algorithm'', Hans-J. Boehm, Alan Demers and Chris Uhler, ACM LOPLAS 2
(Mar-Dec 1993), pp. 46-58.

I don't think any of these are practical on most modern hardware, since
they usually require memory fences, which in turn tend to be not much
cheaper than atomic memory updates.  If you have sequentially consistent
hardware with slow or nonexistent atomic memory updates, then they might
make sense.

Hans

> -----Original Message-----
> From: concurrency-interest-bounces at cs.oswego.edu 
> [mailto:concurrency-interest-bounces at cs.oswego.edu] On Behalf 
> Of Dawid Kurzyniec
> Sent: Thursday, September 28, 2006 9:52 AM
> To: Unmesh joshi
> Cc: concurrency-interest at cs.oswego.edu
> Subject: Re: [concurrency-interest] Lock implementation
> 
> Unmesh joshi wrote:
> > Hi,
> >
> > Most of the commercial Lock implementations rely on low 
> level atomic 
> > instructions like compare_and_swap. Is there any algorithm 
> that does 
> > not rely on low level atomic instructions and is commerciall proven?
> There is Eisenberg-McGuire algorithm, which does not use 
> atomic operations:
> 
> http://www.cs.ucr.edu/~ysong/cs160/lab4/eisenberg-mcguire.cc
> 
> but for the price of much higher overhead (about 8 read and 
> write operations per acquire in uncontended case). I don't 
> know whether it is commercially proven, but it is definitely 
> mathematically proven :)
> 
> Look also here for the example distributed locking 
> implementation based on this scheme:
> 
> http://dcl.mathcs.emory.edu/cgi-bin/viewvc.cgi/software/harnes
s2/trunk/util/src/edu/emory/mathcs/util/remote/locks/RemoteEisMcGLock.ja
va?revision=2416&view=markup
> 
> and here, for the JNDI-based use case:
> 
> http://dcl.mathcs.emory.edu/cgi-bin/viewvc.cgi/software/harnes
> s2/trunk/jndi/jndi-common/src/edu/emory/mathcs/jndi/locks/Fair
> JNDILock.java?revision=2102&view=markup
> 
> 
> Regards,
> Dawid
> 
> 
> _______________________________________________
> Concurrency-interest mailing list
> Concurrency-interest at altair.cs.oswego.edu
> http://altair.cs.oswego.edu/mailman/listinfo/concurrency-interest
> 



More information about the Concurrency-interest mailing list