More Web Proxy on the site http://driver.im/

research-article

Avoiding scheduler subversion using scheduler-cooperative locks

Authors:

Andrea C. Arpaci-Dusseau,

Remzi H. Arpaci-Dusseau,

Michael M. SwiftAuthors Info & Claims

EuroSys '20: Proceedings of the Fifteenth European Conference on Computer Systems

Article No.: 9, Pages 1 - 17

https://doi.org/10.1145/3342195.3387521

Published: 17 April 2020 Publication History

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.

References

[1]

T. E. Anderson. The Performance of Spin Lock Alternatives for Shared-Memory Multiprocessors. IEEE Trans. Parallel Distrib. Syst., 1(1):6--16, January 1990.

Digital Library

[2]

Jonathan Appavoo, Marc Auslander, Maria Butrico, Dilma M Da Silva, Orran Krieger, Mark F Mergen, Michal Ostrowski, Bryan Rosenburg, Robert W Wisniewski, and Jimi Xenidis. Experience with K42, an open-source, Linux-compatible, scalable operating-system kernel. IBM Systems Journal, 44(2):427--440, 2005.

Digital Library

[3]

Remzi H Arpaci-Dusseau and Andrea C Arpaci-Dusseau. Operating systems: Three easy pieces. Arpaci-Dusseau Books LLC, 2018.

[4]

Gaurav Banga, Peter Druschel, and Jeffrey C. Mogul. Resource Containers: A New Facility for Resource Management in Server Systems. In Proceedings of the Third Symposium on Operating Systems Design and Implementation, OSDI '99, page 45--58, USA, 1999. USENIX Association.

Digital Library

[5]

Justinien Bouron, Sébastien Chevalley, Baptiste Lepers, Willy Zwaenepoel, Redha Gouicem, Julia Lawall, Gilles Muller, and Julien Sopena. The Battle of the Schedulers: FreeBSD ULE vs. Linux CFS. In 2018 USENIX Annual Technical Conference (USENIX ATC 18), pages 85--96, 2018.

[6]

Silas Boyd-Wickizer, M Frans Kaashoek, Robert Morris, and Nickolai Zeldovich. Non-scalable locks are dangerous. In Proceedings of the Linux Symposium, pages 119--130, 2012.

[7]

Björn B. Brandenburg and James H. Anderson. Spin-Based Reader-Writer Synchronization for Multiprocessor Real-Time Systems. Real-Time Systems, 46:25--87, 2010.

Digital Library

[8]

Irina Calciu, Dave Dice, Yossi Lev, Victor Luchangco, Virendra J Marathe, and Nir Shavit. NUMA-aware reader-writer locks. In Proceedings of the 18th ACM SIGPLAN symposium on Principles and practice of parallel programming, pages 157--166, 2013.

Digital Library

[9]

Remy Card. tune2fs(8) - linux man page. https://linux.die.net/man/8/tune2fs, 2020.

[10]

Daniel Cederman, Bapi Chatterjee, Nhan Nguyen, Yiannis Nikolakopoulos, Marina Papatriantafilou, and Philippas Tsigas. A Study of the Behavior of Synchronization Methods in Commonly Used Languages and Systems. In 2013 IEEE 27th International Symposium on Parallel and Distributed Processing, pages 1309--1320. IEEE, 2013.

[11]

Milind Chabbi, Michael Fagan, and John Mellor-Crummey. High Performance Locks for Multi-Level NUMA Systems. In Proceedings of the 20th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, PPoPP 2015, page 215--226, New York, NY, USA, 2015. Association for Computing Machinery.

[12]

Milind Chabbi and John Mellor-Crummey. Contention-Conscious, Locality-Preserving Locks. In Proceedings of the 21st ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, PPoPP '16, New York, NY, USA, 2016. Association for Computing Machinery.

[13]

Shuang Chen, Shay GalOn, Christina Delimitrou, Srilatha Manne, and Jose F Martinez. Workload Characterization of Interactive Cloud Services on Big and Small Server Platforms. In 2017 IEEE International Symposium on Workload Characterization (IISWC), pages 125--134. IEEE, 2017.

[14]

Travis Craig. Building FIFO and Priority-Queuing Spin Locks from Atomic Swap. Technical report, Technical Report TR 93-02-02, Department of Computer Science, University of Washington, 1993.

