Файл: А. В. Гордеев А. Ю. Молчанов системное программное обеспечение электронный вариант книги издательства Питер СанктПетербург Челябинск юургу каф. Автоматика и управление 2002 2 Предисловие Настоящий учебник.pdf

313
while true do ЧИТАТЕЛЬ
and while true do ПИСАТЕЛЬ
and while true do ПИСАТЕЛЬ
and while true do ПИСАТЕЛЬ
parend end.
При решении данной задачи используются два семафора R и W и переменная
NR, предназначенная для подсчёта текущего числа процессов типа «читатели», на- ходящихся в критическом интервале. Доступ к разделяемой области памяти осуще- ствляется через семафор W. Семафор R используется для взаимоисключения про- цессов типа «читатели».
Если критический ресурс не используется, то первый появившийся процесс при входе в критический интервал выполнит операцию P(W) и закроет семафор.
Если процесс является «читателем», то переменная NR будет увеличена на едини- цу и последующие «читатели» будут обращаться к ресурсу, не проверяя значение семафора W, что обеспечивает параллельность их доступа к памяти. Последний
«читатель», покидающий критический интервал, является единственным, кто вы- полнит операцию V(W) и откроет семафор W. Семафор R предохраняет от некор- ректного изменения значения NR, а также от выполнения «читателями» операций
P(W) и V(W). Если в критическом интервале находится «писатель», то на семафоре
W может быть заблокирован только один «читатель», все остальные будут блоки- роваться на семафоре R. Другие «писатели» блокируются на семафоре W.
Когда «писатель» выполняет операцию V(W), неясно, какого типа процесс войдёт в критический интервал. Чтобы гарантировать получение процессами «чи- тателями» наиболее свежей информации, необходимо при постановке в очередь го- товности использовать дисциплину обслуживания, учитывающую более высокий приоритет «писателей». Однако этого оказывается недостаточно, ибо если в крити-

314
ческом интервале продолжает находиться, по крайней мере, один «читатель», то он не даст обновить данные, но и не воспрепятствует вновь приходящим процессам
«читателям» войти в свою критическую секцию. Необходим дополнительный се- мафор. Пример правильного решения этой задачи приведен в листинге 6.14.
0>0>0>

315
while true do ЧИТАТЕЛЬ
and while true do ПИСАТЕЛЬ
and while true do ПИСАТЕЛЬ
and while true do ПИСАТЕЛЬ
parend end.
Как можно заметить, семафор S блокирует приход новых «читателей», если появился хотя бы один процесс «писатель». Обратите внимание, что в процедуре
«читатель» использование семафора S имеет место только при входе в критиче- ский интервал. После выполнения чтения уже категорически нельзя использовать этот семафор, ибо он тут же заблокирует первого же «читателя», если хотя бы один
«писатель» захотел войти в свою критическую секцию. И получится так называе- мая тупиковая ситуация, ибо «писатель» не сможет войти в критическую секцию,
поскольку в ней уже находится процесс «читатель». А «читатель» не сможет поки- нуть критическую секцию, потому что процесс «писатель» желает войти в свой критический интервал.
Обычно программы, решающие проблему «читатели – писатели», используют как семафоры, так и мониторные схемы с взаимным исключением, то есть такие,
которые блокируют доступ к критическим ресурсам для всех остальных процессов,
если один из них модифицирует значения общих переменных. Взаимное исключе- ние требует, чтобы «писатель» ждал завершения всех текущих операций чтения.
При условии, что «писатель» имеет более высокий приоритет, чем «читатель», та- кое ожидание в ряде случаев весьма нежелательно. Кроме того, реализация прин- ципа исключения в многопроцессорных системах может вызвать определённую избыточность. Поэтому ниже приводится схема, применяемая иногда для решения задачи «читатели – писатели», которая в случае одного «писателя» допускает од- новременное выполнение операций чтения и записи (листинг 6.15). После чтения

