Lock-free internal binary search trees with memory management

Abstract

The current design trend in microprocessor systems is to add more CPU cores thus increasing parallel execution resources. Although this allows many sequential programs to be run in parallel, it can be challenging to use multiple cores to speed up a single program. Concurrent algorithms have traditionally used mutual exclusion to synchronise access to data structures shared between executing threads. This limits access to the data structure to a single thread at any one time. The pitfalls of using mutual exclusion are well known, deadlock, livelock, convoying and priority inversion to name a few. Mutual exclusion inherently limits parallelism. Non-blocking algorithms are optimistic and can enable much greater levels of parallelism by allowing all threads access to shared data concurrently, resolving contention when detected. This thesis presents a new non-blocking internal binary search tree algorithm. Previous binary search tree algorithms either rely on mutual exclusion or require modi- fications to the tree structure that result in suboptimal memory use. The new algorithm does not suffer from these limitations and closely mirrors the standard implementation of a sequential binary tree. Furthermore, the new algorithm is based on standard atomic instructions which comprise single-word reads, writes and compare-and-swap. The new algorithm is also informally proven to be lock-free and linearisable. Extensive experimental measurement and analysis demonstrates that the new internal binary search tree algorithm has a higher throughput than previously published concurrent dynamic search structure algorithms for a range of workload patterns and data structure sizes. Tests were initially performed without memory management and then the effect of applying hazard pointer memory management was analysed and shown to impose minimal overhead. The memory footprint, per key, is shown to be significantly smaller than that of the other algorithms. Finally, a new technique for avoiding the ABA problem in descriptor-based concurrent algorithms is described and used to ensure all retired objects can be reclaimed.