R-bound等待彼得森锁

Question

在多处理器编程的艺术中,rev.第1版,在Ch.2,练习9如下(转述):

限定R-界定等待互斥算法意味着d _甲^Ĵ ➝d _乙^ķ ⇒CS _甲^Ĵ ➝CS _乙^{ķ+ R}.有没有办法为Peterson算法定义一个门口,以便提供r-bounded等待？

本书使用➝来定义事件优先顺序的总顺序,其中X➝Y表示事件X在Y开始之前开始并完成.D _A是线程A的"门口"事件,它是请求进入关键部分的事件.CS _A是线程A的关键部分事件.

对于任何事件X _A,X _A ⁱ是线程A上事件X的第i次执行.

现在回答这个问题:在我看来,Peterson算法是完全公平的(0-有限等待).此外,我认为r-bounded等待意味着k-bounded等待所有k> r.然后这个问题没有意义,因为彼得森应该满足r-bounded等待所有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

你是对的,两个线程的彼得森算法是公平的(又名先到先得).

让我们(很自然地)定义了门道部是在代码行6-9,和等待部为线10假设d ₀ ^Ĵ ➝d ₁ ^ķ和两个线程都在它们相应的等待部分.在这种情况下,flag[0]==true,flag[1]==true,和victim==1; 因此,线程0可以退出其等待部分,而线程1可以不退出.因此,线程0先行,即CS ₀ ^Ĵ ➝CS ₁ ^ķ和彼得森锁具有0等待界,即是公平的.

不过我认为这个问题确实有意义.这是一个练习,这个部分的第一个练习并不是很难 - 但我认为检查这些概念是否有用仍然很有用.这本书没有说彼得森锁是公平的; 相反,它要求(可能以一种有点复杂的方式)将其证明为一种练习.