Глава 10. Программирование систем реального врец,ц

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

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

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

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

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

10.3. Взаимные исключения и тупики

10.3.1. Защита ресурсов

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

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

и то

время. Таким образом, информация о наличии мест является ресурсом, под-еаШйМ защите, причем в данном случае этот ресурс существует только в виде об-,зсти памяти.

qjcTb программы, в которой осуществляется доступ к тем или иным ооразом за-дйДенному ресурсу (protected resource), называется критической секцией (c?itical

section)-

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

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

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

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

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

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

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

Ют, Аов

ся

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

запрашивающему процессу исключительно в порядке очереди - кто раньше Росил, тот раньше и получает. Для обслуживания медленных устройств с после-ательным доступом иногда применяется механизм спулинга (spooling). Устрой-0 закрепляется монопольно за одним процессом - спулером (spooler). Для осталь-

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

Глава 10. Программирование систем реального врецц о.З- взаимные т;ю11инвмии и тупики

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

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

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

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

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

10.3.2. Взаимное исключение

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

Слово spool - это аббревиатура от simultaneous peripheral operations on line - паралле ная работа с периферийными устройствами.

..Як-

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

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

2. Процессы остаются взаимно независимыми. Остановка одного из процессов ] должна препятствовать продолжению других.

Сформулированные требования соответствуют двум характеристикам - безопг ности и живучести. Безопасность (safety) означает, что доступ к защищенному р сурсу в любой момент времени возможен только со стороны одного из процеса )Кивучесть (liveness) означает, что программа когда-нибудь обязательно будет в полнена, иными словами, что она не остановится и не будет ждать бесконечно. Бег пасность - это статическое свойство, а живучесть - динамическое. Безопасное можно добиться за счет частичного или полного отказа от параллельного исполнен процессов. В действительности наиболее надежными являются строго последо! тельные программы, поскольку в этом случае вообще невозможен параллельный / ступ к ресурсу из различных частей программы.

Распространенный метод управления доступом к ресурсам - применение nef менных защиты. Простейший метод защиты основан на одной двоичной перемени fl. Эта переменная изменяется обоими процессами таким образом, что один из н имеет доступ к защищенному ресурсу, когда fl = true, а другой - когда fl = false.

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

var fl; boolean;

begin

fl :== true;

cobegin

while true do (* бесконечный цикл *) begin (* процесс A *) repeat until f 1 = true;

(* защищенный ресурс *) fl := false;

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

while true do (* бесконечный цикл *) begin (* процесс В*) repeat until f 1 = false;

(* защищенный ресурс *) fl := true;

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

coend; end (* protect example *)

I лава I и. I ipol раммириьаиие систем реального

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

С другой стороны, это решение создает новые проблемы. Наиболее медленн -процесс определяет общую скорость исполнения. Не имеет значения, является чи д быстрее, чем В или наоборот, поскольку каждый процесс для своего развития допже,, ждать, когда другой изменит значение fl. Кроме этого, если исполнение процесса по той или иной причине будет приостановлено, второй тоже должен быть остановлен даже после одного цикла. Более того, циклы занятого ожидания {busy loop), в которых проверяется переменная защиты, напрасно расходуют процессорное время.

Эти проблемы - следствие введения управляющей переменной fl, которая для синхронизации доступа к ресурсу создает дополнительные связи между процессами. Модули, которые должны быть в принципе независимыми, связаны через fl, которая делает из двух модулей фактически последовательный процесс. Тот же результат можно получить, исключив f 1 и выполняя оба процесса последовательно в одном цикле.

Другое решение - переустанавливать защитную переменную fl после проверки ее значения и перед доступом к защищенному ресурсу т. е. все процессы должны иметь следующий вид

repeat until f 1 = true; fl := false;

(* защищенный ресурс *) fl := true;

В этом случае процессы не связаны, и условие живучести выполнено, но решение не является корректным. Если прерывание для переключения процесса останавливает процесс А после контроля fl = trne, но перед присваиванием fl = false, а процесс В производит аналогичную проверку fl, то оба процесса получают доступ к защищенному ресурсу, что противоречит требованию безопасности. Использование для защиты ресурса только одной переменной приводит к необходимости защищать переменную, поскольку она сама становится общим ресурсом.

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

Для того чтобы обойти эту проблему, некоторые процессоры имеют команд} test and set ("проверить и установить"), выполняющую проверку значения буле вой переменной и ее переустановку в ходе одной операции, которую нельзя прервать-Смысл команды test and set в том, что на ее базе .можно построить процедуры син хронизации и защиты ресурсов. Объединения в одной операции проверки перемен ной и ее модификации достаточно для обеспечения защиты.

Команда test and set функционально эквивалентна циклу read-modify-write на шине VMEbus (раздел 8.,3.2). В обоих случаях гарантируется неразрывность ДВУ операций - чтения и записи. Если команда test and set отсутствует в используемо* языке программирования или в наборе команд процессора, то ее можно смоделиро

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

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

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

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

10.3.3. Тупики

Рассмотрим ситуацию, в которой два или больше процессов в системе приостановлены и ожидают каких-нибудь событий. Если такие события для каждого из ожидающих процесса могут быть инициированы только другим ожидающим процессом, О все процессов окажутся в состоянии бесконечного ожидания. Такая ситуация называется тупиком {deadlock) (рис. 10.7).

ждет "В"

ждет

tHc. 10.7. Тупик: а - взаимный; - циркулярный