Алгоритм решения двух процессов 1

Вот алгоритм решения двух процессов 1:

turn = 0;
i = 0, j = 1;
do
{
    while (turn != i) ; //if not i's turn , wait indefinitely 
    // critical section

    turn = j; //after i leaves critical section, lets j in

    //remainder section
} while (1); //loop again

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

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

Обновления P0 переключаются после выхода из критической секции, поэтому P1, ожидающий в цикле while, должен иметь возможность войти в критическую секцию. Подскажите, пожалуйста, почему тогда нет прогресса?


operating-system algorithm progress mutual-exclusion
person Figen Güngör    schedule 02.11.2013    source источник

Ответы (3)


arrow_upward
3
arrow_downward

Прогресс вперед определяется следующим образом:

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

Код, который вы написали выше, не удовлетворяет этому, если потоки не сбалансированы, рассмотрим следующий сценарий:

  1. P0 вошла в критическую секцию, завершила ее и установила поворот на P1.
  2. P1 заходит на участок, завершает его, устанавливает поворот обратно на P0.
  3. P1 быстро завершает оставшуюся секцию и хочет снова войти в критическую секцию. Однако P0 по-прежнему держит ход.
  4. P0 останавливается где-то в оставшейся части на неопределенный срок. P1 голодает.

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

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

person Leeor    schedule 02.11.2013
comment
Вы имеете в виду, что P0 не назначил ход 1 после того, как он покинул критическую секцию, тем предложением, что P0 все еще удерживает ход? Потому что в коде после выхода из критической секции он назначает j для поворота, а затем переходит к оставшейся секции. Что ж, пока P0 находится в оставшейся секции, P1 может войти в критическую секцию, потому что это его очередь в соответствии с назначением turn=j. - person Figen Güngör; 03.11.2013
comment
В № 1 ход устанавливается на P1, в № 2 поворот снова устанавливается на P0, и затем он остается таким, даже если P1 завершил оставшуюся часть (быстрее, чем P0) и хочет войти снова. Другими словами, критическая секция не может принадлежать таким образом: P0 -> P1 -> P1, поэтому, если P0 застрянет в оставшейся части, вы застрянете после P0 -> P1. - person Leeor; 03.11.2013
comment
Теперь я вижу свет. Спасибо. - person Figen Güngör; 03.11.2013

arrow_upward
1
arrow_downward

Вы не можете быть уверены в порядке, в котором выполняется код в двух процессах. Когда первый P1 запускается и пытается войти в критическую секцию, ему это не разрешено, потому что настала очередь P0. Итак, P1 не может войти в критическую секцию, даже если в ней нет другого процесса. Поэтому прогресс не выполняется.

person Sven Painer    schedule 02.11.2013
comment
Теперь это имеет смысл. Спасибо. - person Figen Güngör; 02.11.2013
comment
Ему нужно будет только подождать, пока P0 вернет поворот к P1, и тогда он сможет свободно двигаться внутрь. Требование состоит только в том, что запись не будет отложена на неопределенный срок. - person Leeor; 02.11.2013
comment
Да ты прав. Нормальное определение прогресса заключалось бы в том, что ни один процесс не должен голодать, потому что он никогда не попадет в критическую секцию, а другой процесс всегда будет иметь возможность попасть внутрь. Но в определении в вопросе это было определено по-другому. Там сказано, что когда один процесс хочет войти в критическую секцию, а внутри этой критической секции нет процесса, он должен иметь возможность войти сразу. Прогресс в этом определении не выполняется, тогда как прогресс в другом определении выполняется. - person Sven Painer; 03.11.2013
comment
Но как узнать, когда P0 нужно будет войти в критическую секцию? Не будет ли в этом случае P1 ждать бесконечно долго? - person Figen Güngör; 03.11.2013
comment
Извините, но не вижу смысла в вашем вопросе. В моем примере P1 будет ждать, чтобы войти в критическую секцию, но настала очередь P0 войти в нее. Когда P0 пытается войти в критическую секцию, ему это разрешено, потому что сейчас его очередь. В конце критической секции P0 устанавливает очередь на 1, а затем P1 может войти при следующем запуске. Конечно, если P0 никогда не запускается, P1 никогда не сможет войти, но этого не должно быть, если планирование работает правильно. - person Sven Painer; 03.11.2013

arrow_upward
0
arrow_downward

Проблема здесь в том, что это полностью зависит от планирования процессов более низкого уровня. ОС обычно требуется немного времени, чтобы разбудить спящий процесс, и это делается в тот момент, когда процесс, работающий в данный момент на ЦП, добровольно отказывается от управления, выполняя какой-либо блокирующий системный вызов или прерывание по таймеру, когда истекает квант времени. В полной системе SMP это также требует некоторой нетривиальной синхронизации и сигнализации в ядре.

Это означает, что процесс 0 может просто зациклиться на выходе из критической секции и снова войти в нее, при этом процесс 1 никогда не сможет запуститься.

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

person Nikolai Fetissov    schedule 02.11.2013
comment
Что ж, после того, как P0 покидает критическую секцию, он присваивает повороту значение 1, что означает, что он не может пропустить while(turn!=i ); (в то время как (1! = 0) остается истинным, поэтому он ждет, пока P1 не войдет, и не обновит значение поворота до 0). И поскольку он обновил значение поворота до 1, P1 может пропустить while(turn!=i); (пока (1! = 1); условие ложно) и после входа и выхода из критической секции он обновит очередь до 0, и теперь P0 может войти, и так далее. Таким образом, P0 не может зацикливаться до того, как P1 войдет и обновит значение хода. - person Figen Güngör; 02.11.2013