Pessimistic Software Lock-Elision
Read-write locks are one of the most prevalent lock forms in concurrent applications because they allow read accesses to locked code to proceed in parallel. However, they do not offer any parallelism between reads and writes. This paper introduces pessimistic lock-elision (PLE), a new approach for...
| Main Authors: | , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Springer-Verlag
2014
|
| Online Access: | http://hdl.handle.net/1721.1/90880 https://orcid.org/0000-0002-4552-2414 |
| _version_ | 1826211329848901632 |
|---|---|
| author | Afek, Yehuda Matveev, Alexander Shavit, Nir N. |
| author2 | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science |
| author_facet | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Afek, Yehuda Matveev, Alexander Shavit, Nir N. |
| author_sort | Afek, Yehuda |
| collection | MIT |
| description | Read-write locks are one of the most prevalent lock forms in concurrent applications because they allow read accesses to locked code to proceed in parallel. However, they do not offer any parallelism between reads and writes.
This paper introduces pessimistic lock-elision (PLE), a new approach for non-speculatively replacing read-write locks with pessimistic (i.e. non-aborting) software transactional code that allows read-write concurrency even for contended code and even if the code includes system calls. On systems with hardware transactional support, PLE will allow failed transactions, or ones that contain system calls, to preserve read-write concurrency.
Our PLE algorithm is based on a novel encounter-order design of a fully pessimistic STM system that in a variety of benchmarks spanning from counters to trees, even when up to 40% of calls are mutating the locked structure, provides up to 5 times the performance of a state-of-the-art read-write lock. |
| first_indexed | 2024-09-23T15:04:11Z |
| format | Article |
| id | mit-1721.1/90880 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T15:04:11Z |
| publishDate | 2014 |
| publisher | Springer-Verlag |
| record_format | dspace |
| spelling | mit-1721.1/908802022-09-29T12:25:26Z Pessimistic Software Lock-Elision Afek, Yehuda Matveev, Alexander Shavit, Nir N. Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Shavit, Nir N. Read-write locks are one of the most prevalent lock forms in concurrent applications because they allow read accesses to locked code to proceed in parallel. However, they do not offer any parallelism between reads and writes. This paper introduces pessimistic lock-elision (PLE), a new approach for non-speculatively replacing read-write locks with pessimistic (i.e. non-aborting) software transactional code that allows read-write concurrency even for contended code and even if the code includes system calls. On systems with hardware transactional support, PLE will allow failed transactions, or ones that contain system calls, to preserve read-write concurrency. Our PLE algorithm is based on a novel encounter-order design of a fully pessimistic STM system that in a variety of benchmarks spanning from counters to trees, even when up to 40% of calls are mutating the locked structure, provides up to 5 times the performance of a state-of-the-art read-write lock. National Science Foundation (U.S.) (Grant 1217921) 2014-10-10T13:09:02Z 2014-10-10T13:09:02Z 2012 Article http://purl.org/eprint/type/ConferencePaper 978-3-642-33650-8 978-3-642-33651-5 0302-9743 1611-3349 http://hdl.handle.net/1721.1/90880 Afek, Yehuda, Alexander Matveev, and Nir Shavit. “Pessimistic Software Lock-Elision.” Lecture Notes in Computer Science (2012): 297–311. https://orcid.org/0000-0002-4552-2414 en_US http://dx.doi.org/10.1007/978-3-642-33651-5_21 Distributed Computing Creative Commons Attribution-Noncommercial-Share Alike http://creativecommons.org/licenses/by-nc-sa/4.0/ application/pdf Springer-Verlag Other univ. web domain |
| spellingShingle | Afek, Yehuda Matveev, Alexander Shavit, Nir N. Pessimistic Software Lock-Elision |
| title | Pessimistic Software Lock-Elision |
| title_full | Pessimistic Software Lock-Elision |
| title_fullStr | Pessimistic Software Lock-Elision |
| title_full_unstemmed | Pessimistic Software Lock-Elision |
| title_short | Pessimistic Software Lock-Elision |
| title_sort | pessimistic software lock elision |
| url | http://hdl.handle.net/1721.1/90880 https://orcid.org/0000-0002-4552-2414 |
| work_keys_str_mv | AT afekyehuda pessimisticsoftwarelockelision AT matveevalexander pessimisticsoftwarelockelision AT shavitnirn pessimisticsoftwarelockelision |