Dismiss
InnovationQ will be updated on Sunday, Oct. 22, from 10am ET - noon. You may experience brief service interruptions during that time.
Browse Prior Art Database

Dynamic Lock-Free Double-Ended Queues Using Single-Address Double-Word Compare-and-Swap

IP.com Disclosure Number: IPCOM000012795D
Original Publication Date: 2003-May-28
Included in the Prior Art Database: 2003-May-28
Document File: 2 page(s) / 54K

Publishing Venue

IBM

Abstract

Lock-free objects are inherently fault-tolerant and perform well even under thread failures and arbitrary delays. This invention presents a method for a lock-free implementation of dynamic double-ended queues using single-address double word compare-and-swap instruction that is available on most current processor architectures.

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

Page 1 of 2

  Dynamic Lock-Free Double-Ended Queues Using Single-Address Double-Word Compare-and-Swap

    The invention uses a double-word Anchor to hold both the Left and Right pointers to the end nodes of a doubly linked list representing the double-ended queue. The Anchor also includes a tag that can have one of the values STABLE, RPUSH, or LPUSH, in order to indicate transient states. The operations on the object are PushRight, PopRight, PushLeft, and PopLeft. The operations are symmetric so we present code for operations from the right.

Initially Anchor = <null,null,STABLE>

PushRight(node:*NodeType) {

while true {

<l,r,t> := Anchor;

node^.L := r;

if r == null {

if CAS(&Anchor,<{l,r,t>,<node,node,STABLE>) return;

} else {

if t != STABLE {Stabilize(l,r,t); continue;}

if CAS(&Anchor,<l,r,t>,<l,node,RPUSH>) return;

}

}

}

PopRight() : *NodeType {

while true {

if <l,r,t>:=Anchor == <null,null,STABLE> break;

if t != STABLE {Stabilize(l,r,t); continue;}

if r == l {

if CAS(&Anchor,<l,r,t>,<null,null,STABLE>) break;

} else {

prev := r^.L;

if !CAS(&Anchor,<l,r,t>,<l,prev,STABLE>) continue;

CAS(&prev^.R},r,null); break;

}

}

return r;
}

Stabilize(l,r:*NodeType,t:TagType) {

if t == RPUSH

StabilizeRight(l,r);

else

StabilizeLeft(l,r);

return;
}

StabilizeRight(l,r:*NodeType) {

prev := r^.L;

prevnext := prev^.R;

if prevnext != r {

if <l,r,t> != Anchor return;

if !CAS(&prev^.R,prevnext,r) return;

}

CAS(&Anchor,<l,r,t>,<l,r,STABLE>);

return;
}

1

Page 2 of 2

Disclosed by International Business Machi...