Abstract
The Java\(^{\mbox{\tiny TM}}\) developers kit requires a size() operation for all objects. 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 for the classical atomic snapshot problem. This is perhaps the first example of the potential benefit from using atomic snapshots in real industrial code (the concurrency package is currently deployed on over 10 million desktops).
The key idea behind the new algorithm is to allow snapshot scans to interrupt each other until they agree on a shared linearization point with respect to updates, rather than trying, as was done in the past, to have them coordinate the collecting of a shared global view. As we show, the new algorithm scales well, significantly outperforming existing implementations.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Afek, Y., Dolev, D., Attiya, H., Gafni, E., Merritt, M., Shavit, N.: Atomic snapshots of shared memory. In: PODC, pp. 1–13 (1990)
Anderson, J.H.: Multi-writer composite registers. Distrib. Comput. 7(4), 175–195 (1994)
Attiya, H., Rachman, O.: Atomic snapshots in o (n log n) operations. SIAM J. Comput. 27(2), 319–340 (1998)
Riany, Y., Shavit, N., Touitou, D.: Towards a practical snapshot algorithm. In: ISTCS, pp. 121–129 (1995)
Kirousis, L.M., Spirakis, P.G., Tsigas, P.: Simple atomic snapshots: A linear complexity solution with unbounded time-stamps. In: Dehne, F., Fiala, F., Koczkodaj, W.W. (eds.) ICCI 1991. LNCS, vol. 497, pp. 582–587. Springer, Heidelberg (1991)
Herlihy, M.: Wait-free synchronization. ACM Trans. Program. Lang. Syst. 13(1), 124–149 (1991)
Herlihy, M.P., Wing, J.M.: Linearizability: a correctness condition for concurrent objects. ACM Transactions on Programming Languages and Systems (TOPLAS) 12(3), 463–492 (1990)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2009 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Afek, Y., Shavit, N., Tzafrir, M. (2009). Interrupting Snapshots and the Java\(^{\mbox{\tiny TM}}\) Size() Method. In: Keidar, I. (eds) Distributed Computing. DISC 2009. Lecture Notes in Computer Science, vol 5805. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-04355-0_11
Download citation
DOI: https://doi.org/10.1007/978-3-642-04355-0_11
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-04354-3
Online ISBN: 978-3-642-04355-0
eBook Packages: Computer ScienceComputer Science (R0)