[concurrency-interest] Lock implementation

Dawid Kurzyniec dawidk at mathcs.emory.edu
Thu Sep 28 12:51:35 EDT 2006


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/harness2/trunk/util/src/edu/emory/mathcs/util/remote/locks/RemoteEisMcGLock.java?revision=2416&view=markup

and here, for the JNDI-based use case:

http://dcl.mathcs.emory.edu/cgi-bin/viewvc.cgi/software/harness2/trunk/jndi/jndi-common/src/edu/emory/mathcs/jndi/locks/FairJNDILock.java?revision=2102&view=markup


Regards,
Dawid




More information about the Concurrency-interest mailing list