пожалуйста, сломайте этот алгоритм синхронизации

Question

P1 и P2 - процессы или узлы в кластере. f1 и f2 - их флаги. Предположим, сильная модель памяти, и что оба процесса могут быть перезапущены в любой момент, и что перезапуск процесса очищает его флаг, вот алгоритм, который я придумал и который еще не смог сломать, но это беспокоит меня, потому что это не доказано теоретически выглядит слишком просто по сравнению с Петерсоном.

P1 start:
set f1
if f2 set then clear f1, wait some, goto start
else enter critical section
do whatever
clear f1

P2 start:
set f2
if f1 set then clear f2, wait some, goto start
else enter critical section
do whatever
clear f2

Кто-нибудь может видеть поток? За исключением случаев, когда один из процессов может голодать, если быстро войти в раздел?

Answer 1

Если операция «если X установлен, то очистить Y» не является атомарной, существует потенциальное состояние гонки, которое может помешать любому проникнуть внутрь критической секции. Я попытался обрисовать в общих чертах поток ниже:

P1: set f1
P2: set f2
P1: is f2 set?
P2: is f1 set?
P1: yes, clear f1
P2: yes, clear f2
P1: start wait
P2: start wait
P1: end wait
P2: end wait
P1: goto start
P2: goto start

Это может продолжаться вечно, пока не будет разницы в распределении, выполняемом планировщиком задач, или пока время ожидания для двух P не будет отличаться друг от друга.

Answer 2

Легко доказать, что этот алгоритм гарантирует взаимное исключение. Если оба процесса находятся в критической секции одновременно, это означает, что оба флага были установлены и F1 был установлен до F2 (из кода P1), а также F2 был установлен до F1 (из кода P2) ). Это невозможно, поэтому взаимное исключение гарантировано.

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

Answer 3

Ну, кроме проблемы с голодом, других проблем не вижу.

Алгоритм Петерсона, однако, гарантирует справедливость - каждый процесс гарантированно получает критическую секцию, как только она станет следующей, - которую ваш алгоритм не обеспечивает.

Мне любопытно, почему вы думаете, что алгоритм Петерсона менее прост; это не так уж отличается от того, что у вас есть.

P1 start:
set f1
x = 2
while f2 and (x == 2) wait
enter critical section, etc.
clear f1