7.1.2.4 Compound Double-Ended Queue Revisited
Keywords: perfbook_html

###
7.1.2.4 Compound Double-Ended Queue Revisited

This section revisits the compound double-ended queue, using a trivial rebalancing scheme that moves all the elements from the non-empty queue to the now-empty queue.

Quick Quiz 7.5: Move all the elements to the queue that became empty? In what possible universe is this braindead solution in any way optimal??? End Quick Quiz

In contrast to the hashed implementation presented in the previous section, the compound implementation will build on a sequential implementation of a double-ended queue that uses neither locks nor atomic operations.

Figure: Compound Parallel Double-Ended Queue Implementation

Figure shows the implementation. Unlike the hashed implementation, this compound implementation is asymmetric, so that we must consider the pdeq_dequeue_l() and pdeq_dequeue_r() implementations separately.

Quick Quiz 7.6: Why can't the compound parallel double-ended queue implementation be symmetric? End Quick Quiz

The pdeq_dequeue_l() implementation is shown on lines 1-16 of the figure. Line 6 acquires the left-hand lock, which line 14 releases. Line 7 attempts to left-dequeue an element from the left-hand underlying double-ended queue, and, if successful, skips lines 8-13 to simply return this element. Otherwise, line 9 acquires the right-hand lock, line 10 left-dequeues an element from the right-hand queue, and line 11 moves any remaining elements on the right-hand queue to the left-hand queue, and line 12 releases the right-hand lock. The element, if any, that was dequeued on line 10 will be returned.

The pdeq_dequeue_r() implementation is shown on lines 18-38 of the figure. As before, line 23 acquires the right-hand lock (and line 36 releases it), and line 24 attempts to right-dequeue an element from the right-hand queue, and, if successful, skips lines 24-35 to simply return this element. However, if line 25 determines that there was no element to dequeue, line 26 releases the right-hand lock and lines 27-28 acquire both locks in the proper order. Line 29 then attempts to right-dequeue an element from the right-hand list again, and if line 30 determines that this second attempt has failed, line 31 right-dequeues an element from the left-hand queue (if there is one available) and line 32 moves any remaining elements from the left-hand queue to the right-hand queue. Either way, line 34 releases the left-hand lock.

Quick Quiz 7.7: Why is it necessary to retry the right-dequeue operation on line 29 of Figure ? End Quick Quiz

Quick Quiz 7.8: Surely the left-hand lock must sometimes be available!!! So why is it necessary that line 26 of Figure unconditionally release the right-hand lock? End Quick Quiz

The pdeq_enqueue_l() implementation is shown on lines 40-47 of Figure . Line 44 acquires the left-hand spinlock, line 45 left-enqueues the element onto the left-hand queue, and finally line 46 releases the lock. The pdeq_enqueue_r() implementation (shown on lines 49-56) is quite similar.