The tree is a binary tree consisting of 2n−1 nodes. Each leaf is owned by a single, statically determined, thread. Each node’s two children are linked as partners. One partner is statically designated...

The tree is a binary tree consisting of 2n−1 nodes. Each leaf is owned by a single, statically determined, thread. Each node’s two children are linked as partners. One partner is statically designated as active, and the other aspassive.Fig.18.16illustrates the tree structure. Each thread keeps track of the current sense in a thread-local variable. When a thread arrives at a passive node, it sets its active partner’s sense field to the current sense, and spins on its own sense field until its partner changes that field’s value to the current sense. When a thread arrives at an active node, it spins on its sense field untilits passive partner sets it to the current sense. When the field changes, that particular barrier is complete, and the active thread follows the parent reference to its parent node. Note that an active thread at one level may become passive at the next level. When the root node barrier is complete, notifications percolate down the tree. Each thread moves back down the tree setting its partner’s sense field to the current sense.