Dynamic Lock-Free Deques Using Single-Address Double-Word CAS

Prior lock-free algorithms for double-ended queues (deques)use the DCAS (double-compare-and-swap)atomic primitive,which is not supported on anycurren processor architecture. This paper presents the first CAS-based lock-free algorithm for deques.The algorithm is linearizable,dynamic and compatible with simple and efficient lock-free memorymanagemen methods.The algorithm is practical using single-word CAS (compare-and-swap)or restricted LL/SC load-linked/store-conditional).In order to allow he deque ’s size and memory use to grow and shrink arbitrarily, the algorithm employs single address double-word CAS or restricted LL/SC,which have for long been supported on all major processor architectures.