[15]

Tudor David, Rachid Guerraoui, and Vasileios Trigonakis. Everything You Always Wanted to Know about Synchronization but Were Afraid to Ask. In Proceedings of the Twenty-Fourth ACM Symposium on Operating Systems Principles, SOSP '13, page 33--48, New York, NY, USA, 2013. Association for Computing Machinery.

Digital Library

[16]

Mathieu Desnoyers, Paul E. McKenney, Alan S. Stern, Michel R. Dagenais, and Jonathan Walpole. User-Level Implementations of Read-Copy Update. IEEE Trans. Parallel Distrib. Syst., 23(2):375--382, February 2012.

Digital Library

[17]

Dave Dice. Malthusian Locks. In Proceedings of the Twelfth European Conference on Computer Systems, EuroSys '17, page 314--327, New York, NY, USA, 2017. Association for Computing Machinery.

[18]

Dave Dice and Alex Kogan. BRAVO: Biased Locking for Reader-Writer Locks. In Proceedings of the 2019 USENIX Conference on Usenix Annual Technical Conference, USENIX ATC '19, page 315--328, USA, 2019. USENIX Association.

[19]

Dave Dice and Alex Kogan. Compact NUMA-Aware Locks. In Proceedings of the Fourteenth EuroSys Conference 2019, EuroSys '19, New York, NY, USA, 2019. Association for Computing Machinery.

[20]

Dave Dice, Virendra J. Marathe, and Nir Shavit. Flat-Combining NUMA Locks. In Proceedings of the Twenty-Third Annual ACM Symposium on Parallelism in Algorithms and Architectures, SPAA '11, page 65--74, New York, NY, USA, 2011. Association for Computing Machinery.

[21]

David Dice. Brief Announcement: A Partitioned Ticket Lock. In Proceedings of the Twenty-Third Annual ACM Symposium on Parallelism in Algorithms and Architectures, SPAA '11, page 309--310, New York, NY, USA, 2011. Association for Computing Machinery.

[22]

David Dice, Virendra J. Marathe, and Nir Shavit. Lock Cohorting: A General Technique for Designing NUMA Locks. ACM Trans. Parallel Comput., 1(2), February 2015.

Digital Library

[23]

D. H. J. Epema. An Analysis of Decay-Usage Scheduling in Multiprocessors. SIGMETRICS Perform. Eval. Rev., 23(1):74--85, May 1995.

Digital Library

[24]

Panagiota Fatourou and Nikolaos D. Kallimanis. Revisiting the Combining Synchronization Technique. SIGPLAN Not., 47(8):257--266, February 2012.

Digital Library

[25]

Rachid Guerraoui, Hugo Guiroux, Renaud Lachaize, Vivien Quéma, and Vasileios Trigonakis. Lock-Unlock: Is That All? A Pragmatic Analysis of Locking in Software Systems. ACM Trans. Comput. Syst., 36(1), March 2019.

[26]

Hugo Guiroux, Renaud Lachaize, and Vivien Quéma. Multicore Locks: The Case is Not Closed Yet. In Proceedings of the 2016 USENIX Conference on Usenix Annual Technical Conference, USENIX ATC '16, page 649--662, USA, 2016. USENIX Association.

[27]

Bijun He, William N. Scherer, and Michael L. Scott. Preemption Adaptivity in Time-Published Queue-Based Spin Locks. In Proceedings of the 12th International Conference on High Performance Computing, HiPC'05, page 7--18, Berlin, Heidelberg, 2005. Springer-Verlag.

Digital Library

[28]

Danny Hendler, Itai Incze, Nir Shavit, and Moran Tzafrir. Flat Combining and the Synchronization-Parallelism Tradeoff. In Proceedings of the Twenty-Second Annual ACM Symposium on Parallelism in Algorithms and Architectures, SPAA '10, page 355--364, New York, NY, USA, 2010. Association for Computing Machinery.

[29]

Maurice Herlihy. Wait-Free Synchronization. ACM Trans. Program. Lang. Syst., 13(1):124--149, January 1991.

Digital Library

[30]

