Контрастные алгоритмы Петерсона и Деккера

Я пытаюсь понять алгоритмы Петерсона и Деккера, которые очень похожи и имеют много симметрий.

Я попытался сформулировать алгоритмы на неформальном языке следующим образом:

Peterson's: "I want to enter."                 flag[0]=true;
            "You can enter next."              turn=1;
            "If you want to enter and          while(flag[1]==true&&turn==1){
            it's your turn I'll wait."         }
            Else: Enter CS!                    // CS
            "I don't want to enter any more."  flag[0]=false;

Dekker's:   "I want to enter."                 flag[0]=true;
            "If you want to enter              while(flag[1]==true){
             and if it's your turn               if(turn!=0){
             I don't want to enter any more."      flag[0]=false;
            "If it's your turn                     while(turn!=0){
             I'll wait."                           }
            "I want to enter."                     flag[0]=true;
                                                 }
                                               }
            Enter CS!                          // CS
            "You can enter next."              turn=1;
            "I don't want to enter any more."  flag[0]=false;

Разница, кажется, заключается в том, где "You can enter next."происходит и что "if it's your turn I don't want to enter any more."происходит у Деккера.

В алгоритме Петерсона эти два процесса кажутся доминирующими. Кажется, что процесс проталкивается в критическую секцию, если не очередь другого.

И наоборот, в алгоритме Деккера эти два процесса кажутся покорными и вежливыми. Если оба процесса хотят войти в критическую секцию, и теперь очередь другого, процесс решает больше не хотеть входить. (Это нужно для голода-свободы? Зачем?)

Как именно эти алгоритмы отличаются? Я полагаю, что когда оба процесса пытаются войти в критическую секцию, в системе Петерсона, процесс говорит: «Я вхожу», а в Деккере - «Вы можете войти». Может кто-то прояснить, как процессы ведут себя в каждом алгоритме? Правильный ли мой способ выразить это в неформальных терминах?

Ваши неофициальные описания алгоритмов замечательны.

Я думаю, что в обоих случаях автор пытался найти самое простое из возможных решений, которое гарантировало бы как взаимное исключение, так и тупиковую свободу. Ни один из этих алгоритмов не является голодным или справедливым.[ed: как отмечено в комментариях, алгоритм Петерсона свободен от голода и справедлив]. Решение Dekker было первым алгоритмом взаимного исключения, использующим только инструкции загрузки и сохранения. Это было введено в Dijkstra, Edsger W .; «Сотрудничество последовательных процессов», в F. Genuys, ed. Языки программирования: Институт перспективных исследований НАТО , стр. 43-112, Academic Press, 1968 . Если вы прочитаете статью, вы увидите, как Дейкстра работает через несколько попыток, распознавая проблему с каждой из них, а затем добавляя немного больше для следующей версии. Отчасти неэффективность его алгоритма объясняется тем, что он начинает с алгоритма поворота, а затем пытается изменить его, чтобы процессы могли развиваться в любом порядке. (Не просто 0,1,0,1, ...)

Алгоритм Петерсона был опубликован в 1981 году, после более чем десятилетнего опыта и ретроспективного анализа алгоритма Деккера. Петерсон хотел гораздо более простой алгоритм, чем Деккер, чтобы доказательство правильности было намного проще. Вы можете видеть, что он чувствовал некоторое разочарование в сообществе по названию своей статьи. Петерсон, GL; «Мифы о проблеме взаимного исключения», инф. Proc. Lett. 12 (3): 115-116, 1981, Очень быстро читается и очень хорошо написано. (И грубые замечания о формальных методах бесценны.) В работе Петерсона также обсуждается процесс, на котором он построил свое решение из более простых попыток. (Поскольку его решение проще, требуется меньше промежуточных шагов.) Обратите внимание, что основное отличие (то, что вы называете «доминированием», а не «покорностью») состоит в том, что Петерсон начинал с нуля (а не из алгоритма взятия поворотов, с которого Дейкстра начинал ) его цикл ожидания проще и эффективнее. Он понимает, что он может просто обойтись простым циклическим тестированием, в то время как Дейкстре пришлось каждый раз отступать и повторять попытки.

