...
In this solution, communication with the associated algorithms is accomplished only through hazard pointers and a procedure RetireNode() that is called by threads to pass the addresses of retired nodes.
Pseudocode:PSEUDOCODE
| Code Block | ||||
|---|---|---|---|---|
| ||||
// Hazard pointers types and structure
structure HPRecType {
HP[K]:*Nodetype; Next:*HPRecType;}
// The header of the HPRec list
HeadHPRec: *HPRecType;
// Per-thread private variables
rlist: listType; // initially empty
rcount: integer; // initially 0
//The retired node routine
RetiredNode(node:*NodeType) {
rlist.push(node);
rcount++;
if(rcount >= R)
Scan(HeadHPRec);
}
// The scan routine
Scan(head:*HPRecType) {
// Stage1: Scan HP list and insert non-null values in plist
plist.init();
hprec<-head;
while (hprec != null) {
for (i<-0 to K-1) {
hptr<-hprec^HP[i];
if (hptr!= null)
plist.insert(hptr);
}
hprec<-hprec^Next;
}
// Stage 2: search plist
tmplist<-rlist.popAll();
rcount<-0;
node<-tmplist.pop();
while (node != null) {
if (plist.lookup(node)) {
rlist.push(node);
rcount++;
}
else {
PrepareForReuse(node);
}
node<-tmplist.pop();
}
plist.free();
}
|
...
In the implementation, the pointer being removed is stored in the hazard pointer, preventing other threads from reusing it and thereby avoiding the ABA problem.
Code:CODE
| Code Block | ||||
|---|---|---|---|---|
| ||||
void queue_enqueue(Queue *q, gpointer data) {
Node *node;
Node *tail;
Node *next;
node = g_slice_new(Node);
node->data = data;
node->next = NULL;
while (TRUE) {
tail = q->tail;
HAZARD_SET(0, tail); // Mark tail as hazardous
if (tail != q->tail) { // Check tail hasn't changed
continue;
}
next = tail->next;
if (tail != q->tail) {
continue;
}
if (next != NULL) {
CAS(&q->tail, tail, next);
continue;
}
if (CAS(&tail->next, null, node) {
break;
}
}
CAS(&q->tail, tail, node);
}
gpointer queue_dequeue(Queue *q) {
Node *node;
Node *tail;
Node *next;
while (TRUE) {
head = q->head;
LF_HAZARD_SET(0, head); // Mark head as hazardous
if (head != q->head) { // Check head hasn't changed
continue;
}
tail = q->tail;
next = head->next;
LF_HAZARD_SET(1, next); // Mark next as hazardous
if (head != q->head) {
continue;
}
if (next == NULL) {
return NULL; // Empty
}
if (head == tail) {
CAS(&q->tail, tail, next);
continue;
}
data = next->data;
if (CAS(&q->head, head, next)) {
break;
}
}
LF_HAZARD_UNSET(head); // Retire head, and perform
// reclamation if needed.
return data;
}
|
...