Benjamin Hindman, Andy Konwinski, Matei Zaharia, Ali Ghodsi, Anthony D. Joseph, Randy Katz, Scott Shenker, and Ion Stoica. Mesos: A Platform for Fine-Grained Resource Sharing in the Data Center. In Proceedings of the 8th USENIX Conference on Networked Systems Design and Implementation, NSDI'11, page 295--308, USA, 2011. USENIX Association.

[31]

UpScaleDB Inc. UpScaleDB. https://upscaledb.com/.

[32]

Rajendra K Jain, Dah-Ming W Chiu, and William R Hawe. A Quantitative Measure of Fairness and Discrimination for Resource Allocation in Shared Computer System. Eastern Research Laboratory, Digital Equipment Corporation, Hudson, MA, 1984.

[33]

Orran Krieger, Michael Stumm, Ron Unrau, and Jonathan Hanna. A Fair Fast Scalable Reader-Writer Lock. In Proceedings of the 1993 International Conference on Parallel Processing - Volume 02, ICPP '93, page 201--204, USA, 1993. IEEE Computer Society.

[34]

Lawrence Livermore National Laboratory. Mutex variables. https://computing.llnl.gov/tutorials/pthreads, 2017.

[35]

FAL Labs. KyotoCabinet. https://fallabs.com/kyotocabinet/.

[36]

Yossi Lev, Victor Luchangco, and Marek Olszewski. Scalable Reader-Writer Locks. In Proceedings of the Twenty-First Annual Symposium on Parallelism in Algorithms and Architectures, SPAA '09, page 101--110, New York, NY, USA, 2009. Association for Computing Machinery.

[37]

Jean-Pierre Lozi, Florian David, Gaël Thomas, Julia Lawall, and Gilles Muller. Remote Core Locking: Migrating Critical-Section Execution to Improve the Performance of Multithreaded Applications. In Proceedings of the 2012 USENIX Conference on Annual Technical Conference, USENIX ATC'12, page 6, USA, 2012. USENIX Association.

Digital Library

[38]

Jean-Pierre Lozi, Florian David, Gaël Thomas, Julia Lawall, and Gilles Muller. Fast and Portable Locking for Multicore Architectures. ACM Trans. Comput. Syst., 33(4), January 2016.

Digital Library

[39]

Jean-Pierre Lozi, Baptiste Lepers, Justin Funston, Fabien Gaud, Vivien Quéma, and Alexandra Fedorova. The Linux Scheduler: A Decade of Wasted Cores. In Proceedings of the Eleventh European Conference on Computer Systems, EuroSys '16, New York, NY, USA, 2016. Association for Computing Machinery.

[40]

Victor Luchangco, Dan Nussbaum, and Nir Shavit. A Hierarchical CLH Queue Lock. In Euro-Par 2006 Parallel Processing, pages 801--810, Berlin, Heidelberg, 2006. Springer Berlin Heidelberg.

Digital Library

[41]

Jonathan Mace, Peter Bodik, Madanlal Musuvathi, Rodrigo Fonseca, and Krishnan Varadarajan. 2DFQ: Two-Dimensional Fair Queuing for Multi-Tenant Cloud Services. In Proceedings of the 2016 ACM SIGCOMM Conference, SIGCOMM '16, page 144--159, New York, NY, USA, 2016. Association for Computing Machinery.

Digital Library

[42]

Peter S. Magnusson, Anders Landin, and Erik Hagersten. Queue Locks on Cache Coherent Multiprocessors. In Proceedings of the 8th International Symposium on Parallel Processing, page 165--171, USA, 1994. IEEE Computer Society.

[43]

John M. Mellor-Crummey and Michael L. Scott. Algorithms for Scalable Synchronization on Shared-Memory Multiprocessors. ACM Trans. Comput. Syst., 9(1):21--65, February 1991.

Digital Library

[44]

John M. Mellor-Crummey and Michael L. Scott. Scalable Reader-Writer Synchronization for Shared-Memory Multiprocessors. SIGPLAN Not., 26(7):106--113, April 1991.

[45]

John M. Mellor-Crummey and Michael L. Scott. Synchronization without Contention. SIGARCH Comput. Archit. News, 19(2):269--278, April 1991.

Digital Library

[46]

Changwoo Min, Sanidhya Kashyap, Steffen Maass, Woonhak Kang, and Taesoo Kim. Understanding Manycore Scalability of File Systems. In Proceedings of the 2016 USENIX Conference on Usenix Annual Technical Conference, USENIX ATC '16, page 71--85, USA, 2016. USENIX Association.