Я чувствую, что должен также упомянуть классическую бумагу алгоритма Пекарни Лампорта : Лампорт, Лесли; «Новое решение проблемы параллельного программирования Дейкстры», Comm ACM 17 (8): 453-455, 1974 . Алгоритм Bakery, возможно, проще, чем алгоритм Dekker (и, конечно, проще в случае более чем 2 процессоров), и специально разработан для обеспечения отказоустойчивости. Я специально упоминаю это по двум причинам. Во-первых, потому что он дает немного истории об определении проблемы взаимного исключения и пытается решить ее до 1974 года. Во-вторых, потому что алгоритм Bakery демонстрирует, что для решения проблемы взаимного исключения не требуется аппаратная атомарность.

Наконец, мой любимый Лампорт, Лесли; «Быстрый алгоритм взаимного исключения», ACM Trans. Комп. Sys. 5 (1): 1-11, 1987, В этой статье Лэмпорт пытался оптимизировать решение проблемы взаимного исключения в (общем) случае, когда для критической секции мало споров. Опять же, это гарантирует взаимное исключение и тупиковую свободу, но не справедливость. Это (я считаю) первый алгоритм взаимного исключения, использующий только обычные операции чтения и записи, которые могут синхронизировать N процессоров за O (1) время, когда нет конфликтов. (Когда возникает конфликт, он возвращается к тесту O (N).) Он дает неофициальную демонстрацию того, что лучшее, что вы можете сделать в случае отсутствия конкуренции, - это семь обращений к памяти. (Деккер и Петерсон оба делают это с 4, но они могут обрабатывать только 2 процессора, когда вы расширяете их алгоритмы до N, они должны добавить дополнительные O (N) доступы.)

В целом: я бы сказал, что сам алгоритм Деккера интересен в основном с исторической точки зрения. Статья Дейкстры объяснила важность проблемы взаимного исключения и продемонстрировала, что она может быть решена. Но в течение многих лет назад были найдены более простые (и более эффективные) решения, чем у Dekker.

В следующей статье мы даем формальные модели для алгоритмов Петерсона и Деккера (и некоторых других), и мы использовали средство проверки моделей для доказательства их свойств. Пожалуйста, найдите наши результаты в таблице ниже (столбцы «Deadlock» и «Divergent» относятся к нашим моделям, «ME» = TRUE означает, что алгоритм правильный, «Overtaking» = TRUE означает, что он справедливый).

Р. Меолич, Т. Капус, З. Брезочник. ACTLW - логика дерева вычислений на основе действий с оператором, кроме оператора. Информатика, 178 (6), с. 1542-1557, 2008.

https://doi.org/10.1016/j.ins.2007.10.023

Алгоритм Петерсона оказывает более жесткое давление на вход в критическую секцию, поскольку алгоритм Деккера относительно мягче и менее агрессивен. Чтобы сделать это более понятным, давайте посмотрим на пример об иранской культуре. Прежде чем перейти к этому примеру, полезно знать, что иранцы по-настоящему мягко относятся друг к другу, когда входят куда-то! Похоже, двое иранских мужчин собираются войти в дом, и в этот дом есть только одна дверь.

А теперь представьте себе двух мужчин из другой культуры (культура зомби ), которые на самом деле не слишком заботятся друг о друге, когда входят куда-то ( это вопрос уважения, хочет ли он войти или нет ).

Для уточнения информации о проблеме можно сказать, что:

• Два иранца = два процесса с использованием алгоритма Деккера
• Два зомбиана = два процесса с использованием алгоритма Петерсона

Итак, давайте выясним, что делается в каждом алгоритме ( культуре ). Следующие комментарии относятся к первому иранцу, который собирается войти в дом при использовании алгоритма Деккера :

p0:
   wants_to_enter[0] ← true // Goes through the house entrance
   while wants_to_enter[1] { // If the other man wants to enter too
      if turn ≠ 0 { // Then see if it is your turn or not
         wants_to_enter[0] ← false // If it is not your turn don't go furthur
         while turn ≠ 0 { // and wait until it is your turn
           // busy wait
         }
         wants_to_enter[0] ← true // when it is your turn go through the door
      }
   }

   // critical section
   ...
   turn ← 1
   wants_to_enter[0] ← false // Set the turn for the other man
   // remainder section

У нас также есть два зомби, которые собираются войти в дом, используя алгоритм Петерсона . Этот идет следующим образом:

P0:     
  flag[0] = true; // Goes through the house entrance
  turn = 1; // Set the turn for himself
  while (flag[1] && turn == 1) // Wait until the other one is going in
  {
   // busy wait
  }
   // critical section
      ...
   // end of critical section
  flag[0] = false; // Done going inside

Важно отметить, что оба они не заходят внутрь, в то время как другой делает это ( взаимное исключение ), но иранский народ намного мягче.