Accession Number : ADA191516

Title :   Concurrent Queues: Practical Fetch-and-Phi Algorithms.

Descriptive Note : Technical rept.,

Corporate Author : ROCHESTER UNIV NY DEPT OF COMPUTER SCIENCE

Personal Author(s) : Mellor-Crummey, John M

PDF Url : ADA191516

Report Date : Nov 1987

Pagination or Media Count : 31

Abstract : With the growing use of multiprocessors, data structures that support concurrent operations have become increasingly important. In particular, algorithms and data structures for efficient implementation of concurrent queues have generated interest since operating systems heavily use queueing structures. Existing algorithms for managing concurrent queues all have drawbacks for practical implementation and use. This paper presents two practical implementations of a concurrent queue of unbounded length using fetch-and-phi primitives (a class of atomic read-modify-write operations) and argues their correctness. The first implementation provides wait-free enqueues with unbounded concurrency, although dequeues possess an inherently sequential component. The second implementation provides greater parallelism than existing algorithms and allows the user to trade space for potential parallelism. Both implementations satisfy the strong correctness criterion of linearizability whereas existing algorithms with similiar properties do not.

Descriptors :   *QUEUEING THEORY, ALGORITHMS, DATA BASES, LENGTH, MULTIPROCESSORS, SEQUENCES, STRUCTURES

Subject Categories : Operations Research

Distribution Statement : APPROVED FOR PUBLIC RELEASE