Флаги готовности

Строгое чередование

Переменная-замок

Запрет прерываний

Наиболее простым решением поставленной задачи является следующая организация пролога и эпилога:

while (some condition)

{

запретить все прерывания

critical section

разрешить все прерывания

remainder section

}

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

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

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

shared int lock = 0;

while (some condition)

{

while(lock); lock = 1;

critical section

lock = 0;

remainder section

}

Данный алгоритм не удовлетворяет условию взаимоисключения.

Строгое чередование будет также использовать общую для обоих процессов переменную с начальным значением 0. Только теперь она будет играть не роль замка для критического участка, а явно указывать, кто может следующим войти в него. Для i -го процесса это выглядит так:

shared int turn = 0;

while (some condition)

{

while(turn!= i);

critical section

turn = 1-i;

remainder section

}

Данный алгоритм удовлетворяет условию взаимоисключения, но не удовлетворяет условию прогресса.

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

Пусть два процесса имеют разделяемый массив флагов готовности входа процессов в критический участок

shared int ready[2] = {0, 0};

Когда i -й процесс готов войти в критическую секцию, он присваивает элементу массива ready[i] значение равное 1. После выхода из критической секции он, естественно, сбрасывает это значение в 0. Процесс не входит в критическую секцию, если другой процесс уже готов к входу в критическую секцию или находится в ней.

while (some condition)

{

ready[i] = 1;

while(ready[1-i]);

critical section

ready[i] = 0;

remainder section

}

Данный алгоритм удовлетворяет условию взаимоисключения, но не удовлетворяет условию прогресса.