Concurrent binary search trees: Design and optimizations

Over the last decade processor clock speeds have hit a wall but the demand for performance improvements has continued to grow. So there has been a major shift towards multi-core and many-core processors. This motivates the design of concurrent data structures. In such a data structure, multiple processes may need to operate on overlapping regions of the data structure simultaneously.;Designing a concurrent data structure is far more challenging than its sequential counterpart because processes executing concurrently may interleave in many ways. For all such interleavings, a concurrent data structure should manage the contention among the processes in such a way that all operations complete correctly and leave the data structure in a valid state. Concurrent algorithms may be blocking or non-blocking. Blocking algorithms are usually designed using locks. While a process is holding a lock, it blocks other processes from accessing the portion of the data structure protected by the lock. In a non-blocking algorithm, a suspended process will not prevent other processes from making progress. This is usually achieved by a concept called helping, where a process always leaves enough information about its operation, so that even if it gets suspended, another process (which conflicts with the suspended process) can help finish the operation without waiting for the suspended process to resume.;In this work, we present a blocking and a non-blocking algorithm for concurrent manipulation of a binary search tree in an asynchronous shared memory system. Binary search trees are ubiquitous in computer science and are commonly used to implement dictionary abstract data type. We also provide a general optimization technique to improve performance of existing concurrent binary search trees. In this approach processes can recover from failures due to contention more efficiently using local recovery. Our approach is sufficiently general in the sense that it can be applied to a variety of concurrent binary search trees based on both blocking and non-blocking approaches. Moreover, we also present several techniques to make search operations on such binary search trees terminate in a finite number of steps. Our techniques ensures that search operations never have to restart due to a failure.;Experiments indicate that our algorithms perform best in most cases. And our optimization technique improves performance of our algorithms and other existing algorithms.