Award Date

5-1-2015

Degree Type

Thesis

Degree Name

Master of Science in Computer Science

Department

Computer Science

First Committee Member

Ajoy K. Datta

Second Committee Member

Ajoy K. Datta

Third Committee Member

Lawrence L. Larmore

Fourth Committee Member

Venkatesan Muthukumar

Fifth Committee Member

John Minor

Number of Pages

81

Abstract

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.

Keywords

casn; concurrent; data structure; skip-list

Disciplines

Computer Sciences

File Format

pdf

Degree Grantor

University of Nevada, Las Vegas

Language

English

Rights

IN COPYRIGHT. For more information about this rights statement, please visit http://rightsstatements.org/vocab/InC/1.0/

Download


Share

COinS