7.1.2.2 Compound Double-Ended Queue
Keywords: perfbook_html

###
7.1.2.2 Compound Double-Ended Queue

Figure: Compound Double-Ended Queue

One way of forcing non-overlapping lock domains is shown in Figure . Two separate double-ended queues are run in tandem, each protected by its own lock. This means that elements must occasionally be shuttled from one of the double-ended queues to the other, in which case both locks must be held. A simple lock hierarchy may be used to avoid deadlock, for example, always acquiring the left-hand lock before acquiring the right-hand lock. This will be much simpler than applying two locks to the same double-ended queue, as we can unconditionally left-enqueue elements to the left-hand queue and right-enqueue elements to the right-hand queue. The main complication arises when dequeuing from an empty queue, in which case it is necessary to:

1. If holding the right-hand lock, release it and acquire the left-hand lock, rechecking that the queue is still empty.
2. Acquire the right-hand lock.
3. Rebalance the elements across the two queues.
4. Remove the required element.
5. Release both locks.

Quick Quiz 7.3: In this compound double-ended queue implementation, what should be done if the queue has become non-empty while releasing and reacquiring the lock? End Quick Quiz

The rebalancing operation might well shuttle a given element back and forth between the two queues, wasting time and possibly requiring workload-dependent heuristics to obtain optimal performance. Although this might well be the best approach in some cases, it is interesting to try for an algorithm with greater determinism.