Fairer and More Scalable Reader-Writer Locks by Optimizing Queue Management
Open Access
- 28 February 2025
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 115-127
Abstract
MCS lock and its variants provide scalability on many-core architectures, using lists of lock requests to reduce access contention on the mutex data. Most recent variants have adopted a two-stage design, allowing requests to be allocated from stack memory rather than heap. However, this design still produces mutex access contention and limits fairness in the presence of fast paths. This paper proposes the Freezer mechanism and its optimization methods, which extend the list structure operations of MCS lock, to reduce mutex access without using heap memory and enable an independent choice of fairness policies and fast paths. Additionally, we propose four optimization methods for queue-based reader-writer locks. Our evaluation using three benchmarks demonstrated the effectiveness of the proposed fair reader-writer locks. They achieved up to 3.5× higher throughput and improved tail latency by up to 2.7× compared to the baselines.Keywords
This publication has 27 references indexed in Scilit:
- Fissile Locks2021
- Queue Delegation LockingIEEE Transactions on Parallel and Distributed Systems, 2017
- Shared-Memory Synchronization2013
- User-Level Implementations of Read-Copy UpdateIEEE Transactions on Parallel and Distributed Systems, 2011
- Spin-based reader-writer synchronization for multiprocessor real-time systemsReal-Time Systems, 2010
- Benchmarking cloud serving systems with YCSB2010
- Queue locks on cache coherent multiprocessors2002
- Scalable reader-writer synchronization for shared-memory multiprocessorsACM SIGPLAN Notices, 1991
- Algorithms for scalable synchronization on shared-memory multiprocessorsACM Transactions on Computer Systems, 1991
- Concurrency of operations on B-treesActa Informatica, 1977