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

Бах Морис Дж.

Операции P и V по своему действию похожи на функции sleep и wakeup. Главное различие между ними состоит в том, что семафор является структурой данных, тогда как используемый функциями sleep и wakeup адрес представляет собой всего лишь число. Если начальное значение семафора — нулевое, при выполнении операции P над семафором процесс всегда приостанавливается, поэтому операция P может заменять функцию sleep. Операция V, тем не менее, выводит из состояния приостанова только один процесс, тогда как однопроцессорная функция wakeup возобновляет все процессы, приостановленные по адресу, связанному с событием.

С точки зрения семантики использование функции wakeup означает: данное системное условие более не удовлетворяется, следовательно, все приостановленные по условию процессы должны выйти из состояния приостанова. Так, например,

процессы, приостановленные в связи с занятостью буфера, не должны дальше пребывать в этом состоянии, если буфер больше не используется, поэтому они возобновляются ядром. Еще один пример: если несколько процессов выводят данные на терминал с помощью функции write, терминальный драйвер может перевести их в состояние приостанова в связи с невозможностью обработки больших объемов информации. Позже, когда драйвер будет готов к приему следующей порции данных, он возобновит все приостановленные им процессы. Использование операций P и V в тех случаях, когда устанавливающие блокировку процессы получают доступ к ресурсу поочередно, а все остальные процессы — в порядке поступления запросов, является более предпочтительным. В сравнении с однопроцессорной процедурой блокирования (sleep-lock) данная схема обычно выигрывает, так как если при наступлении события все процессы возобновляются, большинство из них может вновь наткнуться на блокировку и снова перейти в состояние приостанова. С другой стороны, в тех случаях, когда требуется вывести из состояния приостанова все процессы одновременно, использование операций P и V представляет известную сложность.

struct semaphore {

 int lock;

};

Init(semaphore)

struct semaphore semaphore;

{

 semaphore.lock = 1;

}

Pprim(semaphore)

struct semaphore semaphore;

{

 while (read_and_clear(semaphore.lock));

}

Vprim(semaphore)

struct semaphore semaphore;

{

 semaphore.lock = 1;

}

Рисунок 12.7. Операции над семафором, использующие инструкцию read_and_clear

Если операция возвращает значение семафора, является ли она эквивалентной функции wakeup?

while (value(semaphore) ‹ 0) V(semaphore);

Если вмешательства со стороны других процессов нет, ядро повторяет цикл до тех пор, пока значение семафора не станет больше или равно 0, ибо это означает, что в состоянии приостанова по семафору нет больше ни одного процесса. Тем не менее, нельзя исключить и такую возможность, что сразу после того, как процесс A при тестировании семафора на одноименном процессоре обнаружил нулевое значение семафора, процесс B на своем процессоре выполняет операцию P, уменьшая значение семафора до -1 (Рисунок 12.10). Процесс A продолжит свое выполнение, думая, что им возобновлены все приостановленные по семафору процессы. Таким образом, цикл выполнения операции не дает гарантии возобновления всех приостановленных процессов, поскольку он не является элементарным.

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

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

 (1) семафор

 (2) приоритет

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

 0 — в случае нормального завершения

 -1 — в случае аварийного выхода из состояния приостанова по сигналу, принятому в режиме ядра

{

 Pprim(semaphore.lock);

 уменьшить (semaphore.value);

 if (semaphore.value ›= 0)

 {

Vprim(semaphore.lock);

return (0);

 }

 /*

следует перейти в состояние приостанова */

 if (проверяются сигналы) 

{

if (имеется сигнал, прерывающий нахождение в состоянии приостанова) 

{

увеличить (semaphore.value);

if (сигнал принят в режиме ядра) 

{

Vprim(semaphore.lock);

return(-1);

}

else

{

Vprim(semaphore.lock);

longjmp;

}

}

 }

 поставить процесс в конец списка приостановленных по семафору;

 Vprim(semaphore.lock);

 выполнить переключение контекста;

 проверить сигналы (см. выше);

 return(0);

}

Рисунок 12.8. Алгоритм выполнения операции P

Рассмотрим еще один феномен, связанный с использованием семафоров в однопроцессорной системе. Предположим, что два процесса, A и B, конкурируют за семафор. Процесс A обнаруживает, что семафор свободен и что процесс B приостановлен; значение семафора равно -1. Когда с помощью операции V процесс A освобождает семафор, он выводит тем самым процесс B из состояния приостанова и вновь делает значение семафора нулевым. Теперь предположим, что процесс A, по-прежнему выполняясь в режиме ядра, пытается снова заблокировать семафор. Производя операцию P, процесс приостановится, поскольку семафор имеет нулевое значение, несмотря на то, что ресурс пока свободен. Системе придется "раскошелиться" на дополнительное переключение контекста. С другой стороны, если бы блокировка была реализована на основе однопроцессорной схемы (sleep-lock), процесс A получил бы право на повторное использование ресурса, поскольку за это время ни один из процессов не смог бы заблокировать его. Для этого случая схема sleep-lock более подходит, чем схема с использованием семафоров.

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

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

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

{

 Pprim(semaphore.lock);

 увеличить (semaphore.value);

 if (semaphore.value ‹= 0) 

{

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

перевести его в состояние готовности к запуску;

 }

 Vprim(semaphore.lock);

}

Рисунок 12.9. Алгоритм выполнения операции V

Когда блокируются сразу несколько семафоров, очередность блокирования должна исключать возникновение тупиковых ситуаций. В качестве примера рассмотрим два семафора, A и B, и два алгоритма, требующих одновременной блокировки семафоров. Если бы алгоритмы устанавливали блокировку на семафоры в обратном порядке, как следует из Рисунка 12.11, последовало бы возникновение тупиковой ситуации; процесс A на одноименном процессоре захватывает семафор SA, в то время как процесс B на своем процессоре захватывает семафор SB. Процесс A пытается захватить и семафор SB, но в результате операции P переходит в состояние приостанова, поскольку значение семафора SB не превышает 0. То же самое происходит с процессом B, когда последний пытается захватить семафор SA. Ни тот, ни другой процессы продолжаться уже не могут.