彼得森锁在二叉树中

Question

我对二叉树中的Peterson算法有些怀疑.

我正在做一些关于"多处理器编程的艺术"一书的练习,我被困在第2章,前13:

"推广双线程Peterson锁的另一种方法是在二叉树中安排一些2线程的Peterson锁.假设n是2的幂.每个线程被分配一个叶子锁,它与另一个线程共享.每个锁将一个线程视为线程0,另一个线程视为线程1."

没关系,但是什么？如果Peterson只处理2个线程,这棵树怎么样？一棵树有一片叶子？(因为如果我有2个线程,并且每个叶子处理2个线程......结果将是一个带有单个叶子的树？)

"在树锁的获取方法中,线程获取每个双线程的Peterson锁从该线程的叶子到根.树锁的释放方法解​​锁了线程获取的每个2线程Peterson锁,来自根回到它的叶子."

他的意思是什么？叶子如何通过根节点？非常困惑!!:S

感谢你们!

Answer 1

使用n个双线程Peterson锁并将它们排列在二叉树中的概括如下:

要获得锁定:

1. 假设有n个线程想要访问关键区域.
2. 第一步使用n/2双线程Peterson锁.然后为每个双线程Peterson锁分配两个线程.在此步骤结束时,只有n/2个线程获得了锁定.那些n/2双线程的Peterson锁是二叉树的叶子
3. 与第一步类似,第二步使用n/4双线程Peterson锁,并为每个Peterson锁分配两个线程(这些线程在第一步中是"赢家").那些n/4 Peterson锁是树的新节点
4. 这个过程一直持续到达根,只需要一个Peterson锁定.获取最后一个Peterson锁的线程可以进入关键区域.

释放锁定

获取锁的线程必须释放每个Peterson锁从它从相应的叶到根的路径.

我希望这个解释能为你服务.