Морис Бах - Архитектура операционной системы UNIX

алгоритм semop /* операции над семафором */

входная информация:

(1) дескриптор семафора

(2) список операций над семафором

(3) количество элементов в списке

выходная информация: исходное значение семафора

{

проверить корректность дескриптора семафора;

start:

считать список операций над семафором из пространства задачи в пространство ядра;

проверить наличие разрешений на выполнение всех операций;

for (каждой операции в списке) {

if (код операции имеет положительное значение) {

прибавить код операции к значению семафора;

if (для данной операции установлен флаг UNDO)

скорректировать структуру восстановления для данного процесса;

вывести из состояния приостанова все процессы, ожидающие увеличения значения семафора;

}

else

if (код операции имеет отрицательное значение) {

if (код операции + значение семафора ›= 0) {

прибавить код операции к значению семафора;

if (флаг UNDO установлен)

скорректировать структуру восстановления для данного процесса;

if (значение семафора равно 0)

вывести из состояния приостанова все процессы, ожидающие обнуления значения семафора;

continue;

}

выполнить все произведенные над семафором в данном сеансе операции в обратной последовательности (восстановить старое значение семафора);

если (флаги не велят приостанавливаться)

вернуться с ошибкой;

приостановиться (до тех пор, пока значение семафора не увеличится);

перейти на start; /* повторить цикл с самого начала */

}

else { /* код операции равен нулю */

if (значение семафора отлично от нуля) {

выполнить все произведенные над семафором в данном сеансе операции в обратной последовательности (восстановить старое значение семафора);

if (флаги не велят приостанавливаться) return ошибку;

sleep (до тех пор, пока значение семафора не станет нулевым);

goto start; /* повторить цикл */

}

}

} /* конец цикла */

/* все операции над семафором выполнены */

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

вернуть исходное значение семафора, существовавшее в момент вызова функции semop;

}

Рисунок 11.15. Алгоритм выполнения операций над семафором

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

Перейдем к программе, представленной на Рисунке 11.14, и предположим, что пользователь исполняет ее (под именем a.out) три раза в следующем порядке:

a. out &

a. out a &

a. out b &

Если программа вызывается без параметров, процесс создает набор семафоров из двух элементов и присваивает каждому семафору значение, равное 1. Затем процесс вызывает функцию pause и приостанавливается для получения сигнала, после чего удаляет семафор из системы (cleanup). При выполнении программы с параметром 'a' процесс (A) производит над семафорами в цикле четыре операции: он уменьшает на единицу значение семафора 0, то же самое делает с семафором 1, выполняет команду вывода на печать и вновь увеличивает значения семафоров 0 и 1. Если бы процесс попытался уменьшить значение семафора, равное 0, ему пришлось бы приостановиться, следовательно, семафор можно считать захваченным (недоступным для уменьшения). Поскольку исходные значения семафоров были равны 1 и поскольку к семафорам не было обращений со стороны других процессов, процесс A никогда не приостановится, а значения семафоров будут изменяться только между 1 и 0. При выполнении программы с параметром 'b' процесс (B) уменьшает значения семафоров 0 и 1 в порядке, обратном ходу выполнения процесса A. Когда процессы A и B выполняются параллельно, может сложиться ситуация, в которой процесс A захватил семафор 0 и хочет захватить семафор 1, а процесс B захватил семафор 1 и хочет захватить семафор 0. Оба процесса перейдут в состояние приостанова, не имея возможности продолжить свое выполнение. Возникает взаимная блокировка, из которой процессы могут выйти только по получении сигнала.