Pseudocode from article of the above name, IJPP, August 1994. Michael L. Scott and John M. Mellor-Crummey. Inspired by an earlier paper on adaptive combining tree barriers by Gupta and Hill (IJPP, June 1989).
shared pseudodata : Boolean
type node = record
// Volatile fields may change spontaneously; there are no locks.
visitor : volatile ^Boolean := &pseudodata
// first process to visit this node; may be temporarily inconsistent,
// but will stabilize before being dereferenced
bin_left, bin_right, bin_parent : ^node := // tree
left, right, parent : volatile ^node := bin_left, bin_right, bin_parent
depth, inorder : integer := // as appropriate, in unmodified tree;
// inorder allows us to determine left and right descendancy.
type instance = record
f : Boolean := false
root, my_leaf, my_internal_node : ^node := // as appropriate, in tree
// my_internal_node is used only for reinitialization.
private instances : array [0..2] of instance
// separate copy for each process, but allocated
// in memory accessible to other processes
private current_instance : ^instance := &instances[0]
private previous_instance : ^instance := &instances[2]
procedure barrier ()
// find place to wait:
n : ^node := current_instance->my_leaf
loop
w : ^node := n->parent
if w = nil
// signal achievement of barrier:
current_instance->root->visitor^ := true
// may unblock a process at the spin below
goto rtn
x : ^node := fetch_and_store (&w->visitor, ¤t_instance->f)
if x = &pseudodata
exit loop
w->visitor := x // already visited; put it back
n := w // continue up the tree
// adapt tree:
if n->inorder < w->inorder
o : ^node := w->right
else
o : ^node := w->left
p : ^node := w->parent
if p = nil
o->parent := nil
else
// update down pointer:
if w->inorder < p->inorder
p->left := o
else
p->right := o
// update up pointer:
loop
t : ^node := fetch_and_store (&o->parent, p)
if t != nil and then (p = nil or else t->depth > p->depth)
exit loop // swap was a good thing
// else some other process linked o even higher in the tree;
// continue loop to undo our poorer update
p := t
// await notification and pass on the news:
repeat until current_instance->f // spin
// set at the root by line 7 of this procedure;
// set at other nodes by the code below
w->bin_left->visitor^ := true
w->bin_right->visitor^ := true
rtn:
reinitialize (previous_instance)
previous_instance := current_instance
if current_instance = &instances[2]
current_instance := &instances[0]
else
current_instance := current_instance + 1
NB: The termination test for the inner loop above differs from that published in the IJPP paper. The version here reflects a bug fix submitted by Alexander Malkis of the IMDEA Software Institute in March 2012.
shared pseudodata : ^node
type node = record
// Volatile fields may change spontaneously; there are no locks.
visited, notified : volatile Boolean := false, false
// visited = true iff some process has visited this node in
// enter_barrier.
// notified will eventually become true once the barrier is achieved.
owner : volatile ^node := // address of appropriate f field for leaves,
// &pseudodata for internal nodes
// address of f field of a recent visitor in exit_barrier
// (not necessarily the *most* recent)
bin_left, bin_right, bin_parent : ^node := // tree
depth, inorder : integer := // as appropriate, in unmodified tree;
// inorder allows us to determine left and right descendancy.
left, right, parent : volatile ^node := bin_left, bin_right, bin_parent
type instance = record
f : ^node := nil // node at which we were awakened
root, my_leaf, my_internal_node : ^node := // as appropriate, in tree
// my_internal_node is used only for reinitialization.
private instances : array [0..2] of instance
// separate copy for each process, but allocated
// in memory accessible to other processes
private current_instance : ^instance := &instances[0]
private previous_instance : ^instance := &instances[2]
procedure enter_barrier ()
n : ^node := current_instance->my_leaf
loop
w : ^node := n->parent
if w = nil
// signal achievement of barrier:
current_instance->root->notified := true
current_instance->root->owner^ := current_instance->root
// may unblock a process at the spin in exit_barrier,
// informing it that we woke it up at the root
return
if fetch_and_store (&n->visited, true) = false
exit loop
n := w // continue up the tree
// adapt tree:
if n->inorder < w->inorder
o : ^node := w->right
else
o : ^node := w->left
p : ^node := w->parent
if p = nil
o->parent := nil
else
// update down pointer:
if w->inorder < p^inorder
p->left := o
else
p->right := o
// update up pointer:
loop
t : ^node := fetch_and_store (&o->parent, p)
if t != nil and then t->depth > p->depth
exit loop // swap was a good thing
// else some other process linked o even higher in the tree;
// continue loop to undo our poorer update
p := t
procedure exit_barrier ()
n : ^node := current_instance->my_leaf
if n->notified
goto rtn
p : ^node := n->bin_parent
loop
if p->owner = &pseudodata
p->owner := ¤t_instance->f
if p->notified
exit loop
else if p->bin_parent = nil
repeat
p := current_instance->f
until p != nil // spin
// set at root by line 7 of enter_barrier;
// set at other nodes by the code below
exit loop
else
p := p->bin_parent
else if p->notified
exit loop
else
repeat
p := current_instance->f
until p != nil // spin
// set at root by line 7 of enter_barrier;
// set at other nodes by the code below
exit loop
// work way back down to leaf, giving notifications:
while p != current_instance->my_leaf
if n->inorder < p->inorder
o := p->bin_right
p := p->bin_left
else
o := p->bin_left
p := p->bin_right
o->notified := true
o->owner^ := o
// may unblock a process in the spin above,
// informing it that we woke it up at o
rtn:
reinitialize (previous_instance)
previous_instance := current_instance
if current_instance = &instances[2]
current_instance := &instances[0]
else
current_instance := current_instance + 1
