Peterson Lock in a binary tree

Question

I have some doubts about Peterson algorithm in a binary tree.

I am making some exercises of the book "The Art of Multiprocessor Programming" and i'm stuck in chapter 2, ex 13:

"Another way to generalize the two-thread Peterson lock is to arrange a number of 2-thread Peterson locks in a binary tree. Suppose n is a power of two. Each thread is assigned a leaf lock which it shares with one other thread. Each lock treats one thread as thread 0 and the other as thread 1."

That´s OK, but what? If Peterson only treats 2 threads, how will be this tree? One tree with ONE single leaf? (because if I have 2 threads, and each leaf treats 2 threads... the result will be a tree with a single leaf?)

"In the tree-lock’s acquire method, the thread acquires every two-thread Peterson lock fromthat thread’s leaf to the root. The tree-lock’s releasemethod for the tree-lock unlocks each of the 2-thread Peterson locks that thread has acquired, from the root back to its leaf."

What did he mean with that? How can a leaf go through the root node? Very confused!! :S

Thank you guys!

Answer 1

The generalization to use n two-thread Peterson locks and arrange them in a binary tree works as follows:

To acquire the lock:

1. Suppose that there are n threads that want to access to a critical region.
2. The first step uses n/2 two-threads Peterson locks. Then two threads are assigned for each two-threads Peterson lock. At the end of this step only n/2 threads acquired the lock. Those n/2 two-threads Peterson locks are the leaves of the binary tree
3. Similar to the first step, the second step uses n/4 two-threads Peterson locks and two threads are assigned for each Peterson lock (those threads are the "winners" in the first step). Those n/4 Peterson locks are the new nodes of the tree
4. This procedure continues up to it reaches the root, where it's necessary only one Peterson lock. The thread that acquires the last Peterson lock can enter to the critical region.

To release the lock

The thread that acquired the lock must release each Peterson lock in the path that it followed from the corresponding leaf to the root.

I hope this explanation will serve you.