R-ограниченное ожидание блокировки Петерсона

В искусстве многопроцессорного программирования, об. 1-е изд., Гл. 2, Упражнение 9 выглядит следующим образом (перефразировано):

Определить r-ограниченное ожидание того, что алгоритм mutex означает, что D A j ➝ D B k ⇒ CS A j ➝ CS B k + r. Есть ли способ определить дверной проем для алгоритма Петерсона, так что он обеспечивает r-ограниченное ожидание?

В книге используется ➝, чтобы определить общий порядок в приоритете событий, где X ➝ Y означает, что событие X началось и завершилось до начала Y. D A является событием "doorway" для потока A, который является событием запроса для входа в критический раздел. CS A - это событие критического сечения для потока A.

Для любого события X A X A i является i-м исполнением события X в потоке A.

Теперь перейдем к вопросу: мне кажется, что алгоритм Петерсона вполне справедлив (0-ограниченное ожидание). Далее, я думаю, что r-ограниченное ожидание означает k-ограниченное ожидание всех k > r. Тогда этот вопрос не имеет смысла, так как Петерсон должен удовлетворять 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 }

Ответы

Ответ 1

Вы правы, алгоритм Петерсона для двух потоков является справедливым (он же первым пришел первым).

Позвольте (вполне естественно) определить, что секция дверного проема должна быть линиями 6-9 в коде, а секция ожидания - линией 10. Предположим, что D 0 j ➝ D 1 k и оба потока находятся в соответствующих сегментах ожидания. В этом случае flag[0]==true, flag[1]==true и victim==1; поэтому нить 0 может выйти из своей секции ожидания, пока нить 1 не может. Итак, сначала идет нить 0, то есть CS 0 j ➝ CS 1 k а блокировка Петерсона имеет 0-ограниченную ожидание, т.е. справедливо.

Однако я думаю, что этот вопрос имеет смысл. Это упражнение, первое для раздела так не очень сложно - но все же я считаю полезным проверить, понятны ли понятия. В книге не говорится, что замок Петерсона справедлив; вместо этого он спрашивает (возможно, немного запутанным образом), чтобы доказать это как упражнение.