Computing Reviews
Today's Issue Hot Topics Search Browse Recommended My Account Log In
Review Help
Search
Implementing multiple locks using Lamport’s mutual exclusion algorithm
Boehm H., Demers A., Uhler C. ACM Letters on Programming Languages and Systems2 (1-4):46-58,1993.Type:Article
Date Reviewed: May 1 1995

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 &slash; 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.

Reviewer:  M. A. Bassiouni Review #: CR118398
1) Lamport, L. A fast mutual exclusion algorithm. ACM Trans. Comput. Syst. 15, 1 (Feb. 1987), 1–11.
Bookmark and Share
 
Mutual Exclusion (D.4.1 ... )
 
 
Concurrent Programming Structures (D.3.3 ... )
 
Would you recommend this review?
yes
no
Other reviews under "Mutual Exclusion": Date
Another solution of the mutual exclusion problem
Kowaltowski T., Palma A. Information Processing Letters 19(3): 145-146, 1984. Type: Article
May 1 1985
The mutual exclusion problem
Lamport L. Journal of the ACM 33(2): 313-326, 1986. Type: Article
Apr 1 1987
The mutual exclusion problem
Lamport L. Journal of the ACM 33(2): 327-348, 1986. Type: Article
Apr 1 1987
more...

E-Mail This Printer-Friendly
Send Your Comments
Contact Us
Reproduction in whole or in part without permission is prohibited.   Copyright 1999-2024 ThinkLoud®
Terms of Use
| Privacy Policy