316
данных процесс «читатель» проверяет, мог ли он получить неправильное значение,
некорректные данные (вследствие того, что параллельно с ним процесс «писатель»
мог их изменить), и если обнаруживает, что это именно так, то операция, чтения повторяется.
Листинг 6,15. Синхронизация процессов «читатели» и «писатель» без взаим- ного исключения
Var VI, V2 : integer;
Procedure ПИСАТЕЛЬ;
begin
Inc(V1);
Write_Data;
V2:=V1
end;
Procedure ЧИТАТЕЛЬ;
Var V: integer begin repeat V:= V2;
Read_Data until V1 = V
end;
begin
V1:= 0;
V2:= 0;
parbegin while true do ЧИТАТЕЛЬ
and while true do ЧИТАТЕЛЬ
and while true do ЧИТАТЕЛЬ
and while true do ПИСАТЕЛЬ
parend

317
end.
Этот алгоритм использует для данных два номера версий, которым соответст- вуют переменные V1 и V2. Перед записью порции новых данных процесс «писа- тель» увеличивает на 1 значение переменной V1, а после записи – переменную V2.
«Читатель» обращается к V2 перед чтением данных, а к V1 – после. Если при этом
V1 и V2 равны, то, очевидно, что получена правильная версия данных. Если же данные обновлялись за время чтения, то операция повторяется. Данный алгоритм может быть использован в случае, если нежелательно заставлять процесс «писа- тель» ждать, пока «читатели» закончат операцию чтения, или если вероятность по- вторения операции чтения достаточно мала и обусловленное повторными опера- циями снижение эффективности системы меньше потерь, связанных с избыточно- стью решения при использовании взаимного исключения. Однако необходимо иметь в виду ненулевую вероятность зацикливания чтения при высокой интенсив- ности операций записи. Наконец, если само чтение представляет собой достаточно длительную операцию, то оператор V1:=V2 для процесса «читатель» может быть заменён на оператор repeat V:= V2 until V1 = V
Это предотвратит выполнение «читателем» операции чтение, если «писатель»
уже начал запись.
Мониторы Хоара
Анализ рассмотренных задач показывает, что, несмотря на очевидные досто- инства (простота, независимость от количества процессов, отсутствие «активного ожидания»), семафорные механизмы имеют и ряд недостатков. Семафорные меха- низмы являются слишком примитивными, так как семафор не указывает непосред- ственно на синхронизирующее условие, с которым он связан, или на критический ресурс. Поэтому при построении сложных схем синхронизации алгоритмы реше- ния задач порой получаются весьма непростыми, ненаглядными и затруднитель- ными для доказательства их правильности.
Необходимо иметь понятные, очевидные решения, которые позволят приклад- ным программистам без лишних усилий, связанных с доказательством правиль- ности алгоритмов и отслеживанием большого числа взаимосвязанных объектов,

318
создавать параллельные взаимодействующие программы. К таким решениям мож- но отнести так называемые мониторы, предложенные Хоаром [31].
В параллельном программировании монитор – это пассивный набор разде- ляемых переменных и повторно входимых процедур доступа к ним, которым про- цессы пользуются в режиме разделения, причём в каждый момент им может поль- зоваться только один процесс.
Рассмотрим, например, некоторый ресурс, который разделяется между про- цессами каким-либо планировщиком [37]. Каждый раз, когда процесс желает полу- чить в своё распоряжение какие-то ресурсы, он должен обратиться к программе–
планировщику. Этот планировщик должен иметь переменные, с помощью которых он отслеживает, занят ресурс или свободен. Процедуру планировщика разделяют все процессы, и каждый процесс может в любой момент захотеть обратиться к пла- нировщику. Но планировщик не в состоянии обслуживать более одного процесса одновременно. Такая процедура-планировщик и представляет собой пример мони- тора.
Таким образом, монитор – это механизм организации параллелизма, который содержит как данные, так и процедуры, необходимые для реализации динамиче- ского распределения конкретного общего ресурса или группы общих ресурсов.
Процесс, желающий получить доступ к разделяемым переменным, должен обра- титься к монитору, который либо предоставит доступ, либо откажет в нём. Необ- ходимость входа в монитор с обращением к какой-либо его процедуре (например, с запросом на выделение требуемого ресурса) может возникать у многих процессов.
Однако вход в монитор находится под жёстким контролем – здесь осуществляется взаимоисключение процессов, так что в каждый момент времени только одному процессу разрешается войти в монитор. Процессам, которые хотят войти в мони- тор, когда он уже занят, приходится ждать, причем режимом ожидания автомати- чески управляет сам монитор. При отказе в доступе монитор блокирует обратив- шийся к нему процесс и определяет условие, по которому процесс ждёт. Проверка условия выполняется самим монитором, который и деблокирует ожидающий про- цесс. Поскольку механизм монитора гарантирует взаимоисключение процессов,

