On Composability, Efficient Design and Memory Reclamation of Lock-free Data Structures

The transition to multicore processors has brought synchronization, a fundamental challenge in computer science, into focus. In looking for solutions to the problem, interest has developed in the lock-free approach, which has been proven to achieve several advantages over the traditional mutual exclusion ap-proach. This thesis studies challenges in interprocess synchronization in shared memory multicore systems using the lock-free approach. Our contributions fo-cus on efficient design and implementation, composition, and dynamic memory reclamation of lock-free data structures, a key component in lock-free solutions to synchronization problems. First, we show that lock-free synchronization offers several advantages. Lock-free implementations of data structures can achieve decent throughput performance while managing to provide competitive fairness among the shar-ing participants in accessing the shared data. We also show that although lock-freedom does not guarantee starvation-freedom, it is composable in terms o