Листинг 7. Фрагмент программы на ассемблере с критическим интервалом
L: BTC M.1
…
критическая секция
…
AND М, 0В
Несмотря на то что и блокировка памяти, и операция «проверка и установка» пригодны для реализации взаимного исключения, оба эти приема очень неэффективны. Всякий раз, когда один процесс выполняет свой критический участок, любой другой процесс, который попытается войти, попадает в цикл и должен там ожидать разрешения продолжить работу. При таком неопределенном пребывании в цикле, которое называется активным ожиданием, напрасно расходуется процессорное время. До тех пор пока процесс, занимающий в данный момент критический ресурс, не решит его уступить, все другие процессы, ожидающие этого ресурса, могли бы с тем же успехом «отправиться спать» и отдать процессоры, на которых они работают. Когда вход в критический участок снова будет свободен, можно будет «разбудить» один из «спящих» процессов, вернуть ему процессор и разрешить доступ к критическому ресурсу. Простым приемом синхронизации, позволяющим организовать для процессов ожидание, не прибегая к активному ожиданию, является «семафор».
Понятие семафорных механизмов было введено Дейкстрой в 19__. Семафор, называемый иногда также общим семафором – это целая переменная S, значение которой могут менять только операции P(S)[1] и V(S)[2].
Пусть S – семафор. Когда процесс выполняет операцию P(S), S уменьшается на единицу и
1) если S ³ 0, то процесс продолжает работу;
2) если S < 0, то процесс останавливается и встает в очередь ожидания, связанную с S; он останется заблокированным до тех пор, пока операция V(S), выполненная другим процессом, не освободит его.
Когда процесс выполняет V(S), S увеличивается на единицу и
1) если S > 0, то процесс продолжает работу;
2) если S £ 0, то один процесс удаляется из очереди ожидания и получает разрешение продолжить работу; процесс, который обратился к операции V(S), тоже может продолжать работу.
Кроме того, операции Р и V неделимы. В каждый момент только один процесс может выполнять операцию Р или V над данным семафором. Поэтому если S = l и два процесса одновременно попытаются выполнить операцию Р (S), то только одному из них будет позволено продолжать работу. Другой процесс будет заблокирован и поставлен в очередь к семафору S.
Семафор, максимальное значение которого равно единице, называется двоичным семафором. В противном случае семафоры называют N - ичными. Допустимыми значениями семафоров являются только целые числа. Есть реализации, в которых семафорные переменные не могут быть отрицательными, а есть и такие, где модуль отрицательного значения указывает на длину очереди процессов, стоящих в состоянии ожидания открытия семафора.
С помощью двоичного семафора процессы могут организовать взаимное исключение, заключив свои критические участки «в скобки», роль которых играют операции P(S) и V(S). Если имеется два процесса, использующих семафор S для синхронизации своих критических участков, то, по определению семафора, S принимает значения 1, 0 или -1. Если S = l, это значит, что ни один процесс не находится в своем критическом участке. Если S = 0, это значит, что один процесс находится в своем критическом участке. Если S = -1, это значит, что один процесс находится в своем критическом участке и один процесс – в очереди к семафору S, где он ждет разрешения войти в свой критический участок. Это простое решение, использующее двоичные семафоры, применимо точно так же и в случае большого числа процессов.
Основным достоинством использования семафорных операций является отсутствие состояния «активного ожидания», что может существенно повысить эффективность работы мультипрограммной вычислительной системы.
В настоящее время на практике используется много различных видов семафорных механизмов. Варьируемыми параметрами, которые отличают различные виды примитивов, являются начальное значение и диапазон изменения значений семафора, логика действий семафорных операций, количество семафоров, доступных для обработки при исполнении отдельного примитива.
Операции Р и V выполняются операционной системой в ответ на запрос, выданный некоторым процессом и содержащий имя семафора в качестве параметра. Для работы с семафорными переменными необходимо еще иметь операцию инициализации самого семафора, то есть операцию задания ему начального значения. Обычно эту операцию называют InitSem. Она имеет два параметра – имя семафорной переменной и ее начальное значение; т.е. обращение к ней имеет вид: InitSem (Имя_Семафора, Начальное_значение_семафора).
В Листинге 6.1 на примере двух конкурирующих процессов ПР1 и ПР2 представлен вариант решения проблемы взаимного исключения доступа к критическому ресурсу с помощью семафорных примитивов P(S) и V(S), которые задаются в виде:
P(S):
S:=S - 1;
if S < 0 then {остановить процесс и поместить его в очередь ожидания к семафору S}
V(s):
If S < 0 then {поместить один из ожидающих процессов очереди семафора S в очередь готовности};
