Линец Г.И. Лекции по системам реального времени

Подождите немного. Документ загружается.

(* обработка общих переменных *) signal(mutex); cause(change);

end;

При каждом изменении переменной event все процессы проверяют

condition, и только те из них, для которых condition выполнено, могут

продолжаться. Доступ к общему ресурсу защищен с помощью семафора

mutex, при этом продолжается только один процесс. Это решение проще, чем

основанное только на семафорах. Оно также более эффективно, поскольку

процессы проверяют условия только тогда, когда это имеет смысл, т.е. после

изменения значения соответствующих переменных.

Важный тип события в системах реального времени связан с

внешними прерываниями. Программа обработки - обработчик прерываний -

ждет прерывания. Когда оно происходит, исполнение обработчика

возобновляется.

Лекция 3.3. Механизмы защиты ресурсов

1. Взаимные исключения.

2. Предотвращение тупиков.

3. Синхронизирующие объекты операционных систем.

4. Сигналы.

1. Взаимные исключения

Запрет прерываний может носить только исключительный характер.

Другой подход к защите ресурсов основан на взаимном исключении (mutual

exclusion). Никакой процесс не может получить доступ к ресурсу, пока этот

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

Корректная защита ресурсов предполагает следующее:

1. В любой момент времени доступ к защищенному ресурсу имеет

только один процесс.

2. Процессы остаются взаимно независимыми. Остановка одного из

процессов не должна препятствовать продолжению других.

Сформулированные требования соответствуют двум характеристикам

-безопасности и живучести. Безопасность (safety) означает, что доступ к за-

щищенному ресурсу в любой момент времени возможен только со стороны

одного из процессов. Живучесть (liveness) означает, что программа когда-

нибудь обязательно будет выполнена, иными словами, что она не остановит-

ся, и не будет ждать бесконечно. Безопасность - это статическое свойство, а

живучесть - динамическое. Безопасности можно добиться за счет частичного

или полного отказа от параллельного исполнения процессов. В действитель-

ности наиболее надежными являются строго последовательные программы,

поскольку в этом случае вообще невозможен параллельный доступ к ресурсу

из различных частей программы.

Распространенный метод управления доступом к ресурсам - примене-

ние переменных защиты. Простейший метод защиты основан на одной

двоичной переменной f1. Эта переменная изменяется обоими процессами

таким образом, что один из них имеет доступ к защищенному ресурсу, когда

f1 = true, а другой - когда f1 = false.

program protect_example (* защита ресурса *)

var fl: boolean;

begin

f1 : = true;

cobegin

while true do (* бесконечный цикл *)

begin (* процесс А *)

repeat until f1 = true;

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

f1 := false;

…

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

while true do (* бесконечный цикл *)

begin (* процесс В *) repeat until f 1 = false;

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

f1: = true;

…

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

coend;

end (* protect_example *)

Это решение удовлетворяет принципу взаимного исключения - два

процесса проверяют переменную f1 и входят в критическую секцию только

тогда, когда f1 имеет разные значения. Процесс, находящийся в критической

секции, может считать, что он владеет ресурсом монопольно.

С другой стороны, это решение создает новые проблемы. Наиболее

медленный процесс определяет общую скорость исполнения. Не имеет

значения, является ли А быстрее, чем В или наоборот, поскольку каждый

процесс для своего развития должен ждать, когда другой изменит значение

f1. Кроме этого, если исполнение процесса по той или иной причине будет

приостановлено, второй тоже должен быть остановлен, даже после одного

цикла. Более того, циклы занятого ожидания (busy loop), в которых

проверяется переменная защиты, напрасно расходуют процессорное время.

Эти проблемы - следствие введения управляющей переменной f1,

которая для синхронизации доступа к ресурсу создает дополнительные связи

между процессами. Модули, которые должны быть в принципе

независимыми, связаны через f1, которая делает из двух модулей фактически

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

выполняя оба процесса последовательно в одном цикле.

Другое решение — переустанавливать защитную переменную f1

после проверки ее значения и перед доступом к защищенному ресурсу т.е.

все процессы должны иметь следующий вид

repeat until f1 = true;

f1 := false;

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

f1 := true;

…

В этом случае процессы не связаны, и условие живучести выполнено,

но решение не является корректным. Если прерывание для переключения

процесса останавливает процесс А после контроля f1 = true, но перед при-

сваиванием f1 = false, а процесс В производит аналогичную проверку f1, то

оба процесса получают доступ к защищенному ресурсу, что противоречит

требованию безопасности. Использование для защиты ресурса только одной

