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

Question

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

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 будет выполнено как flag [0] = 1 (устанавливается P0 и turn = 0), и он навсегда застрянет в этом цикле, что является мертвой блокировкой.
Так что алгоритм Петерсона не учитывает этот случай?
В случае, если умирание процесса не должно учитываться при анализе таких алгоритмов, тогда в книге по операционным системам Уильяма Сталлинга приложение A содержит серию алгоритмов для параллелизма, начиная с 4 неверных алгоритмов для демонстрации.Он доказывает их неверность, рассматривая случай умирания процесса (в дополнение к другим случаям) до завершения, но затем утверждает, что алгоритм Петерсона является правильным.Я сталкивался с этим потоком, который подсказывает мне, что существует проблема при рассмотрении процесса N (n> 2), но для двух процессов этот алгоритм работает нормально.
Итак, есть ли проблема в анализеалгоритм (предложенный одним из моих одноклассников, и я полностью его поддерживаю), как обсуждалось выше, или алгоритм Петерсона тоже не претендует на тупик с 2 процессами?

---

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

Answer 1

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

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

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

3) Ожидание границы - если Процесс 1 ожидает, Процесс 0 может войти в свою критическую секцию только один раз, перед процессом1 дан зеленый свет, как объяснено в # 2.

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

Answer 2

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

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

Answer 3

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

Answer 4

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

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

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

Answer 5

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

Тогда оба процесса попадают в состояние ожидания ожидания, как:

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

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

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