Technical Report

DCAS-based Concurrent Deques Supporting Bulk Allocation
October 2002

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.

Authors: Mark Moir, Guy Steele, Paul Martin

Content:

Hardware and Software, Engineered to Work Together