Аппаратная реализация взаимного исключения

Begin

begin

Repeat

P(S) ;

< критический интервал >;

V(S) ;

< остальная часть программы >

untilfalse

end;

Procedure Process P2;

begin

Repeat

P(S) ;

< критический интервал >;

V(S) ;

< остальная часть программы >

untilfalse

end;

Begin

Begin

Repeat

< предшествующие операторы >;

P(S) ;

< остальная часть программы >

untilfalse

end;

Pгосеdure Process_P2 ;

Begin

Repeat

< предшествующие операторы >;

V(S) ;

< остальная часть программы >

untilfalse

end;

Begin

S := 0 ;

Process_P1 ;

Process_P2

End .

Рис. 4.16. Синхронизация процессов при помощи семафоров

Здесь процесс P1 выполняет некоторые предшествующие операции, а затем операцию Р(S). Ранее при инициализации семафор был установлен в нуль, так что процесс P1 будет ждать. Со временем процесс P2 выполнит операцию V(S), сигнализируя о том, что данное событие произошло. Тем самым процесс P1 получает возможность продолжить свое выполнение. Отметим, что подобный механизм будет выполнять свои ф­ункции даже в том случае, если процесс P2 обнаружит наступление события и просигнализирует об этом еще до того, как процесс P1 выполнит операцию Р(S); при этом семафор переключится из 0 в 1, так что операция Р(S) просто произведет обратное переключение, из 1 в 0, и процесс P1 продолжит свое выпо­лнение без ожидания.

Мониторы

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

- они настолько элементарны, что не позволяют достаточно легко описывать решение сравнительно серьезных проблем параллельных вычислений;

- неправильное их использование, либо умышленное, либо непреднамеренное, может привести к нарушению работоспособности системы параллельной обработки.

Поэтому необходимо было разработать конструкции более высокого уровня, которые устраняли бы указанные недостатки.

Одной из таких конструкций является монитор, первый вариант которого предложил Дейкстра.

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

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

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

Со временем процесс, который занимал данный ресурс, обратится к монитору, чтобы возвратить ресурс системе. Соответствующая процедура монитора при этом может просто принять уведомление о возвращении ресурса, а затем ждать, пока не поступит запрос от другого процесса, которому потребуется этот ресурс. Однако может оказаться, что уже имеются процессы, ожидающие освобождения данного ресурса. В этом случае монитор выполняет команду оповещения (сигнализации) Signal­, чтобы один из ожидающих процессов мог занять данный ресурс и покинуть монитор. Если процесс сигнализирует о возвращении (­иногда называемом освобождением) ресурса и в это время нет процессов, ожидающих данного ресурса, то подобное оповещение не вызывает никаких других последствий, кроме того, что монитор естественно вновь вносит ресурс в список свободных. Очевидно, что процесс, ожидающий освобождения некоторого ресурса, должен находиться вне монитора, чтобы другой процесс имел возможность войти в монитор и возвратить ему этот ресурс.

Чтобы гарантировать, что процесс, находящийся в ожидании некоторого ресурса, со временем действительно получит этот ресурс, считается, что ожидающий процесс имеет более высокий приоритет, чем новый процесс, пытающийся войти в монитор. В противном случае новый процесс мог бы перехватить ожидаемый ресурс до того, как ожидающий процесс вновь войдет в монитор. Если допустить многократное повторение подобной нежелательной ситуации, то ожидающий процесс мог бы откладываться бесконечно.

Фактически у процессов может возникнуть желание (и необходимость) находиться в режиме ожидания вне монитора по многим различным причинам. Поэтому было введено понятие переменной-условия. Для каждой отдельно взятой причины, по которой процесс может быть переведен в состояние ожидания, назначается свое условие. В связи с этим команды ожидания и сигнализации модифицируются - в них включаются имена условий:

Wait (имя условия)

Signal (имя условия)

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

Пусть нескольким процессам необходим доступ к определенному ресурсу, который может быть использован в каждый конкретный момент времени только одним процессом. На рис.4.17 приведен пример использования монитора для выделения и освобождения подобного ресурса.

