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 |
| Summary: | 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. |
|---|