319
отсутствуют серьёзные проблемы, связанные с организацией параллельных взаи- модействующих процессов. Внутренние данные монитора могут быть либо гло- бальными (относящимися ко всем процедурам монитора), либо локальными (отно- сящимися только к одной конкретной процедуре). Ко всем этим данным можно об- ращаться только изнутри монитора; процессы, находящиеся вне монитора и, по существу, только вызывающие его процедуры, просто не могут получить доступ к данным монитора. При первом обращении монитор присваивает своим перемен- ным начальные значения. При каждом последующем обращении используются те значения переменных, которые сохранились от предыдущего обращения.
Если процесс обращается к некоторой процедуре монитора и обнаруживается,
что соответствующий ресурс уже занят, эта процедура монитора выдает команду ожидания WAIT с указанием условия ожидания. Процесс мог бы оставаться внутри монитора, однако это противоречит принципу взаимоисключения, если в монитор затем вошёл бы другой процесс. Поэтому процесс, переводящийся в режим ожида- ния, должен вне монитора ждать того момента, когда необходимый ему ресурс ос- вободится.
Со временем процесс, который занимал данный ресурс, обратится к монитору,
чтобы возвратить ресурс системе. Соответствующая процедура монитора при этом может просто принять уведомление о возвращении ресурса, а затем ждать, пока не поступит запрос от другого процесса, которому потребуется этот ресурс. Однако может оказаться, что уже имеются процессы, ожидающие освобождения данного ресурса. В этом случае монитор выполняет команду извещения (сигнализации)
SIGNAL, чтобы один из ожидающих процессов мог получить данный ресурс и по- кинуть монитор. Если процесс сигнализирует о возвращении (иногда называемом освобождением) ресурса и в это время нет процессов, ожидающих данного ресурса,
то подобное оповещение не вызывает никаких других последствий кроме того, что монитор, естественно, вновь вносит ресурс в список свободных. Очевидно, что процесс, ожидающий освобождения некоторого ресурса, должен находиться вне монитора, чтобы другой процесс имел возможность войти в монитор и возвратить ему этот ресурс.

