Browse Theses

Non-blocking synchronization (NBS) has significant advantages over blocking synchronization: The same code can ran on uniprocessors, asynchronous handlers, and on shared memory multiprocessors. NBS is deadlock-free, aids fault-tolerance, eliminates interference between synchronization and the scheduler, and can increase total system throughput. These advantages are becoming even more important with the increased use of parallelism and multiprocessors, and as the cost of a delay increases relative to processor speed. This thesis demonstrates that non-blocking synchronization is practical as the sole co-ordination mechanism in systems by showing that careful design and implementation of operating system software makes implementing efficient non-blocking synchronization far easier, by demonstrating that DCAS &parl0;Double-Compare-and-Swap&parr0; is the necessary and sufficient primitive for implementing NBS, and by demonstrating that efficient hardware DCAS is practical for RISC processors. This thesis presents non-blocking implementations of common data-structures sufficient to implement an operating system kernel. These out-perform all non-blocking implementations of the same data-structures and are comparable to spin-locks under no contention. They exploit properties of well- designed systems and depend on DCAS . I present an O(n) non-blocking implementation of CAS n with extensions that support multi-objects, a contention-reduction technique based on DCAS that is fault-tolerant and OS-independent yet performs as well as the best previously published techniques, and two implementations of dynamic, software transactional memory (STM) that support multi-object updates, and have O(w) overhead cost (for w writes in an update) in the absence of preemption. Finally, I demonstrate that the proposed OS implementation of DCAS is inefficient, and present a design of an efficient, hardware, DCAS implementation that is specific to the R4000 processor; however, the observations that make implementation practical are generally applicable. In short, the incremental costs of adding binary atomic synchronization primitives are very low, given that designers have already implemented unary atomic synchronization primitives.