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
Document File: 2 page(s) / 45K

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

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 100% of the total text.

Page 1 of 2

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

  The double-ended queue is represented as a doubly linked list. Each node in the list contains data that represents an item in the abstract object. Two pointers, Right and Left track the rightmost and leftmost nodes in the list. The four operations on a double-ended queue are RightPush, RightPop, LeftPush, and LeftPop. The following is the algorithm. For simplicity the code assumes perfect memory management. The code can be easily adapted to well-known memory management methods.

// Shared structures and variables structure NodeType {R,L:*NodeType; Data:DataType} Right,Left : *NodeType; // Initially Right == null and Left == null

PushRight(data:DataType) { node = NewNode(); node^.Data = data; while true {
r = Right; if r == null { if DCAS(&Right,&Left,null,null,node,node) return; } else {
node^.L = r;
rr = r^.R; if DCAS(&Right,&r^.R,r,rr,node,node) return;

}

}

}

PopRight() : DataType { while true { r = Right; if r == null return EMPTY; l = Left;

if r == l { if DCAS(&Right,&Left,r,l,null,null) break; } else {
prev = r^.L; if DCAS(&Right,&Left,r,l,prev,l) break;

}

The left side operations are symmetric to the right side operations.

1

Page 2 of 2

Disclosed by International Business Machines Corporation

2