[concurrency-interest] Lock implementation
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
Does it mean that those algorithms are interesting only from a
theoretical point of view?
More information about the Concurrency-interest