Avoiding Scheduler Subversion Using Scheduler-Cooperative Locks

Yuvraj Patel, Leon Yang, Leo Arulraj, Andrea C. Arpaci-Dusseau, Remzi H. Arpaci-Dusseau, Michael M. Swift

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

We introduce the scheduler subversion problem, where lock usage patterns determine which thread runs, thereby subverting CPU scheduling goals. To mitigate this problem, we introduce Scheduler-Cooperative Locks (SCLs), a new family of locking primitives that controls lock usage and thus aligns with system-wide scheduling goals; our initial work focuses on proportional share schedulers. Unlike existing locks, SCLs provide an equal (or proportional) time window called lock opportunity within which each thread can acquire the lock. We design and implement three different scheduler-cooperative locks that work well with proportional-share schedulers: a user-level mutex lock (u-SCL), a reader-writer lock (RW-SCL), and a simplified kernel implementation (k-SCL). We demonstrate the effectiveness of SCLs in two user-space applications (UpScaleDB and KyotoCabinet) and the Linux kernel. In all three cases, regardless of lock usage patterns, SCLs ensure that each thread receives proportional lock allocations that match those of the CPU scheduler. Using microbenchmarks, we show that SCLs are efficient and achieve high performance with minimal overhead under extreme workloads.
Original languageEnglish
Title of host publicationProceedings of the Fifteenth European Conference on Computer Systems
Place of PublicationNew York, NY, USA
PublisherAssociation for Computing Machinery, Inc
Number of pages17
ISBN (Print)9781450368827
DOIs
Publication statusPublished - 17 Apr 2020
EventThe 15th European Conference on Computer Systems 2020 - Heraklion, Greece
Duration: 27 Apr 202030 Apr 2020
Conference number: 15
https://www.eurosys2020.org/

Publication series

NameEuroSys '20
PublisherAssociation for Computing Machinery

Conference

ConferenceThe 15th European Conference on Computer Systems 2020
Abbreviated titleEuroSys 2020
Country/TerritoryGreece
CityHeraklion
Period27/04/2030/04/20
Internet address

Fingerprint

Dive into the research topics of 'Avoiding Scheduler Subversion Using Scheduler-Cooperative Locks'. Together they form a unique fingerprint.

Cite this