Implementing Lock Free Data Structure for Shared-Memory Systems using Linked List

It is becoming evident that non-blocking algorithms can deliver significant benefits to parallel system. Such algorithms use low-level atomic primitives such as compare-and-swap through careful design and by eschewing the use of locks, it is possible to build system which scale to highly-parallel environments and which are resilient to scheduling decisions. Lock-free data structures implement concurrent objects without the use of mutual exclusion. This approach can avoid performance problems due to unpredictable delays while processes are within critical sections. Although universal methods are known that give lock-free data structures for any abstract data type, the overhead of these methods makes them inefficient when compared to conventional techniques using mutual exclusion, such as spin locks. In using lock-free data structures and algorithms for implementing a shared linked list and skip list, it allows concurrent traversal, insertion, and deletion by any number of processes. General Terms Data Structure, Memory Management, Algorithms