Program Monitor ;

Vаг Res_eng : boolean ; {ресурс занят}

Res_free : condition ; {переменная-условие}

Pгосеdure Lockout ; {захват ресурса}

Begin

if Res_eng then

Wait(Res_free);

Res_eng := true

end ;

Pгосеdure Deallocate ; {освобождение ресура}

Begin

Res_eng := false ;

Signal(Res_free)

end ;

Begin

Res_eng := false

End .

Рис. 4.17. Распределение ресурса при помощи монитора

Передача сообщений

Взаимодействие между процессами при реализации взаимного исключения и семафоров осуществляется посредством обмена временными сигналами. Более тесное взаимодействие требует специальных средств связи, которые обеспечивают передачу и получение произвольных данных. Примерами последних служат данные, предназначенные для вывода на устройства построчной печати, запросы состояний (особенно устройств ввода-вывода) и даже почта от одного интерактивного пользователя к другому. В контексте связи между процессами все это называется сообщениями. В системе с одним процессором посылающий и пол­учающий процессы не могут работать одновременно. В мультипроцессорных системах также нет никакой гарантии их одновременного исполнения. Следовательно, для хранения посланного, но еще не полученного сообщения необходимо место. Формально оно называется буфером сообщений, неформально - почтовым ящиком. Если объем передаваемых д­анных велик, то эффективнее не передавать их непосредственно, а отправлять в почтовый ящик сообщение, информирующее процесс-получатель о том, где можно их найти.

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

Реализация почтовых ящиков требует использования пр­имитивных операторов низкого уровня, таких как Р и V, но пользователям можно дать средства более высокого уровня. Для организации связи между процессами используется множество 8-словных буферов для сообщений, очередь сообщений для каждого процесса, управляемая по дисциплине FIFO (первый пришел - первый обслужен), и следующие четыре операции, которые выполняются в непрерывном режиме:

1. Послать сообщение (получатель, сообщение, буфер)

2. Ждать сообщение (отправитель, сообщение, буфер)

3. Послать ответ (результат, ответ, буфер)

4. Ждать ответ (результат, ответ, буфер).

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

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

Послать ответ записывает ответ в тот буфер, из которого было получено сообщение, и добавляет буфер к очереди отправителя. Если отправитель ждет ответ, то он деблокируется.

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

Описанные операции требуют, чтобы процесс обслуживал свою очередь в порядке FIFO и блокировал себя, пока другие процессы обрабатывают его запросы. Чтобы снять эти ограничения, вводятся следующие две операции:

5. Ждать событие (последний буфер, следующий буфер, результат)

6. Получить событие (буфер)

Ждать событие блокирует обратившийся процесс, пока событие (сообщение или ответ) не поступит в очередь за переменной последний буфер. После установки процесса на процессор адрес буфера, в который оно поступило, записывается в переменную следующий буфер, а результат сообщает, является событие сообщением или ответом.

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

Основные достоинства использования буферов сообщений состоят в следующем:

1. Процессу не нужно знать о существовании других процессов до тех пор, пока он не получит сообщения от них.

2. Два процесса могут обмениваться более чем одн­им сообщением за один раз.

3. Операционная система может гарантировать, что никакой процесс не вмешается в беседу других процессов.

4. Очереди буферов позволяют процессу-отправителю продолжать работу, не обращая внимания на получателя.

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

Тупиковые ситуации

При параллельном исполнении процессов могут возникать такие ситуации, при которых два или более процесса все время находятся в заблокированном состоянии. Самым простым является случай, когда каждый из двух процессов ждет ресурс, занятый другим процессом. Из-за этого ожидания ни один из процессов не может продолжить исполнение и освободить ресурс, необходимый другому. Эта тупиковая ситуация, образно называемая "смертельное объятие", больше известна как дедлок (deadlock). Хотя дедлок может быть результатом ошибок программирования, чаще всего он возникает не из-за них.

Не нашли, что искали? Воспользуйтесь поиском по сайту: