Browse Prior Art Database

Fast Dynamic Lock-Free Double-Ended Queue Implementation Using Double-Compare-and-Swap

IP.com Disclosure Number: IPCOM000013122D
Original Publication Date: 2003-Jun-13
Included in the Prior Art Database: 2003-Jun-13

Publishing Venue

IBM

Abstract

Lock-free objects hold important advantages over corresponding conventional lock-based objects, with respect to fault-tolerance and robust performance even under thread failures and arbitrary delays. This invention presents a fast lock-free dynamic implementation of double-ended queues that allows simple memory management of removed nodes. The implementation uses the double-compare-and-swap (DCAS) instruction that is available on most current processor architectures. The implementation requires only one DCAS per push or pop operation on the object.in the absence of contention