Fairer and More Scalable Reader-Writer Locks by Optimizing Queue Management

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.