R-bounded waiting for the Peterson Lock

Question

In The Art of Multiprocessor Programming, rev. 1st Ed., in Ch. 2, Excercise 9 is as follows (paraphrased):

Define r-bounded waiting for a mutex algorithm to mean that D_A^j ➝ D_B^k ⇒ CS_A^j ➝ CS_B^k+r. Is there a way to define a doorway for the Peterson algorithm such that it provides r-bounded waiting?

The book uses ➝ to define a total order on the precedence of events, where X ➝ Y means event X started and completed before Y started. D_A is the "doorway" event for a thread A, which is the event of the request to enter the critical section. CS_A is the critical section event for thread A.

For any event X_A, X_Aⁱ is the the i-th execution of event X on thread A.

Now getting to the question: it seems to me that the Peterson algorithm is completely fair (0-bounded waiting). Further, I think that r-bounded waiting implies k-bounded waiting for all k > r. Then this question does not make sense, since Peterson should satisfy r-bounded waiting for all r.

Is the question asking for a "simplification" of the Peterson algorithm, since it is requesting a relaxation of constraints?

This is self-study, not homework.

The code of the Peterson lock algorithm, taken from the book:

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

You are right, the Peterson algorithm for two threads is fair (aka first come first served).

Let's (quite naturally) define the doorway section to be lines 6-9 in the code, and the waiting section to be line 10. Let's assume D₀^j ➝ D₁^k and both thread are in their corresponding waiting sections. In this case, flag[0]==true, flag[1]==true, and victim==1; therefore, thread 0 may exit its waiting section while thread 1 may not. So, thread 0 goes first, i.e. CS₀^j ➝ CS₁^k and Peterson lock has 0-bounded waiting, i.e. is fair.

However I think the question does make sense. It's an exercise, the first one for the section so not very hard - but still I think useful to check if the concepts are understood. The book does not say that the Peterson lock is fair; instead, it asks (perhaps in a bit convoluted way) to prove it as an exercise.