Brief Announcement: Concurrent Double-Ended Priority Queues

Priority queues, which store a set of keys and support an Insert operation that adds a key to the set and an ExtractMin operation that removes and returns the minimum key, have long been recognized as an important data structure for concurrent systems. They have been used in operating systems for job queues and load balancing, heuristic searches [29], graph algorithms (e.g., [1, 17]) and for event-driven simulations [19]. There are numerous concurrent implementations of priority queues.

In the single-process setting, there has been much research on designing a double-ended priority queue (DEPQ), which supports both ExtractMin and ExtractMax operations [31]. We provide a general transformation to construct a linearizable concurrent DEPQ from a concurrent (single-ended) priority queue. Implementing a concurrent DEPQ has not been explored previously.

We take our inspiration from the insight that some of the sequential DEPQ data structures can be viewed as being constructed from a pair of single-ended priority queues [5]. Our general construction in Section 3 uses two linearizable, concurrent priority queues to construct a linearizable dual-consumer DEPQ, which allows only one process to perform ExtractMin and one process to perform ExtractMax at a time. Insertions proceed concurrently with one another and with Extract operations. The construction works even if the underlying priority queues used are single-consumer, meaning that only one process at a time may perform ExtractMin operations. Our construction uses a new lightweight layer of synchronization between the two processes that perform ExtractMin and ExtractMax operations. It preserves linearizability and lock-free progress: if the underlying priority queue is lock-free, then so is the resulting DEPQ. If the underlying priority queue also supports deletions of arbitrary elements, we provide time and space bounds for our DEPQ.

Section 4 describes how to adapt our dual-consumer DEPQ to handle concurrent Extract operations at each end using a lock-based combining technique [10]. At a high level, each process that acquires the lock for one end of the DEPQ performs a whole batch of Extract operations, which keeps the overhead for synchronization low.

Our technique is general enough to be applied to any concurrent priority queue. In the full version [11], we provide an example that applies our technique (including combining) to a simple list-based priority queue.

There are many DEPQ implementations for just one process (see e.g., Chong and Sahni’s survey [5]). In the concurrent setting, we are unaware of any previous work that aims to provide a linearizable concurrent DEPQ implementation. Medidi and Deo [24] described a DEPQ that supports batches of parallel operations, but their focus was on the synchronous PRAM model. Our construction uses two concurrent (single-ended) priority queues as building blocks. See [7, 26] for surveys of early work on concurrent priority queues, including many based on sequential heap data structures. Tamir, Morrison and Rinetzky [34] added support for an operation that modifies an existing key in a lock-based concurrent heap. Pugh’s skip list data structure [28] has been used as the basis for several concurrent priority queues [3, 21, 32, 33]. Liu and Spear [22] gave a novel concurrent priority queue data structure based on a tree where each node stores a sorted linked list.

The concurrent priority queues discussed above allow multiple concurrent consumers. Our construction requires only a single-consumer priority queue, which may be easier to implement. Hoover and Wei [16] gave a wait-free single-consumer priority queue where operations take $O(\log n+\log p)$ steps, where $n$ is the number of elements in the queue and $p$ is the number of processes accessing it.

One way to use existing data structures to build a linearizable concurrent DEPQ is to use a binary search tree (BST), where the tree is sorted by key values [20, Section 5.2.3]. There are a number of lock-free concurrent BST implementations (e.g., [8, 27]) that support insertion and deletion of keys. The Delete operation can easily be modified to delete (and return) the minimum or maximum key present in the BST to yield the Extract operations of a DEPQ. Since repeated Extract operations at one end of the DEPQ could yield a lopsided BST, it would likely be desirable to use a balanced BST, such as the concurrent chromatic tree, which has both lock-based and lock-free implementations [2, 4]. However, even with balancing, this would require each Extract operation to traverse a path of length $\mathrm{\Theta }(\log n)$ in the BST when the DEPQ contains $n$ elements. In contrast, if we apply our approach to a (single-ended) concurrent priority queue based on a list or skip list, Extract operations find the required key right at the beginning of the list, and less restructuring is required, compared to the rebalancing of chromatic trees. There are also concurrent implementations of (single-ended) priority queues that augment a search tree with a sorted singly-linked list of keys in the tree to expedite ExtractMin operations [18, 30].