[47]

M. Oh, J. Eom, J. Yoon, J. Y. Yun, S. Kim, and H. Y. Yeom. Performance Optimization for All Flash Scale-Out Storage. In 2016 IEEE International Conference on Cluster Computing (CLUSTER), pages 316--325, Sep. 2016.

[48]

Yoshihiro Oyama, Kenjiro Taura, and Akinori Yonezawa. Executing parallel programs with synchronization bottlenecks efficiently. In Proceedings of the International Workshop on Parallel and Distributed Computing for Symbolic and Irregular Applications, volume 16, page 95. Citeseer, 1999.

[49]

Zoran Radovic and Erik Hagersten. Hierarchical Backoff Locks for Nonuniform Communication Architectures. In Proceedings of the 9th International Symposium on High-Performance Computer Architecture, HPCA '03, page 241, USA, 2003. IEEE Computer Society.

[50]

Robert Ricci, Eric Eide, and CloudLab Team. Introducing CloudLab: Scientific infrastructure for Advancing Cloud Architectures and Applications. ; login:: the magazine of USENIX & SAGE, 39(6):36--38, 2014.

[51]

Jeff Roberson. ULE: A Modern Scheduler for FreeBSD. In BSDCon, 2003.

[52]

Michael L. Scott. Shared-Memory Synchronization. Morgan & Claypool Publishers, 2013.

[53]

L. Sha, R. Rajkumar, and J. P. Lehoczky. Priority Inheritance Protocols: an Approach to Real-Time Synchronization. IEEE Transactions on Computers, 39(9):1175--1185, Sep. 1990.

Digital Library

[54]

David Shue, Michael J. Freedman, and Anees Shaikh. Performance Isolation and Fairness for Multi-Tenant Cloud Storage. In Proceedings of the 10th USENIX Conference on Operating Systems Design and Implementation, OSDI'12, page 349--362, USA, 2012. USENIX Association.

[55]

Ben Verghese, Anoop Gupta, and Mendel Rosenblum. Performance Isolation: Sharing and Isolation in Shared-Memory Multiprocessors. SIGPLAN Not., 33(11):181--192, October 1998.

Digital Library

[56]

Axel Wagner. ext4: Mysterious "No space left on device"-errors. https://blog.merovius.de/2013/10/20/ext4-mysterious-no-space-left-on.html, 2018.

[57]

Carl A. Waldspurger and William E. Weihl. Lottery Scheduling: Flexible Proportional-Share Resource Management. In Proceedings of the 1st USENIX Conference on Operating Systems Design and Implementation, OSDI '94, page 1--es, USA, 1994. USENIX Association.

[58]

David Wentzlaff and Anant Agarwal. Factored Operating Systems (fos): The Case for a Scalable Operating System for Multicores. SIGOPS Oper. Syst. Rev., 43(2):76--85, April 2009.

Digital Library

[59]

David Wentzlaff, Charles Gruenwald, Nathan Beckmann, Kevin Modzelewski, Adam Belay, Lamia Youseff, Jason Miller, and Anant Agarwal. An Operating System for Multicore and Clouds: Mechanisms and Implementation. In Proceedings of the 1st ACM Symposium on Cloud Computing, SoCC '10, page 3--14, New York, NY, USA, 2010. Association for Computing Machinery.

[60]

Matei Zaharia, Benjamin Hindman, Andy Konwinski, Ali Ghodsi, Anthony D. Joesph, Randy Katz, Scott Shenker, and Ion Stoica. The Datacenter Needs an Operating System. In Proceedings of the 3rd USENIX Conference on Hot Topics in Cloud Computing, HotCloud'11, page 17, USA, 2011. USENIX Association.

Digital Library

[61]

A. Zhong, H. Jin, S. Wu, X. Shi, and W. Gen. Optimizing Xen Hypervisor by Using Lock-Aware Scheduling. In 2012 Second International Conference on Cloud and Green Computing, pages 31--38, Nov 2012.

Digital Library

Cited By

