concurrency - 二叉树中的彼得森锁

Question

我对二叉树中的彼得森算法有一些疑问。

我正在做“多处理器编程的艺术”这本书的一些练习，但我被困在第 2 章，前 13 章:

“另一种概括双线程 Peterson 锁的方法是安排
二叉树中的许多 2 线程 Peterson 锁。假设 n 是 2 的幂。每个线程都分配了一个叶锁，它与另一个线程共享。每把锁
将一个线程视为线程 0，将另一个线程视为线程 1。”

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

"在树锁的获取方法中，线程获取每两个线程
Peterson 锁定从该线程的叶子到根。树锁的释放方法为
树锁解锁线程已获取的每个 2 线程 Peterson 锁，
从根到叶。”

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

谢谢你们!

Answer 1

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

获取锁:

假设有 n 个线程想要访问临界区。

第一步使用 n/2 个双线程 Peterson 锁。然后为每个双线程彼得森锁分配两个线程。在这一步结束时，只有 n/2 个线程获得了锁。那些 n/2 个双线程 Peterson 锁是二叉树的叶子

与第一步类似，第二步使用 n/4 个双线程 Peterson 锁，并为每个 Peterson 锁分配两个线程(这些线程是第一步中的“赢家”)。那些 n/4 个 Peterson 锁是树的新节点

这个过程一直持续到它到达根部，在那里只需要一个 Peterson 锁。获取最后一个 Peterson 锁的线程可以进入临界区。

解除锁定

获取锁的线程必须释放它从相应叶子到根所遵循的路径中的每个 Peterson 锁。

我希望这个解释对你有用。