переменной приводит к необходимости защищать переменную, поскольку

она сама становится общим ресурсом.

Было предложено несколько решений, основанных на нескольких

переменных защиты, но они скорее могут считаться курьезами, имеющими

мало практического значения. В заключение отметим, что для синхронизации

параллельных процессов лучше не вводить новых переменных, поскольку

они добавляют новые связи и сами становятся общими ресурсами.

Чтобы обойти эту проблему, некоторые процессоры имеют команду

test_and_set ("проверить_и_установить"), выполняющую проверку значения

булевой переменной и ее переустановку в ходе одной операции, которую

нельзя прервать. Смысл команды test_and_set в том, что на ее базе можно по-

строить процедуры синхронизации и защиты ресурсов. Объединения в одной

операции проверки переменной и ее модификации достаточно для обеспече-

ния защиты.

Команда test_and_set функционально эквивалентна циклу read-modify-

write на шине VMEbus. В обоих случаях гарантируется неразрывность двух

операций - чтения и записи. Если команда test_and_set отсутствует в исполь-

зуемом языке программирования или в наборе команд процессора, то ее

можно смоделировать другими средствами при условии, что допустим запрет

прерываний на короткое время.

Реализация критических секций и взаимного исключения в распреде-

ленной системе сама по себе представляет проблему. Для начала, нет прямо-

го эквивалента команды test_and_set, поскольку в этом случае имеется более

одного процессора. В принципе, для каждого ресурса можно установить еди-

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

сначала запрашивает координатора, который дает разрешение только одному

из запрашивающих процессов. Однако это решение не является столь про-

стым, как кажется. Единый координатор процессов является узким местом - и

при его отказе ресурс остается либо заблокированным, либо незащищенным.

Более того, если ресурс является просто переменной в памяти, то строить це-

лый алгоритм для его защиты нерационально. На самом деле координатор

сам является ресурсом, за доступ к которому будет происходить

конкуренция, не говоря уже о том, что в распределенной системе для

посылки запроса нужно еще получить и доступ к каналу связи.

Возможной альтернативой является использование маркера, который

перемещается между процессами. При этом в критическую секцию может

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

тях: в случае сбоя в процессе, являющемся владельцем маркера, должен су-

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

числа переменных в памяти этот метод может оказаться громоздким и трудно

реализуемым.

В заключение отметим, что в распределенных системах не существует

практичного, эффективного и простого метода защиты ресурсов, сравнимого

с командой test_and_set в однопроцессорных конфигурациях. Каждый случай

необходимо оценивать индивидуально и выбирать соответствующее практи-

ческое решение.

2. Предотвращение тупиков

Рассмотрим ситуацию, в которой два или больше процессов в системе

приостановлены и ожидают каких-нибудь событий. Если такие события для

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

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

ожидания. Такая ситуация называется тупиком (deadlock) (рис. 1).

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

продолжают исполняться фактически на одном месте. Это называется зави-

санием (starvation). Например, если процесс непрерывно проверяет значение

условной переменной, которое не изменяется, поскольку все остальные про-

цессы также заняты проверкой. Иными словами, процессы, оказавшиеся в

тупике, находятся в очереди ожидания (т. е. они блокированы), а зависшие

процессы исполняются, но фактически на одном месте.

Рисунок 1. - Тупик: а – взаимный; б – циркулярный

Тупик и одновременный доступ к защищенному ресурсу являются

двумя симметричными проблемами, относящимися к чрезвычайным ситуа-

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

несколько процессов выполняются параллельно.

Можно предложить несколько подходов к решению проблемы

тупиков. Простейшим из них является полное игнорирование проблемы и

работа в режиме, когда при возникновении тупика некоторые процессы

уничтожаются, например оператором, или производится ручная перезагрузка

системы. Естественно, такое решение неприемлемо для систем реального

времени, в особенности, если они должны работать без участия оператора.

Кроме стратегии с привлечением оператора, существуют еще и другие

-автоматического обнаружения и предотвращения. Первая предполагает

перераспределение ресурсов для разрешения ситуации или, в крайнем

случае, уничтожение одного из процессов. Вторая - распределение ресурсов

так, что тупики не возникают вообще.

Для обнаружения тупиковой ситуации необходимо непрерывно прове-

рять состояние всех исполняющихся процессов и их взаимодействие для

обнаружения циклов типа показанных на рис. 1. Такой контроль можно

делать с помощью фоновой (background) программы, периодически

запускаемой планировщиком. Однако и такая программа не может

гарантированно выявить все тупиковые ситуации. В распределенных

