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 }

Coop

Could this be migrated to SO, please? I have a feeling it will receive attention from someone who will answer this. – Coop

Sounds to me like it was a much better fit for CS than for SO? – Pacorro

@RonanThibaudau It was, but no was answering there either. I figured there would be more people here, so the chances would be better. – Coop

I saw it was, i still think it should've stayed there, sure there are more people here but i don't think there are "more people that can answer this question". If it was all about people count we would have love history & botanic questions here :) – Pacorro

@RonanThibaudau Well you're right. I can't argue that my foresight was better than your hindsight! – Coop

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.

Disport

I believe, that the Peterson algorithm should be 1-bounded waiting, for more that 2 threads. Is that right? – Pasty

Answer 2

I interpreted the problem as "is it possible to modify the doorway section of the Peterson algorithm such that the 1-waiting bound increases to some arbitrary r". I'd reason that this is impossible:

The state of a thread that is waiting as compared to a thread that has finished waiting and has entered the CS is indistinguishable. In the logic of a program that raises r from 1 to some arbitrary value, we would need some sort of condition during the doorway that allows us to "jump" the other thread (not wait, while that thread continues to wait).

In addition to whatever counter we would need to implement for this, this would require us to know if that thread is waiting (in which case we might skip it), or if it is in the CS (in which case we should never skip it).

But not 100% sure on this answer, or if I'm interpreting the question correctly. as Alexey mentions, if this question is asking us get the waiting bounded by some constant, then this is already done because we have the following guarantee:

If a thread completes the doorway section before another thread, it will enter the critical section before that thread. Certainly the other thread (that completes its doorway section after us), will set victim = them, and so until victim gets changed (and who would change it, we are waiting!), that thread will wait. And because Peterson is deadlock free we must enter the CS at some point, and so it must be before the other thread.

Doge