DocumentCode :
1069480
Title :
A nonblocking algorithm for shared queues using compare-and-swap
Author :
Prakash, Sundeep ; Lee, Yann Hang ; Johnson, Theodore
Author_Institution :
Dept. of Comput. & Inf. Sci., Florida Univ., Gainesville, FL, USA
Volume :
43
Issue :
5
fYear :
1994
fDate :
5/1/1994 12:00:00 AM
Firstpage :
548
Lastpage :
559
Abstract :
Nonblocking algorithms for concurrent objects guarantee that an object is always accessible, in contrast to blocking algorithms in which a slow or halted process can render part or all of the data structure inaccessible to other processes. A number of algorithms have been proposed for shared FIFO queues, but nonblocking implementations are few and either limit the concurrency or provide inefficient solutions. The authors present a simple and efficient nonblocking shared FIFO queue algorithm with O(n) system latency, no additional memory requirements, and enqueuing and dequeuing times independent of the size of the queue. They use the compare & swap operation as the basic synchronization primitive. They model their algorithm analytically and with a simulation, and compare its performance with that of a blocking FIFO queue. They find that the nonblocking queue has better performance if processors are occasionally slow, but worse performance if some processors are always slower than others
Keywords :
data structures; queueing theory; FIFO queue algorithm; compare-and-swap; concurrent objects; data structure; nonblocking algorithm; nonblocking queue; performance; queue; shared queues; Algorithm design and analysis; Analytical models; Concurrent computing; Councils; Data structures; Delay; Interference; Performance analysis; Queueing analysis; Robustness;
fLanguage :
English
Journal_Title :
Computers, IEEE Transactions on
Publisher :
ieee
ISSN :
0018-9340
Type :
jour
DOI :
10.1109/12.280802
Filename :
280802
Link To Document :
بازگشت