Interrupting snapshots and the Java[superscript TM] size() method
The Java[superscript TM] developers kit requires a size() operation for all objects, tracking the number of elements in the object. Unfortunately, the best known solution, available in the Java concurrency package, has a blocking concurrent implementation that does not scale. This paper presents a h...
| Main Authors: | , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Elsevier
2016
|
| Online Access: | http://hdl.handle.net/1721.1/101051 https://orcid.org/0000-0002-4552-2414 |
| _version_ | 1826210151944683520 |
|---|---|
| author | Afek, Yehuda Tzafrir, Moran 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 Tzafrir, Moran Shavit, Nir N. |
| author_sort | Afek, Yehuda |
| collection | MIT |
| description | The Java[superscript TM] developers kit requires a size() operation for all objects, tracking the number of elements in the object. Unfortunately, the best known solution, available in the Java concurrency package, has a blocking concurrent implementation that does not scale. This paper presents a highly scalable wait-free implementation of a concurrent size() operation based on a new lock-free interrupting snapshots algorithm.
The key idea behind the new algorithm is to allow snapshot scan methods to interrupt each other until they agree on a shared linearization point with respect to update methods. This contrasts sharply with past approaches to the classical atomic snapshot problem, that have had threads coordinate the collecting of a shared global view. As we show empirically, the new algorithm scales well, significantly outperforming existing implementations. |
| first_indexed | 2024-09-23T14:44:22Z |
| format | Article |
| id | mit-1721.1/101051 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T14:44:22Z |
| publishDate | 2016 |
| publisher | Elsevier |
| record_format | dspace |
| spelling | mit-1721.1/1010512022-09-29T10:18:10Z Interrupting snapshots and the Java[superscript TM] size() method Interrupting snapshots and the Java[superscript TM] size method Afek, Yehuda Tzafrir, Moran Shavit, Nir N. Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Shavit, Nir N. The Java[superscript TM] developers kit requires a size() operation for all objects, tracking the number of elements in the object. Unfortunately, the best known solution, available in the Java concurrency package, has a blocking concurrent implementation that does not scale. This paper presents a highly scalable wait-free implementation of a concurrent size() operation based on a new lock-free interrupting snapshots algorithm. The key idea behind the new algorithm is to allow snapshot scan methods to interrupt each other until they agree on a shared linearization point with respect to update methods. This contrasts sharply with past approaches to the classical atomic snapshot problem, that have had threads coordinate the collecting of a shared global view. As we show empirically, the new algorithm scales well, significantly outperforming existing implementations. European Union (Project VELOX Grant FP7-ICT-2007-1) 2016-02-02T01:48:03Z 2016-02-02T01:48:03Z 2012-04 2012-02 Article http://purl.org/eprint/type/JournalArticle 07437315 1096-0848 http://hdl.handle.net/1721.1/101051 Afek, Yehuda, Nir Shavit, and Moran Tzafrir. “Interrupting Snapshots and the Java Size Method.” Journal of Parallel and Distributed Computing 72, no. 7 (July 2012): 880–888. https://orcid.org/0000-0002-4552-2414 en_US http://dx.doi.org/10.1016/j.jpdc.2012.03.007 Journal of Parallel and Distributed Computing Creative Commons Attribution-NonCommercial-NoDerivs License http://creativecommons.org/licenses/by-nc-nd/4.0/ application/pdf Elsevier MIT web domain |
| spellingShingle | Afek, Yehuda Tzafrir, Moran Shavit, Nir N. Interrupting snapshots and the Java[superscript TM] size() method |
| title | Interrupting snapshots and the Java[superscript TM] size() method |
| title_full | Interrupting snapshots and the Java[superscript TM] size() method |
| title_fullStr | Interrupting snapshots and the Java[superscript TM] size() method |
| title_full_unstemmed | Interrupting snapshots and the Java[superscript TM] size() method |
| title_short | Interrupting snapshots and the Java[superscript TM] size() method |
| title_sort | interrupting snapshots and the java superscript tm size method |
| url | http://hdl.handle.net/1721.1/101051 https://orcid.org/0000-0002-4552-2414 |
| work_keys_str_mv | AT afekyehuda interruptingsnapshotsandthejavasuperscripttmsizemethod AT tzafrirmoran interruptingsnapshotsandthejavasuperscripttmsizemethod AT shavitnirn interruptingsnapshotsandthejavasuperscripttmsizemethod |