Lock implementation

classic Classic list List threaded Threaded
4 messages Options
Reply | Threaded
Open this post in threaded view
|

Lock implementation

Unmesh joshi
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?

Thanks,
Unmesh


_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://altair.cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: Lock implementation

Dawid Kurzyniec
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


_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://altair.cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: Lock implementation

Boehm, Hans
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: [hidden email]
> [mailto:[hidden email]] On Behalf
> Of Dawid Kurzyniec
> Sent: Thursday, September 28, 2006 9:52 AM
> To: Unmesh joshi
> Cc: [hidden email]
> 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
> [hidden email]
> http://altair.cs.oswego.edu/mailman/listinfo/concurrency-interest
>

_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://altair.cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: Lock implementation

Dawid Kurzyniec
Boehm, Hans wrote:
> 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 guess one potential advantage of Eisenberg-McGuire over Lamport's is
fairness - if one needs it.

> 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.
>  
We have experimented with such locks in distributed computing settings -
to coordinate access to data shared in a JNDI service, without using
external lock managers. But then, the problem of failure recovery arises
- i.e. what do you do if somebody crashes (or gets disconnected) while
holding the lock, and possibly after having made changes that caused the
data to be inconsistent. It seems that most usage scenarios (except for
very simple ones, like atomic variables, counters etc.) require true
transactions anyway.

Does it mean that those algorithms are interesting only from a
theoretical point of view?

Regards,
Dawid

_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://altair.cs.oswego.edu/mailman/listinfo/concurrency-interest