320
Чтобы гарантировать, что процесс, находящийся в ожидании некоторого ре- сурса, со временем получит этот ресурс, делается так, что ожидающий процесс имеет более высокий приоритет, чем новый процесс, пытающийся войти в мони- тор. В противном случае новый процесс мог бы перехватить ожидаемый ресурс до того, как ожидающий процесс вновь войдет в монитор. Если допустить многократ- ное повторение подобной нежелательной ситуации, то ожидающий процесс мог бы откладываться бесконечно. Однако для систем реального времени можно допус- тить использование дисциплины обслуживания на основе абсолютных или дина- мически изменяемых приоритетов.
В листинге 6.16 в качестве примера приведён простейший монитор для выде- ления одного ресурса.
Листинг 6.16. Пример монитора Хоара monitor Resourse;
condition free; { условие - свободный }
var busy : boolean; { busy - занят }
procedure REQUEST; {запрос}
begin if busy then WAIT ( free);
busy:=rtrue;
TakeOff; { ВЫДАТЬ РЕСУРС }
end;
procedure RELEASE;
begin
TakeOn; { ВЗЯТЬ РЕСУРС }
busy:=false;
SIGNAL ( free )
end;
begin busy:=false;
end.
Единственный ресурс динамически запрашивается и освобождается процесса- ми, которые обращаются к процедурам REQUEST (запрос) и RELEASE (осво-

321
бодить). Если процесс обращается к процедуре REQUEST в тот момент, когда ре- сурс используется, значение переменной busy (занято) будет равно true, и проце- дура REQUEST выполнит операцию монитора WAIT(free). Эта операция блокиру- ет не процедуру REQUEST, а обратившийся к ней процесс. Процесс помещается в конец очереди процессов, ожидающих, пока не будет выполнено условие free
(свободный).
Когда процесс, использующий ресурс, обращается к процедуре RELEASE,
операция монитора SIGNAL деблокирует процесс, находящийся в начале очереди,
не позволяя исполняться никакой другой процедуре внутри того же монитора. Этот деблокированный процесс готов возобновить исполнение процедуры REQUEST
сразу же после операции WAIT(free), которая его и блокировала. Если операция
SIGNAL(free) выполняется в то время, когда нет процесса, ожидающего условия free, то никакие действия не выполняются.
Использование монитора в качестве основного средства синхронизации и свя- зи освобождает процессы от необходимости явно разделять между собой информа- цию. Напротив, доступ к разделяемым переменным всегда ограничен телом мони- тора, и поскольку мониторы входят в состав ядра операционной системы, то разде- ляемые переменные становятся системными переменными. Это автоматически ис- ключает критические интервалы (так как в каждый момент монитором может поль- зоваться только один процесс, то два процесса никогда не могут получить доступ к разделяемым переменным одновременно).
Монитор является пассивным объектом в том смысле, что это не процесс; его процедуры выполняются только по требованию процесса.
Хотя по сравнению с семафорами мониторы не представляют собой сущест- венно более мощного инструмента для организации параллельных взаимодейст- вующих вычислительных процессов, у них есть некоторые преимущества перед более примитивными синхронизирующими средствами. Во-первых, мониторы очень гибки. В форме мониторов можно реализовать не только семафоры, но и многие другие синхронизирующие операции. Например, разобранный во втором разделе данной главы механизм решения задачи «поставщик – потребитель» легко

322
запрограммировать в виде монитора. Во-вторых, локализация всех разделяемых переменных внутри тела монитора позволяет избавиться от малопонятных конст- рукций в синхронизируемых процессах. Сложные взаимодействия процессов мож- но синхронизировать наглядным образом. В-третьих, мониторы дают процессам возможность совместно использовать программные модули, представляющие со- бой критические секции. Если несколько процессов совместно используют ресурс и работают с ним совершенно одинаково, то в мониторе нужна только одна проце- дура, тогда как решение с семафорами требует, чтобы в каждом процессе имелся собственный экземпляр критической секции. Таким образом, мониторы обеспечи- вают по сравнению с семафорами значительное упрощение организации взаимо- действующих вычислительных процессов и большую наглядность при лишь незна- чительной потере в эффективности.
Почтовые ящики
Тесное взаимодействие между процессами предполагает не только синхрони- зацию – обмен временными сигналами, но и передачу, и получение произвольных данных – обмен сообщениями. В системе с одним процессором посылающий и по- лучающий процессы не могут работать одновременно. В мультипроцессорных сис- темах также нет никакой гарантии их одновременного исполнения. Следовательно,
для хранения посланного, но ещё не полученного сообщения необходимо место.
Оно называется буфером сообщений или почтовым ящиком
1
.
Если процесс Р1 хочет общаться с процессом Р2, то Р1 просит систему обра- зовать или предоставить ему почтовый ящик, который свяжет эти два процесса так,
чтобы они могли передавать друг другу сообщения. Для того чтобы послать про- цессу Р2 какое-то сообщение, процесс Р1 просто помещает это сообщение в поч- товый ящик, откуда процесс Р2 может его в любое время взять. При применении почтового ящика процесс Р2 в конце концов обязательно получит сообщение, ко- гда обратится за ним, если вообще обратится. Естественно, что процесс Р2 должен знать о существовании почтового ящика. Поскольку в системе может быть много почтовых ящиков, необходимо обеспечить доступ процессу к конкретному почто-
1
Название «почтовый ящик» происходит от обычного приспособления для отправки почты.