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

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

Если операция «if X set then clear 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

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

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

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

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

Answer 3

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

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