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

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

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), и он навсегда останется в этом цикле, что является мертвой блокировкой.
Так не учитывает ли алгоритм Петерсона этот случай?
В случае, если смерть процесса не должна учитываться при анализе таких алгоритмов, то в «Книге операционных систем» Уильяма Столлинга, приложение А, содержится серия алгоритмов параллелизма, начиная с 4 неверных алгоритмов для демонстрации. Он доказывает их неправильность, рассматривая случай смерти процесса (в дополнение к другим случаям) до завершения, но затем утверждает, что алгоритм Петерсона верен. Я наткнулся на этот поток, который дал мне понять, что существует проблема при рассмотрении процесса N (n> 2), но для двух процессов этот алгоритм работает нормально.
Так есть ли проблема в анализе алгоритма (предложенного одним из моих одноклассников, и я полностью поддерживаю его), как обсуждалось выше, или алгоритм Петерсона также не требует тупика с двумя процессами?


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

15
задан Community 23 May 2017 в 12:10
поделиться