Учитывает ли алгоритм двухстороннего исключения Петерсона процессы умирания?

9

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

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

введите описание изображения здесь

Что произойдет, если процесс, который достигает критического раздела, сначала умирает, прежде чем покинуть его?

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

Ответы:

1

Это зависит от того, как реализованы блокировки. Если вы сделаете это, как в статье в Википедии, т.е. защитите критическую секцию с одним логическим значением на процесс¹, у вас наверняка возникнут проблемы. Если один процесс умирает, он никогда не сбрасывает свой флаг, поэтому другой процесс зацикливается навсегда.

На практике вы можете защитить свой код от многих способов смерти. Например, возьмем эту реализацию в стиле Java:

flag[1] = true;
turn = 1;
while ( flag[0] == true && turn == 1 ) { Thread.yield(); }
try {
  // critical section
}
finally {
  flag[1] = false;
}

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

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


  1. В любом случае, это плохо масштабируется.
  2. В Java, я думаю, finalizeдолжен выполняться даже на kill, но это не гарантируется спецификацией. kill -9Вероятно, это смертный приговор для любого решения, которое требует, чтобы процесс умирания что-то сделал.
Рафаэль
источник
1

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

N

vonbrand
источник