A scalable and starvation-free concurrent locking mechanism
Jonathan Nash · Concurrency Practice and Experience · 1999
Locks provide mutually exclusive access to a shared resource and are used in a wide range of situations, from within application programs and parallel libraries to operating system kernels. Thus, providing high performance for lock access is an important consideration in overall system performance. This paper describes an implementation of a locking mechanism for a multiprocessor. The approach is an extension of the classic Mellor–Crummey and Scott (MCS) algorithm, but using only a simple atomic swap operation to achieve both scalable high performance and starvation-free behaviour. The paper demonstrates the performance of the lock on a 256-processor Cray T3D machine. Copyright © 1999 John Wiley & Sons, Ltd.