Объясните, почему этот алгоритм не гарантирует взаимного исключения

Рассмотрим следующую попытку «занятого ожидания» для алгоритма взаимного исключения. Объясните, почему это не гарантирует взаимного исключения. Я не могу понять, почему это не так, для меня это выглядит так, может кто-нибудь объяснить, почему это не так?

/*Process0 */
while (flag[1]) do {/* nothing */}
flag[0] = true;
/*critical section */
flag[0] = false;

/*Process1 */
while (flag[0]) do {/* nothing */}
flag[1] = true;
/*critical section */
flag[1] = false;

concurrency algorithm mutual-exclusion
person SSI    schedule 14.12.2014    source источник

Ответы (2)


arrow_upward
2
arrow_downward

Это не работает, потому что вещи, которые вы, по-видимому, считаете атомарными (т. е. неделимыми), на самом деле таковыми не являются.

Прямо сейчас вы, кажется, предполагаете, что как только цикл while в одном процессе завершится, выполнение будет продолжаться, по крайней мере, на протяжении всего присваивания flag[N] без каких-либо переключений контекста.

Это просто неправда. Для удобства разобьем каждый процесс на части A (цикл while) и B (критическая секция). Вполне возможно иметь последовательность вроде:

1A
2A
1B [for a while, then interrupted by context switch]
2B [for a while, then interrupted by context switch]
1B [resumes after context switch]
2B [resumes after context switch]

Это именно такой код, который работает в 99,9% случаев. Вы, вероятно, можете тестировать его как сумасшедший в течение нескольких месяцев подряд, и покажется, что он работает идеально — затем вы продемонстрируете его перед клиентом, он рухнет, сгорит и уничтожит все, что его окружает. Затем вы отправляете его обратно в лабораторию, и как бы они ни старались, они не могут воспроизвести проблему.

person Jerry Coffin    schedule 14.12.2014
comment
You can probably test it like crazy for months on end, and it'll seem like it works perfectly--then you demo it in front of a customer, it crashes, burns, and destroys its surroundings. Then you send it back to the lab, and try though they will, they can't duplicate the problem.------ ха-ха-ха(ROFL)... - person Am_I_Helpful; 15.12.2014

arrow_upward
0
arrow_downward

Здесь могут произойти две вещи.

  1. Вы можете иметь два (или более) процесса, работающих одновременно. Любой может схватить

    while (flag[1]) do {/* ничего */} // Оба процесса могут видеть снятие флага одновременно

     flag[0] = true;  // Two process set the flag

  2. У вас может быть переключатель контекста

    while (flag[1]) do {/* ничего */} // Здесь процесс блокируется

        // Some other process sets flag [0]

 flag[0] = true;  // Gets set for a second time
person user3344003    schedule 14.12.2014