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!
The generalization to use n two-thread Peterson locks and arrange them in a binary tree works as follows:
To acquire the lock:
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.
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With