|
We present a lock-free implementation of a dynamically sized double-ended
queue (deque) that is based on the double compare-and-swap (DCAS)
instruction. This implementation improves over the best previous one by
allowing storage to be allocated and freed in bulk when the size of the
deque changes significantly, and to avoid invocation of the storage
allocator at all while the size remains relatively stable. We achieved
this implementation in two steps by first solving the easier problem of
implementing the deque for a garbage-collected environment, and then
applying the Lock-Free Reference Counting methodology we recently proposed
in order to achieve a version independent of garbage collection.
|