Our DEPQ construction uses two (single-ended) priority queues MinPQ and MaxPQ organized using opposite total orders on the keys. Thus, an Extract on MinPQ returns the minimum key and an Extract on MaxPQ returns the maximum key. Algorithm 1 gives pseudocode for our construction.

An Insert operation on the DEPQ simply inserts the key into both priority queues. To coordinate extractions, each item has an associated reserved bit, which is initially 0. An ExtractMin on the DEPQ repeatedly removes the (next) minimum element from MinPQ and tries to set the element’s reserved bit using a TestAndSet instruction until it successfully changes the reserved bit of some element. That element is then returned. If, at any time, the ExtractMin observes that MinPQ is empty, it terminates and indicates that the DEPQ is empty. The ExtractMax operation on the DEPQ is symmetric to ExtractMin, using MaxPQ in place of MinPQ.

The reserved bit ensures that an element cannot be returned twice by both an ExtractMin and an ExtractMax. An element removed from the DEPQ by an ExtractMin operation may remain in MaxPQ for some time, but if it is eventually removed from MaxPQ by an ExtractMax operation, the ExtractMax will skip the item because its TestAndSet operation will fail to set the item’s reserved bit.

If the priority queue implementation we are using also supports a Delete operation, then we can add the optional lines 15 and 25 to the Extract operations. The DEPQ is linearizable regardless of whether these lines are included or not. When an ExtractMin operation removes an item from MinPQ, line 15 removes it from MaxPQ. Whether the inclusion of these lines improves performance may depend upon the underlying priority queue: if deleting an arbitrary element is not much more costly than extracting the minimum, or if performance of the priority queues would degrade significantly due to the presence of obsolete items, then it may be worthwhile to include lines 15 and 25.

The construction provided in Section 3 permits a single Extract operation at each end of the DEPQ at a time. If multiple processes wish to perform Extract operations, we could use two locks: one for each end. A process must acquire the lock for one end of the DEPQ before performing an Extract on that end. Insert operations can proceed regardless of the locks.

To reduce the overhead required by locking, we can use software combining, wherein the process that acquires the lock performs its own work as well as the work of other processes that failed to acquire the lock. Combining is particularly useful for data structures like stacks, queues, deques and priority queues, which have hot spots of contention (e.g., [10, 13, 14, 9]). Early versions of this approach [12, 35] used a tree to combine requests for work. Hendler et al. [14] developed a more efficient approach called flat combining.

We use the CC-Synch combining algorithm of Fatourou and Kallimanis [10] for our DEPQ. This combining algorithm has improved efficiency due to an integrated scheme for both locking the data structure and organizing the requests for operations on it. CC-Synch implements a combining-friendly variant of a queue lock [6, 23, 25]. The queue that implements the lock is also used to store the active operations in FIFO order. Processes use this lock to choose a combiner process, which is delegated to perform a batch of pending operations. After announcing its operation, each process $p$ that is not chosen as the combiner simply waits (by performing local spinning) until a combiner informs $p$ that its requested operation has been completed and provides the result of its operation.

We use two instances of CC-Synch, one for each end of the DEPQ. To perform an Extract operation on the DEPQ, a process adds its operation to the FIFO queue of the appropriate instance of CC-Synch. When CC-Synch chooses a combiner process to perform a batch of Extract operations from the FIFO queue, the combiner performs the Extracts one by one using Algorithm 1. An Insert simply runs Algorithm 1 directly, without using CC-Synch. CC-Synch ensures that only one process acts as a combiner at a time, satisfying Algorithm 1’s requirement that there be only one process performing Extract operations at each end of the DEPQ. This approach improves locality in accessing the data structure, since the combiner process performs an entire batch of Extract operations. It also avoids having a hotspot of contention because multiple Extract operations would typically access the same part of the data structure. We remark that there is little contention on the reserved bits of items: only the two Extract operations that extract an item from MinPQ and MaxPQ can ever access its reserved field, and the reserved field is ignored by Insert operations.