Peterson lock in binary tree

Question

I have some doubts regarding the Peterson algorithm in a binary tree.

I am doing some exercises from the book "The Art of Multiprocessing Programming" and I am stuck in chapter 2, ex 13:

"Another way to generalize Peterson’s two-threaded lock is to organize a series of 2-threaded Peterson locks in a binary tree. Let n be a power of two. Each thread is assigned a leaf lock, which it shares with another thread. Each lock treats one thread as thread 0 and the other - like thread 1. "

This is normal, but what? If Peterson considers only 2 threads, how will it be a tree? One tree with one single leaf? (because if I have 2 threads and each leaf processes 2 threads ... will the result be a tree with a single leaf?)

"In the method of obtaining tree locks, a thread receives every two-threading. Peterson blocks this leaf flow at the root. The tree locks released for the tree lock open each of the 2-thread Petroner locks that the thread acquired, from the root to its leaf."

What did he mean? How does a leaf go through the root of a node? Very confused !!: S

Thanks guys!

Answer 1

A generalization to the use of n double-threaded Peterson locks and placing them in a binary tree works as follows:

To get a lock:

• Suppose there are n threads that want to access a critical region.
• At the first stage, n / 2 double-threaded Peterson locks are used. Then, for each two-threaded Peterson block, two threads are assigned. At the end of this step, only n / 2 threads acquired the lock. These n / 2 double-threaded Peterson locks are leaves of a binary tree.
• As in the first stage, the second stage uses n / 4 dual-threading. Peterson locks and two threads are assigned for each Peterson lock (these flows are the “winners” in the first step). These n / 4 Peterson locks are the new nodes of the tree
• This procedure continues until it reaches the root, where only one Peterson block is required. A thread that gains the last Peterson lock can enter a critical area.

To release the lock

A thread that has acquired a lock should release every Peterson lock in the path that it followed, from the corresponding leaf to the root.

I hope this explanation serves you.