Award Date

8-1-2012

Degree Type

Thesis

Degree Name

Master of Science (MS)

Department

Computer Science

First Committee Member

Ajoy K. Datta

Second Committee Member

Lawrence L. Larmore

Third Committee Member

Juyeon Jo

Number of Pages

65

Abstract

We present a non-blocking implementation for the concurrent Heap data structure in the asynchronous shared memory system. The system may be a traditional one with a single processor with multiple threads, or it may be the one with multiple processors each possibly with multiple threads. Our implementation supports readMin, deleteMin, and insert operations on the heap. The deleteMin and insert operations are non-blocking operations, whereas the readMin is wait-free. One easy approach of using a heap in multi-threading environment could be by locking the entire heap before performing any operation. This would make the implementation very slow to have any practical application.

The above inefficiency could be reduced by using the fine-grained locking mechanism as shown by Herlihy and Shavit. But, this would still be a blocking implementation, where some threads may be waiting forever for some other threads holding the locks that might have crashed or failed.

Israeli and Rappoport gave a non-blocking implementation which supports deleteMin and insert operations using some primitives which they claim could be built using transactional memory. Moreover, their implementation has a limitation on the range of values a node in the heap can have. We propose a different implementation which supports all three operations using a primitive, called Double-Compare-And-Set(DCAS). DCAS is a synchronization operation supported in hardware by Motorola 68K family of processors. It was also going to be supported by Sun's canceled Rock processor. DCAS takes two memory locations as input, and writes new values to them only if they match input expected values. Our algorithm has no limitation on the range of numbers a node can have.

Keywords

Concurrency; Data structures (Computer science); Heap; Memory management (Computer science); Non-blocking; Threads (Computer programs); Wait-free

Disciplines

Computer Engineering | 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