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

Author(s): Gilad, Eran; Brown, Trevor; Oskin, Mark; Etsion, Yoav
Title: Snapshot based synchronization: A fast replacement for Hand-over-Hand locking
Title Series: LNCS
Affiliation IST Austria
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.
Keywords: data structures; Synchronization; Concurrency control; Distributed computer systems; Cache utilization; Coarse-grained; Concurrent access; Ease-of-use; Fine grained; Locking mechanism; Shared data structure; Synchronization state; Locks (fasteners)
Conference Title: Euro-Par: European Conference on Parallel Processing
Volume: 11014
Conference Dates: August 27 - 31, 2018
Conference Location: Turin, Italy
ISBN: 03029743 (ISSN); 9783319969824 (ISBN)
Publisher: Springer  
Date Published: 2018-08-01
Start Page: 465
End Page: 479
DOI: 10.1007/978-3-319-96983-1_33
Notes: Trevor Brown was supported in part by the ISF (grants 2005/17 & 1749/14) and by a NSERC post-doctoral fellowship.
Open access: no
IST Austria Authors
  1. Trevor Brown
    2 Brown
Related IST Austria Work