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.