Snapshot based synchronization: A fast replacement for Hand-over-Hand locking

E. Gilad, T.A. Brown, M. Oskin, Y. Etsion, in:, Springer, 2018, pp. 465–479.

Download
OA 665.37 KB

Conference Paper | Published | English
Author
; ; ;
Department
Series Title
LNCS
Abstract
Concurrent accesses to shared data structures must be synchronized to avoid data races. Coarse-grained synchronization, which locks the entire data structure, is easy to implement but does not scale. Fine-grained synchronization can scale well, but can be hard to reason about. Hand-over-hand locking, in which operations are pipelined as they traverse the data structure, combines fine-grained synchronization with ease of use. However, the traditional implementation suffers from inherent overheads. This paper introduces snapshot-based synchronization (SBS), a novel hand-over-hand locking mechanism. SBS decouples the synchronization state from the data, significantly improving cache utilization. Further, it relies on guarantees provided by pipelining to minimize synchronization that requires cross-thread communication. Snapshot-based synchronization thus scales much better than traditional hand-over-hand locking, while maintaining the same ease of use.
Publishing Year
Date Published
2018-08-01
Acknowledgement
Trevor Brown was supported in part by the ISF (grants 2005/17 & 1749/14) and by a NSERC post-doctoral fellowship.
Volume
11014
Page
465 - 479
Conference
Euro-Par: European Conference on Parallel Processing
Conference Location
Turin, Italy
Conference Date
2018-08-27 – 2018-08-31
ISSN
IST-REx-ID

Cite this

Gilad E, Brown TA, Oskin M, Etsion Y. Snapshot based synchronization: A fast replacement for Hand-over-Hand locking. In: Vol 11014. Springer; 2018:465-479. doi:10.1007/978-3-319-96983-1_33
Gilad, E., Brown, T. A., Oskin, M., & Etsion, Y. (2018). Snapshot based synchronization: A fast replacement for Hand-over-Hand locking (Vol. 11014, pp. 465–479). Presented at the Euro-Par: European Conference on Parallel Processing, Turin, Italy: Springer. https://doi.org/10.1007/978-3-319-96983-1_33
Gilad, Eran, Trevor A Brown, Mark Oskin, and Yoav Etsion. “Snapshot Based Synchronization: A Fast Replacement for Hand-over-Hand Locking,” 11014:465–79. Springer, 2018. https://doi.org/10.1007/978-3-319-96983-1_33.
E. Gilad, T. A. Brown, M. Oskin, and Y. Etsion, “Snapshot based synchronization: A fast replacement for Hand-over-Hand locking,” presented at the Euro-Par: European Conference on Parallel Processing, Turin, Italy, 2018, vol. 11014, pp. 465–479.
Gilad E, Brown TA, Oskin M, Etsion Y. 2018. Snapshot based synchronization: A fast replacement for Hand-over-Hand locking. Euro-Par: European Conference on Parallel Processing, LNCS, vol. 11014. 465–479.
Gilad, Eran, et al. Snapshot Based Synchronization: A Fast Replacement for Hand-over-Hand Locking. Vol. 11014, Springer, 2018, pp. 465–79, doi:10.1007/978-3-319-96983-1_33.
Main File(s)
File Name
Access Level
OA Open Access
Last Uploaded
2019-02-12T07:40:40Z


Export

Marked Publications

Open Data IST Research Explorer

Search this title in

Google Scholar