Fast, Contention-Free Combining Tree Barriers

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).


An adaptive combining tree barrier that spins only on local locations.

  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, &current_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.


A "fuzzy" version of the local-spinning adaptive combining tree barrier.

  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 := &current_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
  


Last Change: 5 October 1995 /