Semantic Lock: Synchronization Based on the Analysis of the Operation Conflict Graph
For developers of concurrent data structures, this provides a more flexible synchronization mechanism, though the evaluation is limited to toy examples and a single augmentation.
The paper introduces SemanticLock, a lock based on operation conflict graphs, generalizing read-write locks. It shows effectiveness in a toy array data structure and by augmenting ConcurrentHashMap with long-running operations.
This paper presents a new lock, SemanticLock, based on the conflict graph between operations. We can consider it a generalization of a read-write lock where conflicts exist between write operations and all other operations. We demonstrate the effectiveness of our lock in two applications. In the first, we design a toy data structure: an array supporting point queries and different range queries. In the second, potentially of greater interest, we augment an existing concurrent data structure, ConcurrentHashMap, with additional long-running operations.