A practical nonblocking queue algorithm using compare-and-swap

Abstract

Many nonblocking algorithms have been proposed for shared queues. Previous studies indicate that link-based algorithms perform best. However, these algorithms have a memory management problem. a dequeued node can not be freed or reused without problem: handling. The problem is usually overloaded; one just assumes the existence of a lower level mechanism, which takes care of all the details of handling the problem. Employing such a mechanism incurs significant overheads, and consequently the link-based queues may not perform as well as claimed. A new nonblocking queue algorithm based on a finite array is proposed in this paper. Comparing with the link-based algorithms. the nerv algorithm provides the same degree of concurrency without being subject to the memory problem, hence suggests a good performance.