Abstract
The MCS lock of Mellor-Crummey and Scott (1991), 23 pages. is a very efficient first-come first-served mutual-exclusion algorithm that uses the atomic hardware primitives fetch-and-store and compare-and-swap. However, it has the disadvantage that the calling thread must provide a pointer to an allocated record. This additional parameter violates the standard locking interface, which has only the lock as a parameter. Hence, it is impossible to switch to MCS without editing and recompiling an application that uses locks.
This article provides a variation of MCS with the standard interface, which remains FCFS, called MCSH. One key ingredient is to stack allocate the necessary record in the acquire procedure of the lock, so its life-time only spans the delay to enter a critical section. A second key ingredient is communicating the allocated record between the acquire and release procedures through the lock to maintain the standard locking interface. Both of these practices are known to practitioners, but our solution combines them in a unique way. Furthermore, when these practices are used in prior papers, their correctness is often argued informally. The correctness of MCSH is verified rigorously with the proof assistant PVS, and experiments are run to compare its performance with MCS and similar locks.
- [1] . 1991. The existence of refinement mappings. Theor. Comput. Sci. 82 (1991), 253–284.Google ScholarDigital Library
- [2] . 2003. Enhancement to the MCS lock for increased functionality and improved programmability.
U.S. patent application number 20030200457 (abondoned). Google Scholar - [3] . 2015. High-performance N-thread software solutions for mutual exclusion. Concurr. Computat.: Pract. Exp. 27 3 (March 2015), 651–701. Google ScholarCross Ref
- [4] . 2022. Locking Micro-Benchmarks. Retrieved from https://github.com/pabuhr/concurrent-locking.Google Scholar
- [5] . 2021. Fissile locks. In Networked Systems, and (Eds.). Vol. LNCS 12129. Springer International Publishing, Cham, Switzerland, 192–208.Google ScholarDigital Library
- [6] . 2021. Hemlock: Compact and scalable mutual exclusion. In Proceedings of the 33rd ACM Symposium on Parallelism in Algorithms and Architectures. ACM, New York, NY, 173–183.Google ScholarDigital Library
- [7] . 1965. Cooperating Sequential Processes.
Technical Report . Technological University, Eindhoven, 87 pages. https://pure.tue.nl/ws/files/4279816/344354178746665.pdf.Google Scholar - [8] . 1965. Solution of a problem in concurrent programming control. Commun. ACM 8, 9 (
September 1965), 569.Google ScholarDigital Library - [9] . 1976. A Discipline of Programming. Prentice-Hall, Englewood Cliffs, NJ.Google ScholarDigital Library
- [10] . 2022. Futexes Are Tricky, Red Hat Inc., 12 pages. Retrieved from https://cis.temple.edu/∼giorgio/cis307/readings/futex.pdf.Google Scholar
- [11] . 2022. PVS Proof Scripts for Verification of Hardware Locks. Retrieved from http://wimhesselink.nl/mechver/HardwareLocks.Google Scholar
- [12] . 2022. Trylock, a case for temporal logic and eternity variables. Sci. Comput. Program. 216, C (
April 2022), 12.Google Scholar - [13] . 2021. Serially Reusable Programs. Retrieved from https://www.ibm.com/docs/en/ztpf/1.1.0.15?topic=structures-serially-reusable-programs.Google Scholar
- [14] . 1974. A new solution of Dijkstra’s concurrent programming problem. Commun. ACM 17 (1974), 453–455.Google ScholarDigital Library
- [15] . 1987. A fast mutual exclusion algorithm. ACM Trans. Comput. Syst. 5 (1987), 1–11.Google ScholarDigital Library
- [16] . 2013. qspinlock: Introducing a 4-byte Queue Spinlock Implementation. Retrieved from https://lwn.net/Articles/561775.Google Scholar
- [17] . 1994. Queue locks on cache coherent multiprocessors. In Proceedings of the 8th International Symposium on Parallel Processing. IEEE Computer Society, Los Alamitos, CA, 165–171.Google ScholarDigital Library
- [18] . 1991. Algorithms for scalable synchronization on shared-memory multiprocessors. ACM Trans. Comput. Syst. 9 (1991), 21–65.Google ScholarDigital Library
- [19] . 2004. Hazard pointers: Safe memory reclamation for lock-free objects. IEEE Trans. Parallel Distrib. Syst. 15, 6 (
June 2004), 491–504.Google ScholarDigital Library - [20] . 2020. PVS Language Reference Version 7.1. SRI International, Computer Science Laboratory, Menlo Park CA, 113 pages. Retrieved February 7, 2023 from https://pvs.csl.sri.com/doc/pvs-language-reference.pdf.Google Scholar
- [21] . 2013. Shared-memory Synchronization. Morgan & Claypool.Google ScholarDigital Library
- [22] . 2016. Be my guest: MCS lock now welcomes guests. In Proceedings of the 21st ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (PPoPP’16). ACM, New York, NY, Article
21 , 12 pages.Google ScholarDigital Library - [23] . 2022. Application Binary Interface.Retrieved February 7, 2023 from https://en.wikipedia.org/wiki/Application_binary_interface.Google Scholar
- [24] . 2022. Application Program Interface.Retrieved February 7, 2023 from https://en.wikipedia.org/wiki/API.Google Scholar
- [25] . 2022. Thread-local Storage. Retrieved February 7, 2023 from https://en.wikipedia.org/wiki/Thread-local_storage.Google Scholar
Index Terms
- MCSH, a Lock with the Standard Interface
Recommendations
Help when needed, but no more: Efficient read/write partial snapshot
An atomic snapshot object is an object that can be concurrently accessed by asynchronous processes prone to crash. It is made of m components (base atomic registers) and is defined by two operations: an update operation that allows a process to ...
Lock Cohorting: A General Technique for Designing NUMA Locks
Special Issue on PPOPP 2012Multicore machines are quickly shifting to NUMA and CC-NUMA architectures, making scalable NUMA-aware locking algorithms, ones that take into account the machine's nonuniform memory and caching hierarchy, ever more important. This article presents lock ...
An efficient lock-aware transactional memory implementation
ICOOOLPS '09: Proceedings of the 4th workshop on the Implementation, Compilation, Optimization of Object-Oriented Languages and Programming SystemsTransactional memory (TM) is an emerging concurrency control mechanism that provides a simple and composable programming model. Unfortunately, transactions violate the semantics of mutual exclusion locks when they execute concurrently. Due to the ...
Comments