Современные операционные системы

Современные операционные системы
Процессы и потоки / Семафоры

Семафоры




Ситуация изменилась в 1965 году, когда Дейкстра предложил использовать целочисленную переменную для подсчета количества активизаций, отложенных на будущее. Он предложил учредить новый тип переменной — семафор (semaphore). Значение семафора может быть равно 0, что будет свидетельствовать об отсутствии сохраненных активизаций или иметь какое-нибудь положительное значение, если ожидается не менее одной активизации.

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

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

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

Между прочим, в первоначальном варианте своей работы Дейкстра вместо down и up использовал имена Р и V соответственно. Но в них не было никакого мнемонического смысла для тех, кто не говорит по-голландски, да и для тех, кто говорит, смысл был едва уловим — Proberen (пытаться) и Verhogen (поднимать выше), поэтому вместо этих терминов мы будет употреблять down и up. Впервые они были представлены в языке программирования Algol 68.



Полное описание: Семафоры




С этим описанием рассматриваются следующие темы:


Решение задачи производителя-потребителя с помощью семафоров
В листинге 2.6 показано, как с помощью семафоров решается проблема утраченных активизаций. Чтобы заставить их корректно работать, очень важно, чтобы их реализация предусматривала неделимый режим работы. Вполне естественно было бы реализовать операции up и down в виде системных вызовов, чтобы операционная система на время тестирования семафора, обновления его значения и приостановки процесса при необходимости кратковременно запрещала все прерывания. Поскольку все эти действия занимают только неск ... Читать

Семафоры full и empty
Теперь, когда в нашем распоряжении имеется хороший примитив взаимодействия процессов, давайте вернемся назад и заново рассмотрим последовательность прерываний, показанную в табл. 2.2. В системе, использующей семафоры, естественным способом скрыть прерывания станет использование семафора с исходным нулевым значением, связанным с каждым устройством ввода-вывода. Сразу же после запуска устройства ввода-вывода управляющий процесс выполняет операцию down в отношении связанного с этим устройством сема ... Читать

Блокирующие переменные
В качестве второй попытки рассмотрим программное решение, в котором используется одна общая (блокирующая) переменная, исходное значение которой равно нулю. Когда процессу требуется войти в свою критическую область, сначала он проверяет значение блокирующей переменной. Если оно равно 0, процесс устанавливает его в 1 и входит в критическую область. Если значение уже равно 1, процесс просто ждет, пока оно не станет равно нулю. Таким образом, нулевое значение означает, что ни один из процессов не на ... Читать

Задача производителя и потребителя
В качестве примера применения этих примитивов рассмотрим задачу производителя и потребителя (также известную как задача ограниченного буфера). Два процесса используют общий буфер фиксированного размера. Один из них, производитель, помещает информацию в буфер, а другой, потребитель, извлекает ее оттуда. (Можно также расширить проблему до т производителей и п потребителей, но мы будем рассматривать только случай с одним производителем и одним потребителем, поскольку такое допущение упрощает решени ... Читать

Автоматическая организация взаимного исключения
Может создаться впечатление, что операции так и signal похожи на операции sleep и makeup, которые, как мы видели ранее, приводят к фатальному состоянию состязательности. Конечно же, они очень похожи, но с одной весьма существенной разницей: sleep и makeup терпели неудачу, когда один процесс пытался заблоки-роваться, а другой пытался его активизировать. При использовании мониторов такая ситуация исключена. Автоматическая организация взаимного исключения в отношении процедур монитора гарантирует с ... Читать