Ph.D Thesis

Ph.D StudentBraginsky Anastasia
SubjectMulti-Threaded Coordination Methods for Constructing
Non-Blocking Data Structures
DepartmentDepartment of Computer Science
Supervisor PROF. Erez Petrank
Full Thesis textFull thesis text - English Version


Shared-memory multiprocessors concurrently execute multiple threads of computation that communicate and synchronize through shared memory; typically, via concurrent data structures, whose efficiency is crucial to performance. Furthermore, new challenges arise in designing scalable concurrent data structures that can perform well with an increasing number of concurrent threads. Non-blocking data structures are scalable and provide a progress guarantee. If several threads attempt to concurrently update the structure, it is guaranteed that one of the threads will eventually make progress.

The first goal of this dissertation is to address the design of high-performance, concurrent, non-blocking data structures. Our intention is that the non-blocking data structure will become the primary choice for a concurrent data structure. To this end, we first present a high performance linked list. We extend state-of-the-art lock-free linked lists by building linked lists with special attention to locality of traversals. These linked lists are built of sequences of entries that reside on consecutive chunks of memory. When traversing such lists, subsequent entries typically reside on the same chunk and are thus close to each other, e.g., in same cache line or on the same virtual memory page. The basic component of this construction is a chunk of entries in the list that maintains a minimum and a maximum number of entries. This basic chunk component is an interesting tool on its own and is used to build the other lock-free data structures that we present.

Another high-performance, non-blocking data structure presented in this dissertation is a priority queue. With the rapid deployment of parallel platforms, concurrent versions of priority queues are becoming increasingly important. In this dissertation, we present a novel, concurrent, lock-free linearizable algorithm for priority queues that significantly outperforms other lock-free priority queues. Our algorithm employs recent advances, including lock-free chunks and the use of the efficient fetch-and-increment atomic instruction. Measurements demonstrate a performance improvement by a factor of up to 2 over existing approaches to concurrent priority queues.

The second goal of this dissertation is to expand the coverage of existing lock-free variants for the data structures whose lock-free implementations have not yet been discovered. This is because the lock-free data structures provide a progress guarantee and are known for facilitating scalability, avoiding deadlocks and live-locks, and providing guaranteed system responsiveness. In this dissertation we present a design for a lock-free balanced tree, specifically, a B tree. To the best of our knowledge, this is the first design of a lock-free, dynamic, and balanced tree that employs standard compare-and-swap operations. 

The third and final dissertation goal is to support the efficient memory management for non-blocking data structures. Efficient memory management of dynamic non-blocking data structures remains an important open question. Existing methods either sacrifice the ability to deallocate objects or reduce performance notably. In this dissertation, we present a novel technique, called Drop the Anchor, which significantly reduces the overhead associated with the memory management while reclaiming objects even in the presence of thread failures. We demonstrate this memory management scheme on the common linked list data structure.