We present a non-blocking lock-free implementation of skip list data structure using multi word compare and swap (CASN) operation. This operation is designed to work on arbitrary number of memory locations as a single atomic step. We discuss the implementation details of CASN operation which only utilizes the single word compare and swap atomic primitive found in most of the contemporary multiprocessor systems. Using this operation, we first design lock-free algorithms to implement various operations on linked list data structure, then extend it to design skip lists. Skip list is a probabilistic data structure composed of linked lists stacked together forming different levels. It provides expected logarithmic time search like balanced search trees, but without requiring rebalancing. The fundamental operations on a skip list data structure require traversing and updating a number of memory locations. Due to this nature of the data structure, using a powerful atomic primitive like CASN in its implementation simplifies the design and makes the concurrent reasoning easier. In addition to fundamental operations, we present a variety of other operations on linked list and skip list data structures and provide examples to support the correctness of the proposed algorithms.
展开▼
