Примитивы межпроцессного взаимодействия

Оба решения — Петерсона и с помощью команды TSL — корректны, но они обла­дают одним и тем же недостатком: наличием активного ожидания. В сущности, оба они реализуют следующий алгоритм: перед входом в критическую область процесс проверяет, можно ли это сделать. Если нельзя, процесс попадает в цикл, ожидая разрешения на вход в критическую область.

Этот алгоритм не только бесцельно расходует время процессора, но, кроме этого, он может иметь некоторые неожиданные последствия. Рассмотрим два процесса: Н, с высоким приоритетом, и L, с низким приоритетом. Правила плани­рования в этом случае таковы, что процесс Н запускается немедленно, как только он оказывается в состоянии ожидания. В какой-то момент, когда процесс L нахо­дится в критической области, процесс Н оказывается в состоянии ожидания (на­пример, он закончил операцию ввода/вывода). Процесс Н попадает в состояние активного ожидания, но поскольку процессу L при условии работающего процес­са Н процессорное время никогда не будет предоставлено, у процесса L не будет возможности выйти из критической области, и процесс Н навсегда останется в цикле. Эту ситуацию иногда называют проблемой инверсии приоритета.

Теперь рассмотрим некоторые примитивы межпроцессного взаимодействия, применяемые вместо циклов ожидания (в которых лишь напрасно расходуется процессорное время). Эти примитивы блокируют процессы в случае запрета на вход в критическую область. Одной из простейших является пара примитивов sleep и wakeup. Примитив sleep — системный запрос, в результате которого вызы­вающий процесс блокируется, пока его не запустит другой процесс. Запрос wakeup ожидает один аргумент — идентификатор запускаемого процесса. Также возможно наличие одного аргумента у обоих запросов (ожидание и запуска) – адреса ячейки памяти, предназначенной для их согласования.

Семафоры

В 1965 году Дейкстра (Е. W. Dijkstra) предложил использовать целую перемен­ную для подсчета сигналов запуска, сохраненных на будущее. Им был предло­жен новый тип переменных, так называемые семафоры, значение которых может быть нулем (в случае отсутствия сохраненных сигналов активизации) или неко­торым положительным числом, соответствующим количеству отложенных сиг­налов.

Дейкстра предложил две операции, down и up (обобщения sleep и wakeup). Операция down сравнивает значение семафора с нулем. Если значение семафора больше нуля, операция down уменьшает его (то есть расходует один из сохраненных сигналов активизации) и просто возвращает управление. Если значение семафо­ра равно нулю, процедура down не возвращает управление процессу, а процесс переводится в состояние ожидания. Все операции проверки значения семафора, его изменения и перевода процесса в состояние ожидания выполняются как еди­ное и неделимое элементарное действие. Тем самым гарантируется, что после начала операции ни один процесс не получит доступа к семафору до окончания или блокирования операции. Атомарность операции чрезвычайно важна для разрешения проблемы синхронизации и предотвращения состояния состязания.

Операция up увеличивает значение семафора. Если с этим семафором связа­ны один или несколько ожидающих процессов, которые не могут завершить бо­лее раннюю операцию down, один из них выбирается системой (например, слу­чайным образом) и ему разрешается завершить свою операцию down. Таким образом, после операции up, примененной к семафору, связанному с нескольки­ми ожидающими процессами, значение семафора так и останется равным 0, но число ожидающих процессов уменьшится на единицу. Операция увеличения значения семафора и активизации процесса тоже неделима. Ни один процесс не может быть блокирован во время выполнения операции up, как ни один процесс не мог быть блокирован во время выполнения операции wakeup в предыдущей модели.

В оригинале Дейкстра употреблял вместо down и up обозначения Р и V соот­ветственно. Мы не будем в дальнейшем использовать оригинальные обозначе­ния, поскольку тем, кто не знает голландского языка, эти обозначения ничего не говорят (да и тем, кто знает язык, говорят немного). Впервые обозначения down и up появились в языке Алгол 68.