P(S);
CSi;
V(S);
Остальное_I; end loop;
Parbegin R1; . . . Rn; Parend.
Действительно, если несколько задач пытаются одновременно выполнить действие P(S), то сделать это не удастся, так как по определению операции P(S) и V(S) являются неделимыми. Другими словами, семафор «захватит» только одна задача, которая установит его значение в «0». Все последующие вызовы P(S) приведут к блокировке вызвавших их задач, и, следовательно, доступ к ресурсу получит только одна из них. Таким образом, взаимное исключение обеспечено. По окончании работы CS задача, захватившая семафор, выполнит действие V(S) и «освободит» из очереди первую заблокированную. Так как очередь заблокированных задач обслуживается в соответствии с дисциплиной FIFO и все задачи имеют конечное время выполнения критической секции, то ни одна из них не будет ждать бесконечно долго.
Развитием двоичного семафора является счетный семафор. Семафор S
может принимать целые значения из диапазона 0...n. Соответствующие P- и V-операции определяются так:
S : СчетныйСемафор(m,n); P(S):
if (S = 0) then wait(S > 0); S := S - 1;
V(S):
if (S < n) then S := S + 1;
При описании счетного семафора следует указывать его начальное m и максимальное n значения (n ≥ m ≥ 0). Если S > 0, то каждый вызов P(S) уменьшает значение S на единицу, при этом вызвавшая P(S) задача продолжает работать. При S = 0 все последующие вызовы P(S) будут блокировать вызывающую задачу и ставить ее в очередь.
При S > 0 операция V(S) просто увеличивает значение семафора, не допуская при этом превышения максимального значения. Очевидно, что в этом случае очередь заблокированных задач будет пуста. Действия операции V(S) при S = 0 должны сопровождаться анализом очереди задач,
6
заблокированных на семафоре, и если она не пуста, то инкремент семафора должен вызывать активизацию первой из них.
Для иллюстрации механизма семафоров рассмотрим хорошо известный пример, который часто называют «Поставщик – Потребитель».
Пусть имеются две задачи, одна из которых, «Поставщик», в какие-то моменты времени записывает в некий буфер порции информации, а вторая – «Потребитель» – выбирает эти порции информации из данного буфера. При этом на реализацию «Поставщика» и «Потребителя» накладываются следующие условия:
1.«Поставщик» не может записывать информацию и блокируется, если буфер полон.
2.«Потребитель», пытаясь читать информацию, блокируется, если буфер пуст.
3.Не допускается одновременная запись и чтение информации.
Одно из решений данного примера строится на использовании трех семафоров – одного двоичного и двух счетных:
Доступ : ДвоичныйСемафор; Не_пуст : СчетныйСемафор(n,n); Не_полон : СчетныйСемафор(0, n); Поставщик:
loop
Производство_Информации;
P(Не_полон); |
// (*) |
P(Доступ); |
// (**) |
Запись_в_буфер; |
|
V(Доступ); |
|
V(Не_пуст); Остальное_Поставщика;
end loop;
Потребитель: loop
P(Не_пуст);
P(Доступ); Запись_в_буфер; V(Доступ); V(Не_полон);
7
Остальное_Потребителя; end loop;
Parbegin Поставщик; Потребитель; Parend.
Обратим внимание на то, что если поменять местами две строки – (*) и (**) – в тексте «Поставщика», то может произойти взаимная блокировка задач. Предположим, что в какой-то момент времени буфер полон и «Поставщик» «захватил» семафор Доступ. В этом случае «Потребитель» не сможет выполнить чтение из буфера и возникнет тупиковая ситуация. Такой пример показывает, что механизм семафоров является весьма низкоуровневым, т. е. допускающим значительные «вольности» при его использовании, которые могут приводить к ошибочным ситуациям. Случайная замена местами строк при написании текста программы является вполне возможной оплошностью. Этот пример показывает, что семафоры, хотя и представляют собой достаточно общий механизм синхронизации, являются средствами относительно низкого уровня.
Менее очевидным, но не менее опасным источником неприятностей в рассмотренном примере является возможность освобождения счетного семафора (вызов V(Не_пуст)) той задачей, которая его не «захватывала» (не выполняла P(Не_пуст)). Таким образом, при использовании механизма семафоров следует придерживаться определенных рекомендаций структурирования кода, стараться, например, чтобы освобождение семафора (V-операция) выполнялось той же задачей, что и его захват (P-операция).
Очевидно, что при «аккуратном» использовании счетного семафора и строгом слежении за последовательностью выполнения P- и V-операций можно обходиться без двоичного семафора. При необходимости надо просто определять счетный семафор с начальным значением «0» или «1» и максимальным «1». Другими словами, двоичный семафор можно считать частным случаем счетного семафора.
Следует отметить, что в современных многозадачных операционных системах реализуется только счетный семафор, при этом допускается, что его значение может стать отрицательным.
Функции двоичного семафора реализуются в другом синхронизирующем механизме – мьютексе (mutex). Мьютекс определяется как объект, способный находиться в одном из двух состояний, – занят или свободен и над которым возможны две операции lock и unlock:
M : mutex;
8
lock:
if (M = занят) then wait(M = свободен); M := занят;
Owner := текущая_задача; unlock:
M := свободен;
Owner := NULL;
На первый взгляд представляется, что мьютекс является аналогом двоичного семафора, lock и unlock являются неделимыми и функционально подобны P- и V-операциям. Отличительной особенностью является наличие у мьютекса атрибута владелец – Owner. «Владельцем» становится текущая задача, в коде которой выполнен lock над «свободным» мьютексом, и в этом случае говорят, что задача захватила этот мьютекс. Любая другая задача, пытающаяся захватить этот объект, будет заблокирована и поставлена в очередь. Выполнить действие unloсk и освободить мьютекс может только его владелец, попытка выполнить unlock другой задачей приведет к ошибке. Атрибут Owner не требует от пользователя его инициализации, в исходном состоянии его значение NULL, а далее устанавливается и «сбрасывается» автоматически при захвате и освобождении мьютекса; другими словами, программист может и не замечать его существования. При этом наличие такого атрибута позволяет решать сложные проблемы, связанные с многозадачностью, как, например, проблему инверсии приоритетов, рассмотрение которой выходит за рамки представленного материала. Таким образом, считать мьютекс аналогом двоичного семафора было бы неправильно.
3. МОНИТОР ХОАРА
Семафоры и мьютексы, предоставляя большую свободу в их использовании, часто провоцируют на построение сложных последовательностей захвата и освобождения, что при неаккуратном написании кода зачастую приводит к довольно запутанным программным конструкциям и подчас неразрешимым проблемам при отладке даже не слишком сложных задач. В 1974 г. английский профессор Чарльз Энтони Хоар опубликовал статью, в которой изложил идею монитора – конструкции, позволяющей инкапсулировать процедуры и данные, обеспечивая к ним взаимно исключающий доступ задач:
9
monitor имя_монитора;
декларация данных, локальных для монитора; procedure имя_процедуры (формальные параметры); begin тело процедуры end;
Декларация других процедур; begin
Инициализация локальных данных;
еnd.
Предлагаемая конструкция представляет собой специфический модуль, в котором собраны данные и процедуры, одновременный доступ к которым возможен только из одной задачи. При создании монитора с ним связывается очередь доступа, в которую помещаются заблокированные задачи, пытающиеся использовать его ресурсы, если они уже используются другой задачей. Таким образом, обеспечивается взаимное исключение доступа.
В качестве примера обратимся снова к задаче «Поставщик – Потребитель».
monitor Буфер;
СамБуфер array[1..ДлинаБуфера] : Данное; СчетчикЗаписей : integer;
procedure Записать(d : Данное); begin
...
end;
function Прочитать : Данное; begin
...
end; begin
СчетчикЗаписей := 0; End Буфер;
Поставщик: loop
D := Производство;
Буфер.Записать(D); end loop;
Потребитель:
10