Accession Number : ADA309412

Title :   Simple, Fast, and Practical Non-Blocking and Blocking Concurrent Queue Algorithms.

Descriptive Note : Technical rept.,

Corporate Author : ROCHESTER UNIV NY DEPT OF COMPUTER SCIENCE

Personal Author(s) : Michael, Maged M. ; Scott, Michael L.

PDF Url : ADA309412

Report Date : DEC 1995

Pagination or Media Count : 14

Abstract : Drawing ideas from previous authors, we present a new non-blocking concurrent queue algorithm and a new two-lock queue algorithm in which one enqueue and one dequeue can proceed concurrently. Both algorithms are simple, fast, and practical; we were surprised not to find them in the literature. Experiments on a 12-node 501 Challenge multiprocessor indicate that the new non-blocking queue consistently outperforms the best known alternatives; it is the clear algorithm of choice for machines that provide a universal atomic primitive (e.g. compare.and.swap or load.linked/store.conditional). The two-lock concurrent queue outperforms a single lock when several processes are competing simultaneously for access; it appears to be the algorithm of choice for busy queues on machines with non-universal atomic primitives (e.g. test and.set). Since much of the motivation for non-blocking algorithms is rooted in their immunity to large, unpredictable delays in process execution, we report experimental results both for systems with dedicated processors and for systems with several processes multiprogrammed on each processor.

Descriptors :   *ALGORITHMS, *QUEUEING THEORY, *CONCURRENT ENGINEERING, SOFTWARE ENGINEERING, DATA MANAGEMENT, DISTRIBUTED DATA PROCESSING, COMPUTER COMMUNICATIONS, PERFORMANCE(ENGINEERING), INPUT OUTPUT PROCESSING, MULTIPROCESSORS, SYSTEMS ANALYSIS, MULTIPROGRAMMING, C PROGRAMMING LANGUAGE.

Subject Categories : Computer Programming and Software

Distribution Statement : APPROVED FOR PUBLIC RELEASE