системах информация о состоянии всех процессов на всех ЭВМ также

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

повышенной нагрузки на сеть, которая при этом возникает, имеется риск

несогласованности сообщений о состоянии процессов, в результате которого

может произойти ошибочное выявление тупиковой ситуации с последующим

уничтожением соответствующих процессов.

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

рые могут привести к тупику. Программы должны быть структурированы и

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

тупиковые ситуации были исключены вообще.

Для возникновения тупика должны выполниться одновременно не-

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

возникнуть.

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

разрешен монопольный доступ.

2. Невытесняющее распределение ресурсов. Ресурс может быть осво-

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

сурс не может быть освобожден извне захватившего его процесса.

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

по одному, т. е. по мере необходимости.

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

Эти четыре утверждения косвенно дают ключ к предотвращению

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

тупик не возникнет.

Первое утверждение выполняется всегда, так как взаимное

исключение является принципиальным для гарантии упорядоченного

управления общими ресурсами.

Второе утверждение требует, чтобы операционная система

распознавала тупиковые ситуации и реагировала соответственно, вынуждая

процесс освободить ресурс. Это решение приемлемо лишь в случае, если

допускается принудительное уничтожение процесса, и зависит от механизма

восстановления.

В соответствии с третьим утверждением альтернативой выделению по

одному является выделение всех необходимых ресурсов одновременно.

Практичность этого решения, естественно, зависит от вида этих ресурсов и

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

хвативший их процесс. Если процессу выделяется десяток переменных на

время выполнения небольшого количества команд, без информации о том,

какие из них будут действительно использоваться — это одна ситуация, а ес-

ли один процесс надолго блокирует доступ к целой базе данных — это со-

всем другое дело.

Если система структурирована в соответствии с моделью "клиент-

сервер" и работает на основе замкнутых транзакций, то проблему тупиков

решить проще. В случае возникновения тупика можно просто отменить тран-

закцию, а не уничтожать один или несколько процессов.

Нарушение четвертого запрета чаще всего приводит к тупикам. Если

двум процессам требуются ресурсы А и В и первый их запрашивает в поряд-

ке А - В, а второй - В - А, то для возникновения тупика достаточно того, что-

бы первый процесс был прерван после захвата ресурса А и управление было

передано второму, который, в свою очередь, захватывает ресурс В. После

этого каждый процесс будет бесконечно ждать, пока другой не освободит за-

хваченный ресурс.

Четвертое утверждение дает практический способ избежать тупиков.

Тупик можно предотвратить, если определен точный порядок

(последовательность) запроса ресурсов, соблюдаемый всеми процессами. В

приведенном примере это означает, что "А должен быть распределен перед

В" и что все процессы строго следуют этому правилу. При этом

освобождение ресурсов должно происходить в порядке, обратном их

выделению. Этот метод, в принципе, несложно применить при разработке

системы реального времени, пока процессы находятся в руках одного или

небольшой группы программистов, но его практическая ценность быстро

уменьшается при возрастающем числе ресурсов или разделяемых

переменных.

4. Сигналы

Сигнал дает возможность задаче реагировать на событие, источником

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

вызывают прерывание задачи и выполнение заранее предусмотренных

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

работы самого процесса, а могут быть направлены процессу другим

процессом, то есть вырабатываться асинхронно. Синхронные сигналы чаще

всего приходят от системы прерываний процессора и свидетельствуют о

действиях процесса, блокируемых аппаратурой, например деление на нуль,

ошибка адресации, нарушение защиты памяти и т. д.

Примером асинхронного сигнала является сигнал с терминала. Во

многи ОС предусматривается оперативное снятие процесса с выполнения.

Для этого пользователь может нажать некоторую комбинацию клавиш

(Сtгl+С, Сtг1+Вгеаk) в результате чего ОС вырабатывает сигнал и направляет

его активному процессу. Сигнал может поступить в любой момент

выполнения процесса (то есть он является асинхронным), требуя от процесса

немедленного завершения работы. В данном случае реакцией на сигнал

является безусловное завершение процесса

В системе может быть определен набор сигналов. Программный код

процесса, которому поступил сигнал, может либо проигнорировать его, либо

прореагировать на него стандартным действием (например, завершиться),

либо выполнить специфические действия, определенные прикладным

программистом. В последнем случае в программном коде необходимо

предусмотреть специальные системные вызовы, с помощью которых

операционная система информируется, какую процедуру надо выполнить в

ответ на поступление того или иного сигнала.

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

между процессами и пользователями (терминалами). Поскольку посылка

сигнала предусматривает знание идентификатора процесса, то

