The Baskets Queue
FIFO Queues have over the years been the subject of significant research. Such queues are used as buffers both in a variety of applications, and in recent years as a key tool in buffering data in high speed communication networks.
- PDF / 548,130 Bytes
- 14 Pages / 430 x 660 pts Page_size
- 47 Downloads / 229 Views
The School of Computer Science, Tel Aviv University, Israel 2 Sun Microsystems Laboratories [email protected], [email protected], [email protected]
Abstract. FIFO Queues have over the years been the subject of significant research. Such queues are used as buffers both in a variety of applications, and in recent years as a key tool in buffering data in high speed communication networks. Overall, the most popular dynamic-memory lock-free FIFO queue algorithm in the literature remains the MS-queue algorithm of Michael and Scott. Unfortunately, this algorithm, as well as many others, offers no more parallelism than that provided by allowing concurrent accesses to the head and tail. In this paper we present the Baskets Queue - a new, highly concurrent lock-free linearizable dynamic memory FIFO queue. The Baskets Queue introduces a new form of parallelism among enqueue operations that creates baskets of mixed-order items instead of the standard totally ordered list. The operations in different baskets can be executed in parallel. Surprisingly however, the end result is a linearizable FIFO queue, and in fact, we show that a basket queue based on the MS-queue outperforms the original MS-queue algorithm in various benchmarks. Keywords: CAS, Compare and Swap, Concurrent Data Structures, FIFO queue, Lock-free, Non-blocking, Synchronization.
1 Introduction First-in-first-out (FIFO) queues are among the most basic and widely used concurrent data structures. They have been studied in a static memory setting [1,2] and in a dynamic one [3,4,5,6,7,8,9,10,11,12,13,14,15,2]. The classical concurrent queue is a linearizable structure that supports enqueue and dequeue operations with the usual FIFO semantics. This paper focuses on queues with dynamic memory allocation. The best known concurrent FIFO queue implementation is the lock-free queue of Michael and Scott [16] which is included in the JavaT M Concurrency Package [17]. Its key feature is that it maintains, in a lock-free manner, a FIFO ordered list that can be accessed disjointly through head and tail pointers. This allows enqueue operations to execute in parallel with dequeue operations. A later article by Ladan-Mozes and Shavit [7] presented the optimistic queue that in many cases performs better than the MS-queue algorithm. The optimistic doubly-linked list reduces the number of compare-and-swap (CAS) operations necessary to perform an enqueue and replaces them with simple stores. However, neither algorithm allows more parallelism then that allowed by the disjoint head and tail. E. Tovar, P. Tsigas, and H. Fouchal (Eds.): OPODIS 2007, LNCS 4878, pp. 401–414, 2007. c Springer-Verlag Berlin Heidelberg 2007
402
M. Hoffman, O. Shalev, and N. Shavit
a basket
an item x xx xx x xx xx x
x x x x x
x x x x x
Head
Tail Fig. 1. The abstract Baskets Queue
In an attempt to add more parallelism, Moir et. al [18] showed how one could use elimination as a back-off scheme to allow pairs of concurrent enqueue and dequeue operations to exchange values without accessing
Data Loading...
