Lock-free data structures
John D. Valois · 1996
Data structures which are shared among concurrent processes require some sort of synchronization in order to avoid becoming corrupted by conflicting updates and to ensure that the processes see correct results. This can be accomplished through mutual exclusion; guaranteeing a process exclusive access while performing critical operations on the data structure. While well understood, this approach can have detrimental effects on performance in an asynchronous environment where processes can suffer unpredictable delays. An alternative approach is to avoid the use of mutual exclusion through the use of simple synchronization primitives such as Compare-and-Swap. Such lock-free data structures can be immune from performance degradation due to slow processes. Universal methods for constructing lock-free data structures for any abstract data type are known, but the resulting implementations are much less efficient than using conventional techniques for mutual exclusion such as spin locks. In this thesis, we present lock-free data structures, algorithms, and memory management techniques for several common abstract data types. Our techniques result in implementations that are as efficient, if not more so, than conventional approaches, and thus provide a practical alternative to using spin locks. We demonstrate the efficiency of our techniques experimentally, and we also show how standard axiomatic formal proof methods can be adapted for the verification of our algorithms.