взаимодействие посредством сигналов возможно только между

родственными процессами, которые могут получить данные об

идентификаторах друг друга.

В распределенных системах, состоящих из нескольких процессоров,

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

переменные, семафоры, сигналы и другие аналогичные средства, основанные

на разделяемой памяти, оказываются непригодными. В таких системах

синхронизация может быть реализована только посредством обмена

сообщениями.

Лекция 3.4. Обмен информацией между процессами

1. Общие области памяти.

2. Почтовые ящики.

3. Каналы.

4. Удаленный вызов процедур.

5. Сравнение методов синхронизации и обмена данными.

1. Общие области памяти

Взаимодействующие процессы нуждаются в обмене информацией.

Поэтому многозадачная операционная система должна обеспечивать

необходимые для этого средства. Обмен данными должен быть прозрачным

для процессов, т.е. передаваемые данные не должны изменяться, а сама

процедура должна быть легко доступна для каждого процесса.

Простейший метод - использование общих областей памяти, к

которым разные процессы имеют доступ для чтения/записи. Очевидно, что

такая область представляет собой разделяемый ресурс, доступ к которому

должен быть защищен, например, семафором. Главное преимущество общих

областей памяти заключается в том, что к ним можно организовать прямой и

мгновенный доступ, например один процесс может последовательно записы-

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

При программировании на машинном уровне общие области размеща-

ются в оперативной памяти по известным адресам. В языках высокого уровня

вместо этого используются глобальные переменные, доступные нескольким

дочерним процессам. Так, например, происходит при порождении потоков,

для которых переменные родительского процесса являются глобальными и

работают как общие области памяти. В случае возможных конфликтов дос-

тупа к общим областям они должны быть защищены семафорами.

2. Почтовые ящики

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

ными и синхронизацию процессов, - это почтовые ящики. Почтовый ящик

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

нения сообщений (рис. 1). Для обмена сообщениями различного типа можно

определить несколько почтовых ящиков.

Рисунок 1. - Работа почтового ящика

Во многих операционных системах почтовые ящики реализованы в

виде логических файлов, доступ к которым аналогичен доступу к

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

операции: создание, открытие, запись/чтение сообщения, закрытие, удаление.

В некоторых системах поддерживаются дополнительные служебные

функции, например счетчик сообщений в почтовом ящике или чтение

сообщения без удаления его из ящика.

Почтовые ящики размещаются в оперативной памяти или на диске и

существуют лишь до выключения питания или перезагрузки. Если они физи-

чески расположены на диске, то считаются временными файлами, уничто-

жаемыми после выключения системы. Почтовые ящики не имеют имен по-

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

тификаторы, которые используются процессами при обращении.

Для создания почтового ящика операционная система определяет ука-

затели на область памяти для операций чтения/записи и соответствующие

переменные для защиты доступа. Основными методами реализации являются

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

список, который, в принципе, не накладывает никаких ограничений на число

сообщений в почтовом ящике.

В наиболее распространенных реализациях процесс, посылающий со-

общение, записывает его в почтовый ящик с помощью оператора, похожего

на оператор записи в файл

put_mailbox ( # 1, message)

Аналогично, для получения сообщения процесс считывает его из поч-

тового ящика с помощью оператора вида

get _mailbox (# 1, message)

Запись сообщения в почтовый ящик означает, что оно просто копиру-

ется в указанный почтовый ящик. Может случиться, что в почтовом ящике не

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

слишком мал, либо хранящиеся в нем сообщения еще не прочитаны.

При чтении из почтового ящика самое старое сообщение

пересылается в принимающую структуру данных и удаляется из ящика.

Почтовый ящик -это пример классической очереди, организованной по

принципу FIFO. Операция чтения из пустого ящика приводит к различным

результатам в зависимости от способа реализации — либо возвращается

пустая строка (нулевой длины), либо операция чтения блокируется до

получения сообщения. В последнем случае, чтобы избежать нежелательной

остановки процесса, необходимо предварительно проверить число

сообщений, имеющихся в данный момент в ящике.

3. Каналы

Канал (pipe) представляет собой средство обмена данными между дву-

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

Этот механизм был первоначально разработан для среды UNIX как средство

перенаправления входа и выхода процесса. В ОС UNIX физические устрой-

ства ввода/вывода рассматривают как файлы, а каждая программа имеет

стандартное устройство ввода (вход) и стандартное устройство вывода

(выход), клавиатуру и экран монитора - можно переопределить, например, с

помощью файлов. Когда выход одной программы перенаправляется на вход

100