7.1.2.2 Compound Double-Ended Queue

Figure: Compound Double-Ended Queue
\resizebox{3in}{!}{\includegraphics{SMPdesign/lockdeqpair}}

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.

Paul E. McKenney 2011-12-16