Name
Abstract | ||
|---|---|---|
We describe an approach for implementing higher-level mutual-exclusion constructs using Lamport's algorithm. A straightforward implementation of, for example, monitor locks based on Lamport's algorithm requires O(n) space per monitor lock if there are n processes that may share the lock. It has occasionally been claimed that this makes the algorithm undesirable in practice. The insight presented here is that we only need a (small) constant amount of space per lock, plus O(n) space shared by all locks in the system. For some common applications, this adds no memory references to the implementation of the algorithm. Fully general spin-lock acquisition and release can usually be implemented with the addition of one memory reference to Lamport's algorithm. On particularly unfavorable hardware, three additional memory references may be required in the contention-free case. |
Year | DOI | Venue |
|---|---|---|
1993 | 10.1145/176454.176479 | LOPLAS |
Keywords | Field | DocType |
common application,multiprocessing,general spin-lock acquisition,additional memory reference,constant amount,monitor lock,n process,critical section,memory reference,contention-free case,multiple lock,straightforward implementation,mutual exclusion algorithm,higher-level mutual-exclusion,spin lock,mutual exclusion | Lamport's bakery algorithm,Lock (computer science),Computer science,Parallel computing,Critical section,Lamport timestamps,Algorithm,Logical clock,Multiprocessing,Theoretical computer science,Mutual exclusion | Journal |
Volume | Issue | Citations |
2 | 1-4 | 0 |
PageRank | References | Authors |
0.34 | 3 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Hans Boehm | 1 | 632 | 38.83 |
| A J Demers | 2 | 8151 | 2084.66 |
| Chris Uhler | 3 | 0 | 0.34 |