concurrency - R界等待彼得森锁

Question

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


定义r边界等待互斥算法，以表示DAj➝DBk⇒CSAj➝CSBk + r。有没有一种方法可以为Peterson算法定义门口，从而提供r边界等待？


本书使用➝定义了事件优先级的总顺序，其中X➝Y表示事件X在Y开始之前开始并完成。 DA是线程A的“门口”事件，这是请求进入关键部分的事件。 CSA是线程A的关键部分事件。

对于任何事件XA，XAi是线程A上事件X的第i个执行。

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

这个问题是否要求“简化”彼得森算法，因为它要求放宽约束？

这是自学而非功课。

彼得森锁算法的代码，摘自本书：

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行。假设D0j➝D1k并且两个线程都在其相应的等待部分中。在这种情况下，flag[0]==true，flag[1]==true和victim==1；因此，线程0可能退出其等待部分，而线程1可能不会退出。因此，线程0首先进入，即CS0j➝CS1k，并且Peterson锁具有0界等待，即公平。

但是我认为这个问题确实有意义。这是一项练习，因此本节的第一个练习不是很困难-但我认为检查概念是否理解仍然很有用。这本书并没有说彼得森锁是公平的。相反，它要求（也许以某种复杂的方式）证明它是一种练习。