R 界等待彼得森锁

Question

在多处理器编程的艺术中，修订版。第一版，第 1 章。 2、练习9如下（转述）：

定义 r 有界等待互斥算法，表示 D_A^j ➝ D_B^k ⇒ CS_A^j ➝ CS_B^k+r。有没有办法为 Peterson 算法定义一个入口，使其提供 r 有限等待？

本书使用➝定义事件优先级的总顺序，其中X➝Y表示事件X在Y开始之前开始并完成。 D_A是线程A的“门口”事件，即请求进入临界区的事件。 CS_A 是线程 A 的临界区事件。

对于任何事件 X_A，X_Aⁱ 是事件 X 在线程 A 上的第 i 次执行。

现在回答问题：在我看来，Peterson 算法是完全公平的（0 界等待）。此外，我认为 r 有界等待意味着 k 有界等待所有 k > r。那么这个问题就没有意义了，因为 Peterson 应该满足 r 有界等待所有 r。

问题是否要求“简化”Peterson 算法，因为它要求放宽约束？

这是自学，不是作业。

Peterson锁算法的代码，摘自书中：

1 class Peterson implements Lock {
2     // thread-local index, 0 or 1
3     private volatile boolean[] flag = new boolean[2];
4     private volatile int victim;
5     public void lock() {
6         int i = ThreadID.get();
7         int j = 1 - i;
8         flag[i] = true; // I’m interested
9         victim = i; // you go first
10        while (flag[j] && victim == i) {}; // wait
11     }
12     public void unlock() {
13         int i = ThreadID.get();
14         flag[i] = false; // I’m not interested
15     }
16 }

Answer 1

你是对的，两个线程的 Peterson 算法是公平的（又名先来先服务）。

让我们（很自然地）将门口部分定义为代码中的第 6-9 行，将等待部分定义为第 10 行。假设 D₀^j ➝ D₁^k 并且两个线程都是在相应的等候区。在这种情况下，

flag[0]==true

、

flag[1]==true

和

victim==1

；因此，线程 0 可以退出其等待部分，而线程 1 则不能。因此，线程 0 首先执行，即 CS₀^j ➝ CS₁^k 并且 Peterson 锁具有 0 界等待，即是公平的。

不过我觉得这个问题确实有道理。这是一个练习，是本节的第一个练习，所以不是很难 - 但我认为对于检查概念是否被理解仍然有用。书中并没有说彼得森锁是公平的；而是说彼得森锁是公平的。相反，它要求（也许以一种有点复杂的方式）将其作为练习来证明。

Answer 2

我将问题解释为“是否可以修改 Peterson 算法的门口部分，以便

1

等待界限增加到任意

r

”。我认为这是不可能的：

与已完成等待并进入 CS 的线程相比，正在等待的线程的状态是无法区分的。在将

r

从 1 提高到某个任意值的程序逻辑中，我们需要在门口有某种条件，允许我们“跳转”另一个线程（不是等待，而该线程继续等待）。

除了我们需要为此实现的任何计数器之外，这还要求我们知道该线程是否正在等待（在这种情况下我们可能会跳过它），或者它是否在 CS 中（在这种情况下我们永远不应该跳过它）它）。

但不能100%确定这个答案，或者我是否正确解释了这个问题。正如 Alexey 提到的，如果这个问题要求我们得到某个常数限制的等待时间，那么这已经完成了，因为我们有以下保证：

如果一个线程先于另一个线程完成门口部分，它将先于该线程进入临界区。当然，另一个线程（在我们之后完成其门口部分）将设置

victim = them

，因此直到

victim

被更改（谁会更改它，我们正在等待！），该线程将等待。而且因为 Peterson 没有死锁，所以我们必须在某个时刻进入 CS，因此它必须在另一个线程之前。