Mutable locks: Combining the best of spin and sleep locks
Corresponding Author
Romolo Marotta
DIAG, Sapienza, University of Rome, Rome, Italy
Correspondence
Romolo Marotta and Pierangelo Di Sanzo, DIAG, Sapienza, University of Rome, Italy.
Emails: [email protected] (R. M.) and [email protected] (P. D. S)
Francesco Quaglia, DICII, Tor Vergata University, Rome, Italy.
Email: [email protected]
Search for more papers by this authorDavide Tiriticco
DIAG, Sapienza, University of Rome, Rome, Italy
Search for more papers by this authorCorresponding Author
Pierangelo Di Sanzo
DIAG, Sapienza, University of Rome, Rome, Italy
Correspondence
Romolo Marotta and Pierangelo Di Sanzo, DIAG, Sapienza, University of Rome, Italy.
Emails: [email protected] (R. M.) and [email protected] (P. D. S)
Francesco Quaglia, DICII, Tor Vergata University, Rome, Italy.
Email: [email protected]
Search for more papers by this authorAlessandro Pellegrini
DIAG, Sapienza, University of Rome, Rome, Italy
Search for more papers by this authorCorresponding Author
Francesco Quaglia
DICII, Tor Vergata University, Rome, Italy
Correspondence
Romolo Marotta and Pierangelo Di Sanzo, DIAG, Sapienza, University of Rome, Italy.
Emails: [email protected] (R. M.) and [email protected] (P. D. S)
Francesco Quaglia, DICII, Tor Vergata University, Rome, Italy.
Email: [email protected]
Search for more papers by this authorCorresponding Author
Romolo Marotta
DIAG, Sapienza, University of Rome, Rome, Italy
Correspondence
Romolo Marotta and Pierangelo Di Sanzo, DIAG, Sapienza, University of Rome, Italy.
Emails: [email protected] (R. M.) and [email protected] (P. D. S)
Francesco Quaglia, DICII, Tor Vergata University, Rome, Italy.
Email: [email protected]
Search for more papers by this authorDavide Tiriticco
DIAG, Sapienza, University of Rome, Rome, Italy
Search for more papers by this authorCorresponding Author
Pierangelo Di Sanzo
DIAG, Sapienza, University of Rome, Rome, Italy
Correspondence
Romolo Marotta and Pierangelo Di Sanzo, DIAG, Sapienza, University of Rome, Italy.
Emails: [email protected] (R. M.) and [email protected] (P. D. S)
Francesco Quaglia, DICII, Tor Vergata University, Rome, Italy.
Email: [email protected]
Search for more papers by this authorAlessandro Pellegrini
DIAG, Sapienza, University of Rome, Rome, Italy
Search for more papers by this authorCorresponding Author
Francesco Quaglia
DICII, Tor Vergata University, Rome, Italy
Correspondence
Romolo Marotta and Pierangelo Di Sanzo, DIAG, Sapienza, University of Rome, Italy.
Emails: [email protected] (R. M.) and [email protected] (P. D. S)
Francesco Quaglia, DICII, Tor Vergata University, Rome, Italy.
Email: [email protected]
Search for more papers by this authorSummary
In this article, we present mutable locks, a synchronization construct with the same semantic of traditional locks (such as spin locks or sleep locks), but with a self-tuned optimized trade-off between responsiveness and CPU-time usage during threads' wait phases. Mutable locks tackle the need for efficient synchronization supports in the era of multicore machines, where the run-time performance should be optimized while reducing resource usage. This goal should be achieved with no intervention by the programmers. Our proposal is intended for exploitation in generic concurrent applications, where scarce or no knowledge is available about the underlying software/hardware stack and the workload. This is an adverse scenario for static choices between spinning and sleeping, which is tackled by our mutable locks thanks to their hybrid waiting phase and self-tuning capabilities.
REFERENCES
- 1Held J. “Single-chip cloud computer”, an IA Tera-scale research processor. In: MR Guarracino, F Vivien, JL Träff, et al., eds. Euro-Par 2010 Parallel Processing Workshops. Berlin, Heidelberg: Springer Berlin Heidelberg; 2011: 85.
10.1007/978-3-642-21878-1_11 Google Scholar
- 2Dice D, Shalev O, Shavit N. Transactional locking II. Paper presented at: DISC'06. 2006; 194-208; Berlin, Heidelberg: Springer-Verlag.
- 3McKenney PE, Slingwine JD. Read-Copy Update: Using Execution History to Solve Concurrency Problems. Proceedings of the 10th Parallel and Distributed Computing and Systems Conference. Las Vegas, NV: ACTA Press; 1998: 509-518.
- 4Dijkstra EW. Solution of a problem in concurrent programming control. Commun. ACM. 1965; 8(9): 569. https://doi.org/10.1145/365559.365617.
- 5Lamport L. A new solution of Dijkstra's concurrent programming problem. Commun. ACM. 1974; 17(8): 453-455. https://doi.org/10.1145/361082.361093.
- 6Kruskal CP, Rudolph L, Snir M. Efficient synchronization of multiprocessors with shared memory. ACM Trans. Program. Lang Syst. 1988; 10(4): 579-601. https://doi.org/10.1145/48022.48024.
- 7Rudolph L, Segall Z. Dynamic decentralized cache schemes for MIMD parallel processors. Paper presented at: ISCA '84. Association for Computing Machinery; 1984; 340-347; New York, NY.
- 8Anderson TE. The performance of spin lock alternatives for shared-memory multiprocessors. IEEE Trans. Parallel Distrib. Syst. 1990; 1(1): 6-16. https://doi.org/10.1109/71.80120.
10.1109/71.80120 Google Scholar
- 9Scott ML. Shared-memory synchronization. Synth Lect Comput Architec. 2013; 8(2): 1-221. https://doi.org/10.2200/S00499ED1V01Y201304CAC023.
10.2200/S00499ED1V01Y201304CAC023 Google Scholar
- 10Mellor-Crummey JM, Scott ML. Algorithms for scalable synchronization on shared-memory multiprocessors. ACM Trans. Comput. Syst. 1991; 9(1): 21-65. https://doi.org/10.1145/103727.103729.
- 11 IEEE, The Open Group. POSIX.1-2017 https://pubs.opengroup.org/onlinepubs/9699919799/; 2018.
- 12 Microsoft. Windows API Index https://docs.microsoft.com/en-us/windows/win32/apiindex; 2019.
- 13 Free Software Foundation. GNU C Library https://www.gnu.org/software/libc/; 2019.
- 14Karlin AR, Li K, Manasse MS, Owicki S. Empirical studies of competitve spinning for a shared-memory multiprocessor. SIGOPS Oper. Syst.Rev. 1991; 25(5): 41-55. https://doi.org/10.1145/121133.286599.
10.1145/121133.286599 Google Scholar
- 15Lim B-H, Agarwal A. Waiting algorithms for synchronization in large-scale multiprocessors. ACM Trans. Comput. Syst. 1993; 11(3): 253-294. https://doi.org/10.1145/152864.152869.
- 16Lim B-H, Agarwal A. Reactive synchronization algorithms for multiprocessors. SIGPLAN Not. 1994; 29(11): 25-35. https://doi.org/10.1145/195470.195490.
10.1145/195470.195490 Google Scholar
- 17Eastep J, Wingate D, Santambrogio MD, Agarwal A. Smartlocks: lock acquisition scheduling for self-aware synchronization. Paper presented at: ICAC '10; 2010;215-224; New York, NY: ACM.
- 18Antić J, Chatzopoulos G, Guerraoui R, Trigonakis V. Locking made easy. Paper presented at: Middleware '16; 2016; 20:1-20:14; New York, NY: ACM.
- 19Johnson FR, Stoica R, Ailamaki A, Mowry TC. Decoupling contention management from scheduling. SIGARCH Comput. Archit. News. 2010; 38(1): 117-128. https://doi.org/10.1145/1735970.1736035.
10.1145/1735970.1736035 Google Scholar
- 20Falsafi B, Guerraoui R, Picorel J, Trigonakis V. Unlocking energy. Paper presented at: USENIX Association; 2016;393-406; Denver, CO.
- 21Dice D. Malthusian locks. Paper presented at: EuroSys '17. 2017;314-327; New York, NY: ACM.
- 22Guerraoui R, Guiroux H, Lachaize R, Quéma V, Trigonakis V. Lock-unlock: is that all? A pragmatic analysis of locking in software systems. ACM Trans. Comput. Syst. 2019; 36(1): 1–149. https://doi.org/10.1145/3301501.
- 23Jacobson V. Congestion avoidance and control. Paper presented at: SIGCOMM '88. 1988;314-329; New York, NY: ACM.
- 24Gramoli V. More than you ever wanted to know about synchronization: synchrobench, measuring the impact of the synchronization on concurrent algorithms. Paper presented at: PPoPP 2015; 2015;1-10; New York, NY: ACM.
- 25McVoy L, Staelin C. Lmbench: portable tools for performance analysis. Paper presented at: ATEC '96; 1996;23; Berkeley, CA: USENIX Association.
- 26Rupp C. Upscaledb. https://upscaledb.com; 2019. Accessed November 13, 2019.
- 27Rupp C. Ups Benchmark. https://upscaledb.com/benchmarking.html; 2019. Accessed November 13, 2019.
