Award Date

12-15-2018

Degree Type

Thesis

Degree Name

Master of Science in Computer Science

Department

Computer Science

First Committee Member

Ajoy K. Datta

Second Committee Member

John Minor

Third Committee Member

Yoohwan Kim

Fourth Committee Member

Venkatesan Muthukumar

Number of Pages

42

Abstract

A concurrent data object is lock-free if it guarantees that at least one, among all concurrent operations, finishes after a finite number of steps. In other words, a lock free technique guarantees that some thread always makes progress. Lock-free data objects offer several advantages over their blocking counterparts, such as being immune to deadlocks and priority inversion, and typically provide high scalability and performance, especially in shared memory multiprocessor architectures.

Composition of data structures is a powerful approach to combine simple data structures to create more complex ones. It works as a building block for many advanced useful data structures. In this thesis, we study the composition of lock-free data structures. We specifically consider a simple yet fundamental problem of combining two stacks to create a queue in a lock-free concurrent setting. Thus, we simulate the enqueue and dequeue operations of queues using the push and pop operations of stacks. Our work explores the challenges in combining the lock-free data structures with respect to ensuring the consistency as well as the lock-freedom of the composed data structure. We also implement the algorithm and experimentally evaluate its performance.

Keywords

data structure composition; lock-free; mulit core; queue using two stacks

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