Park SCalciu IKim TKashyap SAngel SKasikci BKohler E(2021)Contextual concurrency controlProceedings of the Workshop on Hot Topics in Operating Systems10.1145/3458336.3465279(167-174)Online publication date: 1-Jun-2021
https://dl.acm.org/doi/10.1145/3458336.3465279
Panda APanwar ABasu A(2021)nuKSM: NUMA-aware Memory De-duplication on Multi-socket ServersProceedings of the 30th International Conference on Parallel Architectures and Compilation Techniques10.1109/PACT52795.2021.00026(258-273)Online publication date: 26-Sep-2021
https://dl.acm.org/doi/10.1109/PACT52795.2021.00026
Ren YMin CKannan SLu SHowell J(2020)CrossFSProceedings of the 14th USENIX Conference on Operating Systems Design and Implementation10.5555/3488766.3488774(137-154)Online publication date: 4-Nov-2020
https://dl.acm.org/doi/10.5555/3488766.3488774

Recommendations

Execution privatization for scheduler-oblivious concurrent programs
OOPSLA '12

Making multithreaded execution less non-deterministic is a promising solution to address the difficulty of concurrent programming plagued by the non-deterministic thread scheduling. In fact, a vast category of concurrent programs are scheduler-oblivious:...
Execution privatization for scheduler-oblivious concurrent programs
OOPSLA '12: Proceedings of the ACM international conference on Object oriented programming systems languages and applications

Making multithreaded execution less non-deterministic is a promising solution to address the difficulty of concurrent programming plagued by the non-deterministic thread scheduling. In fact, a vast category of concurrent programs are scheduler-oblivious:...
Contention-aware scheduler: unlocking execution parallelism in multithreaded java programs
OOPSLA '08: Proceedings of the 23rd ACM SIGPLAN conference on Object-oriented programming systems languages and applications

In multithreaded programming, locks are frequently used as a mechanism for synchronization. Because today's operating systems do not consider lock usage as a scheduling criterion, scheduling decisions can be unfavorable to multithreaded applications, ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

EuroSys '20: Proceedings of the Fifteenth European Conference on Computer Systems

April 2020

49 pages

ISBN:9781450368827

DOI:10.1145/3342195

General Chairs:
Angelos Bilas
University of Crete and FORTH-ICS
,
Kostas Magoutis
University of Crete and FORTH-ICS
,
Evangelos Markatos
University of Crete and FORTH-ICS
,
Program Chairs:
Dejan Kostic
KTH Royal Institute of Technology, Sweden
,
Margo Seltzer
The University of British Columbia, Canada

Copyright © 2020 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGOPS: ACM Special Interest Group on Operating Systems

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 17 April 2020

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Research-article

Funding Sources

National Science Foundation
Department of Energy

Conference

EuroSys '20

Sponsor:

SIGOPS

EuroSys '20: Fifteenth EuroSys Conference 2020

April 27 - 30, 2020

Heraklion, Greece

Acceptance Rates

EuroSys '20 Paper Acceptance Rate 43 of 234 submissions, 18%;

Overall Acceptance Rate 241 of 1,308 submissions, 18%

Upcoming Conference

EuroSys '25

Sponsor:
sigops

Twentieth European Conference on Computer Systems

March 30 - April 3, 2025

Rotterdam , Netherlands

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

3
Total Citations
View Citations
594
Total Downloads

Downloads (Last 12 months)118
Downloads (Last 6 weeks)14

Reflects downloads up to 11 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Park SCalciu IKim TKashyap SAngel SKasikci BKohler E(2021)Contextual concurrency controlProceedings of the Workshop on Hot Topics in Operating Systems10.1145/3458336.3465279(167-174)Online publication date: 1-Jun-2021
https://dl.acm.org/doi/10.1145/3458336.3465279
Panda APanwar ABasu A(2021)nuKSM: NUMA-aware Memory De-duplication on Multi-socket ServersProceedings of the 30th International Conference on Parallel Architectures and Compilation Techniques10.1109/PACT52795.2021.00026(258-273)Online publication date: 26-Sep-2021
https://dl.acm.org/doi/10.1109/PACT52795.2021.00026
Ren YMin CKannan SLu SHowell J(2020)CrossFSProceedings of the 14th USENIX Conference on Operating Systems Design and Implementation10.5555/3488766.3488774(137-154)Online publication date: 4-Nov-2020
https://dl.acm.org/doi/10.5555/3488766.3488774

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents