Почему это решение Mutex неверно?

Question

Есть 2 процесса P1 и P2, которые могут войти в критическую секцию.

Требования к решению Mutex:

Зона мьютекса - (критическая секция), которая может содержать только один процесс максимум.

Нет взаимной блокировки - процесс вне критической секции не может заблокировать процесс внутри него.

Нет голодания - процесс, заинтересованный во входе в критическую секцию, не должен ждать вечно.

Успех без конфликтов - процесс, заинтересованный во входе в критическую секцию, должен преуспеть в этом, если нет других заинтересованных процессов.

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

то есть, какое требование это не удовлетворяет?

С1 и С2 инициализируются на 1.

P1:  LOOP
        Non-Critical Section
        LOOP UNTIL C2 = 1 END_LOOP;
        C1 := 0;
        Critical Section
        C1 := 1;
END

P2:  LOOP
        Non-Critical Section
        LOOP UNTIL C1 = 1 END_LOOP;
        C2 := 0;
        Critical Section
        C2 := 1;
END

Answer 1

Чтобы интерпретировать вопрос с наилучшими намерениями, я должен был бы предположить, что каждое чтение или запись считаются атомарными и хорошо упорядоченными. Тогда это имеет больше смысла.

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

Однако завершение этого цикла и последующее присваивание (которое остановит завершение другого цикла) не являются атомарными. Поэтому у нас есть следующий возможный сценарий:

P1: exit wait loop because C2 is 1

P2: exit wait loop because C1 is 1
P2: set C2 to 0
P2: enter critical section

P1: set C1 to 0
P1: enter critical section

Вышеуказанное нарушает это первое требование наличия зоны мьютекса. Условия, которые приводят к такому нарушению, обычно известны как состояние гонки.

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

P2: exit wait loop because C1 is 1
P2: set C2 to 0

P1: spin on C2 != 1 for entire time slice

P2: enter critical section
P2: set C2 to 1
P2: exit wait loop because C1 is 1
P2: set C2 to 0

P1: spin on C2 != 1 for entire time slice

P2: enter critical section
P2: set C2 to 1
P2: exit wait loop because C1 is 1
P2: set C2 to 0

P1: spin on C2 != 1 for entire time slice

...

За исключением некоторых условий, маловероятно, что P1 будет голодать вечно. Но поскольку P1 утверждает, что он ждет, он не должен ожидать, что P2 получит несколько трещин в критической секции, прежде чем он получит поворот.

Это также может быть нарушением требования "Успех без конфликтов", но с этим трудно поспорить. Но я хотел бы предложить, что если P2 больше не работает, то подумайте, в каком состоянии C2 может остаться и почему P1 вообще нужно знать о P2.