Невозможно понять правильность алгоритма Петерсона

У меня есть сценарий для обсуждения здесь для алгоритма Петерсона:

flag[0]   = 0;
flag[1]   = 0;
turn;

P0: flag[0] = 1;                                       
    turn = 1;                                               
    while (flag[1] == 1 && turn == 1)                        
    {                                                       
           // busy wait                                             
    }                                                                                      
    // critical section                                     
       ...                                                     
    // end of critical section                              
    flag[0] = 0;   

P1: flag[1] = 1;                                       
    turn = 0;                                               
    while (flag[0] == 1 && turn == 0)                        
    {                                                       
           // busy wait                                             
    }                                                                                      
    // critical section                                     
       ...                                                     
    // end of critical section                              
    flag[1] = 0;

Предположим, что оба процесса запуска выполняются одновременно .P0 устанавливает флаг [0] = 1 и умирает. Затем начинается P1. Его условие while будет выполняться как флаг [0] = 1 (установленный P0 и turn = 0), и он будет застревать в этом цикле навсегда, что является мертвой блокировкой.
Итак, алгоритм Петерсона не учитывает этот случай?
В случае, если процесс анализа не учитывается при анализе таких алгоритмов, то в книге "Операционная система" Уильяма Столлинга в приложении A содержится серия алгоритмов для concurrency, начиная с 4 неправильного алгоритма демонстрации. Это доказывает их неверность, рассматривая случай смерти процесса (в дополнение к другим случаям) до завершения, но затем утверждает, что алгоритм Петерсона является правильным. Я наткнулся на этот поток, который подсказывает, что существует проблема при рассмотрении N процесса (n > 2), но для двух процессов этот алгоритм отлично работает.
Итак, есть ли проблема в анализе алгоритма (предложенного одним из моих одноклассников, и я полностью его второй), как обсуждалось выше, или алгоритм Петерсона не требует взаимоблокировки с 2 процессами?

В этой статье Некоторые мифы о знаменитых алгоритмах взаимного исключения автор заключил Петерсон никогда не утверждал, что его алгоритм обеспечивает ограниченный обход.
Может ли неограниченный обход считаться бесконечным, как в случае тупика? В этом случае у нас может быть меньше проблем с принятием того, что алгоритм Петерсона может привести к тупиковой ситуации.

Ответы

Ответ 1

Конечно, вы могли бы написать код, который бы породил необработанное исключение, но алгоритм предполагает, что исполняемый процесс всегда устанавливает свой флаг в false, после выполнения его критической секции. Поэтому алгоритм Петерсона пропускает 3 теста для критических секций.

1) Взаимное исключение - флаг [0] и флаг [1] могут быть истинными, но поворот может быть только 0 или 1. Поэтому может выполняться только одна из двух критических секций. Другой будет ожидать отжима.

2) Прогресс. Если процесс 0 находится в критическом разделе, тогда поверните = 0, а флаг [0] будет истинным. Как только он завершит критический раздел (даже если произойдет что-то катастрофическое), он должен установить флаг [0] в значение false. Если процесс 1 был ожидающим вращения, он теперь будет свободен как флаг [0]!= True.

3) Bound-waiting - Если процесс 1 ждет, Process 0 может только ввести его в критический раздел один раз, прежде чем процесс 1 получит зеленый свет, как описано в № 2.

Проблема с алгоритмом Петерсона заключается в том, что в современной архитектуре кеш процессора может испортить требование взаимного исключения. Эта проблема называется кэш-когерентностью, и возможно, что кеш, используемый Процессами 0 на CPU 0, устанавливает флаг [0] равным true, тогда как Process 1 на CPU 1 все еще считает флаг [0] ложным. В этом случае будут входить оба критических раздела, а BANG... взаимное исключение не удастся, и теперь возможны условия гонки.

Ответ 2

Вы правы, алгоритм Петерсона предполагает, что процессы не прерываются при выполнении части алгоритма для синхронизации. У меня нет доступа к книге, которую вы упомянули, но, возможно, другие алгоритмы неверны, поскольку они не учитывают процессы, выходящие за пределы частей синхронизации (что еще хуже)?

Примечание: хотя исторически все еще интересно, алгоритм Петерсона также делает предположения о том, что работа с памятью недействительна с сегодняшним оборудованием.

Ответ 3

Большинство алгоритмов блокировки не учитывают процесс, когда он находится в критическом разделе (как другие процессы могут различать процесс, умерший после блокировки, по сравнению с процессом, который занимает много времени?).

Однако процесс, умирающий, когда он не находится в критическом разделе, не должен препятствовать вхождению или выходу других процессов. Например, критический раздел, где два процесса "по очереди" для входа в критический раздел проблематичен; если один процесс умирает вне критической секции, второй ждет навсегда, чтобы первый имел свою очередь. Это, возможно, то, о чем говорил ваш учитель.

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

Ответ 4

Даже некоторые из методов семафора терпят неудачу, если мы предполагаем это преждевременное умирание процессов (попробуйте проблему производителя/потребителя) Таким образом, мы не можем сказать, что алгоритм неверен, но только потому, что он не был создан для этой цели, как мы его видим. Все они ошибочно понятны.

Ответ 5

Я согласен с Фабио. Вместо того, чтобы говорить "P0 устанавливает флаг [0] = 1 и умирает", я хотел бы рассмотреть сценарий, в котором P0 выгружен планировщиком, а P1 запланирован сразу же после того, как P0 устанавливает свой флаг [0] до 1.

Затем оба процесса попадают в ловушку в ожидании занятости, например:

Флаг (0) = 1, флаг (1) = 1 и turn = 0. Это означает, что P1 будет занят, ожидая, когда условие во время цикла будет истинным.

Теперь, если P1 выгружен, скажем, из-за тайм-аута, а P0 запланирован планировщиком, тогда: Флаг (0) = 1, флаг (1) = 1 и turn = 1. Это означает, что P0 также будет занят, ожидая, когда условие while пока истинно.

Теперь оба процесса ожидают друг друга, и происходит взаимоблокировка. Я не знаю, почему это решение настолько знаменито или нам что-то не хватает...?