R-bounded waiting for the Peterson Lock
concurrency
Solution
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 D0j ➝ D1k 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. CS0j ➝ CS1k 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.
Problem
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 DAj ➝ DBk ⇒ CSAj ➝ CSBk+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. DA is the "doorway" event for a thread A, which is the event of the request to enter the critical section. CSA is the critical section event for thread A. For any event XA, XAi 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 } ```