Towards an Ideal Queue Lock
Prasad Jayanti, Siddhartha Jayanti, Sucharita Jayanti · 2020
The MCS lock was the first mutual exclusion lock to support an arbitrary number of processes with unknown identities such that each process can acquire and release the lock in a constant number of RMRs on both Cache-Coherent and Distributed Shared Memory multiprocessors. The MCS algorithm, however, has a shortcoming: its Exit section is not bounded. The algorithm also requires hardware support for more than one special instruction, namely, Fetch&Store and Compare&Swap.