[concurrency-interest] Lock implementation

Dawid Kurzyniec dawidk at mathcs.emory.edu
Thu Sep 28 19:31:05 EDT 2006


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



More information about the Concurrency-interest mailing list