Advanced Concurrency Techniques for Concurrent Data Structures
Concurrent algorithms have gained importance as multi-core machines have become more ubiquitous. Several techniques are employed to enable the construction of such algorithms. We present algorithms for the Group Mutual Exclusion (GME) problem which can be used as an advanced concurrency technique to increase the performance of software built on concurrent data structures. The group mutual exclusion (GME) problem is a generalization of the classical mutual exclusion problem in which every critical section is associated with a type or session. Critical sections belonging to the same session can execute concurrently, whereas critical sections belonging to different sessions must be executed serially. The well-known read-write mutual exclusion problem is a special case of the group mutual exclusion problem. We present a new GME algorithm for an asynchronous shared-memory system under the Cache-Coherent model that, in addition to satisfying lockout freedom, bounded exit and concurrent entering properties, has O(1) step-complexity when the system contains no conflicting requests as well as O(1) space-complexity per GME object when the system contains sufficient number of GME objects. We also present a GME algorithm for the Distributed Shared Memory model that satisfies above properties and has optimal Remote Memory-Reference complexity. To the best of our knowledge, no existing GME algorithm has O(1) step-complexity for concurrent entering for either model. The Remote-Memory-Reference complexity of a request for cache-coherent model is only O(c˙) in the amortized case, where ˙c denotes the point contention of the request. Experiments indicate that our GME algorithm vastly outperforms well-known GME algorithms in most, if not all, cases. We also present a lock-based concurrent algorithm for a strictly-balanced red black tree data structure. Our algorithm can be implemented on hardware directly without requiring any additional system support such as transactional memory. We also make use of several optimizations to improve the performance of our tree. Our experimental results indicate that our lock-based algorithm for a strictly balanced binary search tree outperforms other relaxed balanced trees for read-dominated workloads.