Fast lock-free linked lists in distributed shared memory systems

Abstract

In shared memory systems concurrent processes operate on shared data structures. The consistency of the data structures is maintained by mutual exclusion, which is implemented by locking. Locking is an easy way of ensuring consistency of the shared data structures, but it has several drawbacks. The major drawback is that it increases the latency of all the processes as the shared data structure is accessed in a serial manner. It might also result in deadlocks when the process currently accessing the shared data structure is pre-empted or terminated. An alternate approach to avoid mutual exclusion by locking is by implementing lock-free data structures. This is possible by using basic synchronization primitives such as Compare & Swap and Double Compare & Swap. Processes can concurrently read and write on these data structures and also maintain the consistency of the data structure. Lock-free data structures reduces the latency of the processes and avoids deadlocks. This thesis presents lock-free linked listsalong with the algorithms that operate on them. The algorithms were simulated and were compared with Greenwald & Cheriton's and Valois' algorithms. The design of the linked lists along with the effective and efficient use of the synchronization primitives in the algorithms provides a improved performance over the other two algorithms. The correctness of the algorithms is also presented in the thesis.