Hans-J. Boehm
Alan J. Demers
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.
- BERSHAD, B., REDELL, D., AND ELLIS, J. 1992. Fast mutual exclusion for uniprocessors. In ASPLOS-V Proceedings. SIGPLAN Not. 27, 9 (Sept.), 223-233. Google Scholar
- BURNS, J., AND LYNCH, N. 1993. Bounds on shared memory for mutual exclusion. Inf. Comput. 107, 2 (Dec.), 171-184. Google Scholar
- LAMPORT, L. 1987. A fast mutual exclu'sion algorithm. ACM Trans. Comput. Syst. 5, 1 (Feb.), 1-11. Google Scholar
- OWICKI, S., AND GRIES, D. 1976. An axiomatic proof technique for parallel programs. Acta Inf. 6, 4, 319-340.Google Scholar
- WEISER, M., DEMERS, A., AND HAUSER, C. 1989. The portable common runtime approach to interoperability. In Proceedings of the 12th ACM Symposium on Operating System Principles (Litchfield Park, Ariz., Dec. 1989). ACM, New York. Proceedings appeared as Oper. Syst. Rev. 23, 5. Google Scholar
Index Terms
- Implementing multiple locks using Lamport's mutual exclusion algorithm
Recommendations
An Efficient Abortable-locking Protocol for Multi-level NUMA Systems
PPoPP '17The popularity of Non-Uniform Memory Access (NUMA) architectures has led to numerous locality-preserving hierarchical lock designs, such as HCLH, HMCS, and cohort locks. Locality-preserving locks trade fairness for higher throughput. Hence, some ...
Fast mutual exclusion for uniprocessors
In this paper we describe restartable atomic sequences, an optimistic mechanism for implementing simple atomic operations (such as Test-And-Set) on a uniprocessor. A thread that is suspended within a restartable atomic sequence is resumed by the ...
Fast mutual exclusion for uniprocessors
ASPLOS V: Proceedings of the fifth international conference on Architectural support for programming languages and operating systemsIn this paper we describe restartable atomic sequences, an optimistic mechanism for implementing simple atomic operations (such as Test-And-Set) on a uniprocessor. A thread that is suspended within a restartable atomic sequence is resumed by the ...
Reviews
M. A. Bassiouni
The implementation of spin locks using Lamport's fast algorithm for mutual exclusion [1] is described. A straightforward implementation of Lamport's algorithm would replicate all of its variables, including the Boolean vector used to detect and resolve contention, for each lock in the system. The contribution of this paper is that it shows how to implement Lamport's algorithm by sharing a single Boolean vector among all locks used. This reduces the space requirement of each lock from O n to O n/m , where n is the number of processes that use the locks and m is the number of locks in the system. The paper is well written, and the presentation is clear and logically structured. The authors present their approach by first considering a restricted type of locking environment where no process can hold more than one lock at a time. They then show how to extend their approach to the case of nested locking. Proofs of correctness are adequately covered in two appendices. Although the paper does not provide new fundamental results, it is a welcome addition to the rich and growing literature on mutual exclusion algorithms. The main benefit of the paper is that it gives a practical way to implement a well-known algorithm without incurring a linear growth in space requirement as the number of locks in the system increases. This contribution is of practical value. The authors also include helpful remarks about the speed of their implementation and the additional overhead (in memory references) if their approach is implemented on unfavorable hardware. The paper would have been more useful, however, if it contained detailed performance results on the speed of this approach in comparison with other implementations.
Access critical reviews of Computing literature here
Become a reviewer for Computing Reviews.
Comments