One of the simplest and most effective ways to deterministically partition a data structure is to hash it. It is possible to trivially hash a double-ended queue by assigning each element a sequence number based on its position in the list, so that the first element left-enqueued into an empty queue is numbered zero and the first element right-enqueued into an empty queue is numbered one. A series of elements left-enqueued into an otherwise-idle queue would be assigned decreasing numbers (-1, -2, -3, ...), while a series of elements right-enqueued into an otherwise-idle queue would be assigned increasing numbers (2, 3, 4, ...). A key point is that it is not necessary to actually represent a given element's number, as this number will be implied by its position in the queue.
Given this approach, we assign one lock to guard the left-hand index,
one to guard the right-hand index, and one lock for each hash chain.
Figure shows the resulting
data structure given four hash chains.
Note that the lock domains do not overlap, and that deadlock is avoided
by acquiring the index locks before the chain locks, and by never
acquiring more than one lock of each type (index or chain) at a time.
Each hash chain is itself a double-ended queue, and in this example,
each holds every fourth element.
The uppermost portion of
Figure
shows the state after a single element (``R1'') has been
right-enqueued, with the right-hand index having been incremented to
reference hash chain 2.
The middle portion of this same figure shows the state after
three more elements have been right-enqueued.
As you can see, the indexes are back to their initial states, however,
each hash chain is now non-empty.
The lower portion of this figure shows the state after three additional
elements have been left-enqueued and an additional element has been
right-enqueued.
From the last state shown in
Figure ,
a left-dequeue operation would return element ``L-2'' and left
the left-hand index referencing hash chain 2, which would then
contain only a single element (``R2'').
In this state, a left-enqueue running concurrently with a right-enqueue
would result in lock contention, but the probability of such contention
can be arbitrarily reduced by using a larger hash table.
Figure
shows how 12 elements would be organized in a four-hash-bucket
parallel double-ended queue.
Each underlying single-lock double-ended queue holds a one-quarter
slice of the full parallel double-ended queue.
Figure
shows the corresponding C-language data structure, assuming an
existing struct deq that provides a trivially locked
double-ended-queue implementation.
This data structure contains the left-hand lock on line 2,
the left-hand index on line 3, the right-hand lock on line 4,
the right-hand index on line 5, and, finally, the hashed array
of simple lock-based double-ended queues on line 6.
A high-performance implementation would of course use padding or special
alignment directives to avoid false sharing.
Figure
shows the implementation of the enqueue and dequeue functions.7.1Discussion will focus on the left-hand operations, as the right-hand
operations are trivially derived from them.
Lines 1-13 show pdeq_dequeue_l(), which left-dequeues and returns an element if possible, returning NULL otherwise. Line 6 acquires the left-hand spinlock, and line 7 computes the index to be dequeued from. Line 8 dequeues the element, and, if line 9 finds the result to be non-NULL, line 10 records the new left-hand index. Either way, line 11 releases the lock, and, finally, line 12 returns the element if there was one, or NULL otherwise.
Lines 15-24 shows pdeq_enqueue_l(), which left-enqueues the specified element. Line 19 acquires the left-hand lock, and line 20 picks up the left-hand index. Line 21 left-enqueues the specified element onto the double-ended queue indexed by the left-hand index. Line 22 updates the left-hand index, and finally line 23 releases the lock.
As noted earlier, the right-hand operations are completely analogous to their left-handed counterparts.
Quick Quiz 7.4: Is the hashed double-ended queue a good solution? Why or why not? End Quick Quiz
Paul E. McKenney 2011-12-16