Fairer and More Scalable Reader-Writer Locks by Optimizing Queue Management
This program is tentative and subject to change.
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 contention in mutex access and limits fairness when using fast paths. This paper proposes \textit{Freezer} mechanism and its optimization methods, which extend the list structure operations of MCS lock, to achieve reducing mutex access without using heap memory and enabling independent choice of fairness policies and use of fast paths. Additionally, we propose four optimization methods for queue-based reader-writer locks. Our evaluation using three benchmarks confirmed the effectiveness of the proposed fair reader-writer locks. They achieved up to 3.4$\times$ higher throughput and improved tail latency by up to 2.9$\times$ compared to baselines.
This program is tentative and subject to change.
Mon 3 MarDisplayed time zone: Pacific Time (US & Canada) change
14:00 - 15:20 | Session 3: Concurrent Data Structures and Synchronization I (Session Chair: TBA)Main Conference at Acacia D | ||
14:00 20mTalk | Reciprocating Locks Main Conference | ||
14:20 20mTalk | Aggregating Funnels for Faster Fetch&Add and Queues Main Conference Younghun Roh MIT, Yuanhao Wei University of British Columbia, Eric Ruppert York University, Panagiota Fatourou FORTH ICS and University of Crete, Greece, Siddhartha Jayanti Google Research, Julian Shun MIT | ||
14:40 20mTalk | Fairer and More Scalable Reader-Writer Locks by Optimizing Queue Management Main Conference | ||
15:00 20mTalk | Publish on Ping: A Better Way to Publish Reservations in Memory Reclamation for Concurrent Data Structures Main Conference |