У меня есть сценарий для обсуждения здесь для алгоритма Петерсона:
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), но для двух процессов этот алгоритм работает нормально.
Так есть ли проблема в анализе алгоритма (предложенного одним из моих одноклассников, и я полностью поддерживаю его), как обсуждалось выше, или алгоритм Петерсона также не требует тупика с двумя процессами?
В этой статье Некоторые мифы о знаменитых алгоритмах взаимного исключения , автор пришел к выводу Петерсон никогда не утверждал, что его алгоритм обеспечивает ограниченный обход.
Можно ли рассматривать неограниченный обход как достижение бесконечности, как в случае тупика? Что ж, в этом случае у нас будет меньше проблем с пониманием того, что алгоритм Петерсона может привести к тупику.