Похожая ситуация возникает, когда один или несколько процессов продолжаюх полняться фактически на одном месте. Это называется зависанием (starvation) ц пример, если процесс непрерывно проверяет значение условной переменной, кот не изменяется, поскольку все остальные процессы также заняты проверкой. Инь словами, процессы, оказавшиеся в тупике, находятся в очереди ожидания (те блокированы), а зависшие процессы исполняются, но фактически на одном месте

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

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

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

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

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

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

1. Взаимное исключение. Существуют системные ресурсы, к которым разрешен монопольный доступ.

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

3. Последовательный захват ресурсов. Процесс запрашивает ресурсы по одномУ т. е. по мере необходимости.

4. Захват ресурсов в обратном порядке.

Эти четыре утверждения косвенно дают ключ к предотвращению тупиковых си туаций. Достаточно, чтобы одно из них не выполнялось, и тупик не возникнет.

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

Второе утверждение требует, чтобы операционная система распознавала тупиковые ситуации и реагировала соответственно, вынуждая процесс освободить ресурс. 30 решение приемлемо лишь в случае, если допускается принудительное уничтожение процесса, и зависит от механизма восстановления.

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

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

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

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

10-4. Синхронизация процессов - семафоры и события 10-4.1. Семафоры

Организация некоторого порядка исполнения процессов называется синхрониза-иеи (synchronization). Синхронизация процессов является основной функцией мно-задачных операционных систем и используется для защиты ресурсов - с помощью ханизма синхронизации упорядочивается доступ к ресурсу. То есть процесс может олучить доступ к ресурсу только после того, как другой процесс освободил его. Как по показано выше, введение дополнительных переменных для защиты ресурсов не Лучший выход, поскольку эти переменные сами становятся общим ресурсом. Суще-тво проблемы состоит в том, что операции проверки и изменения значения перемен-ой защиты разделены во времени и могут быть прерваны в любой момент. Более

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

Семафоры (semaphore) - это основной метод синхронизации, свободный от уа занных недостатков. Он, в сущности, является наиболее общим методом синхронизации процессов.

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

Очень важно, что проверка и уменьшение значения семафора в операции wait выполняются за один шаг. Операционная система не может прервать выполнение операции wait между проверкой и уменьшением значения. Операция wait для семафора имеет такое же функциональное значение, что и инструкция test and set.

Если несколько процессов ждут одного и того же семафора, то после выполнения операции signal только один из них может продолжить свое развитие. В зависимости от реализации процессы могут ждать в очереди, упорядоченной либо по принципу FIEO (Firstln, FirstOut ~ первым вошел, первым вышел), либо в соответствии с приоритетами, или выбираться случайным образом.

Названия управляющей структуры "семафор" и операций signal и wait имеют очевидное мнемоническое значение. В литературе вместо signal и wait применяются и другие названия с тем же самым функциональным смыслом.

С помощью семафоров проблема защиты ресурсов из раздела 10.3.2 решается просто

program sem example (* защита ресурса *) var PI: semaphore

begin

PI := 1;

cobegin

while true do (* бесконечный цикл *) begin (* процесс А *) wait(Pl);

(* защищенный ресурс *) signal(Pl);

end; (* процесс А *)

while true do (* бесконечный цикл *) begin (* процесс В *) wait(Pl);

(* защищенный ресурс *) signal(Pl);

end; (* процесс В *)

coend; end. (* sem example *)

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

Само по себе применение семафоров не гарантирует предотвращения тупиковых ситуаций. Если два процесса используют семафоры следующим образом

wait(Pl) wait(P2)

wait(P2) wait(Pl)

(* защищенный ресурс *)

(* защищенный ресурс *)

signal(Pl) signaI(P2)

signal(P2) signal(Pl)

то по-прежнему существует риск возникновения тупика. Если переключение процессов происходит между двумя операторами wait первой программы, а вторая про-Фамма выполнит свои операторы wait, то это приводит к тупику, поскольку каждая Рограмма ожидает от другой освобождения семафора. Проблема состоит в том, что, я семафор гарантирует неразрывность проверки и установки значения, он сам ос-ется защищенным ресурсом. В приведенном примере явно нарушен запрет после-ательного выделения, и это приводит к возможности тупиковых ситуаций, емафор может помочь при синхронизации взаимосвязанных действий. Напри-с вн " процесс должен работать с данными только после того, как они считаны ешнего порта, программа может иметь следующий вид:

Process "Чтение данных"

while true do begin

(* чтение новых данных *) signal(data available); end;

Process "Обработка данных"

while true do begin

wait(data available); (* обработка данных *) end;

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

Для защиты критических секций, в которые по определению в любой момент времени может входить только один процесс, используются двоичные семафоры, также называемые mutex (от mutual exclusion - взаимное исключение). В этом случае нельзя использовать обычные семафоры, так как их значение может превышать 1 и, следовательно, несколько программ могут получить доступ к ресурсу, уменьшая значения семафора. Операция signal над двоичным семафором всегда устанавливает его значение в 1. Операция wait уменьшает это значение с 1 до О и разрешает процессу продолжаться дальше. Если семафор имеет значение О, то процесс, выполняющий wait, должен ждать до тех пор, пока значение семафора не изменится.

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

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

В заключение отметим, что семафоры являются удобным средством высок уровня для замещения операции test and set и помогают избежать циклов занято ожидания. Однако их неправильное использование может привести к ситуаци нок и к тупикам.

10.4.2. События

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

begin

wait until condition;

modify data; end

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

Если использовать семафоры, то их потребуется два: один - для контроля досту-

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

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

Для решения этой проблемы была введена новая переменная синхронизации event (событие), с которой связаны операции await (ждать) и cause (вызвать)\ Процесс, выполнивший операцию await {event), остается в состоянии ожидания, пока значение переменной event не изменится. Это изменение контролируется с помощью операции cause. При наступлении события, т. е. выполнении операции cause {event), освобождаются все ожидающие его процессы, в то время как в случае семафора освобождается лишь один процесс. Операции с событиями можно реализовать либо с помощью двоичной переменной, либо с помощью счетчика, при этом основные принципы остаются одинаковыми.

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

var mutex: semaphore; change: event;

begin

while not condition do avfa.\t{change); wait(mMtex);

(* обработка общих переменных *) signal(mMtex); cause(c/2ange); end;

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

«*aiw ° "" значение не только "ждать", но и "предстоять", т. е. конструкцию

Чнг.-« трактовать, как "предстоит событие А". Глагол to cause означает "быть при-

ои , побудительным мотивом, "вызвать что-либо", т. е. конструкция cause (А) интерпре-РУется как "вызвать событие А" (в литературе и в операционных системах иногда испочь- «тся и другие названия). - Примеч. рео-