Надежность систем реального времени

Для СРВ критерии надежности определяются факторами:

– защита кода ОС от воздействия процессов пользователя;

– защита одних процессов пользователя от других;

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

– наличие встроенных средств сигнализации и обработки внештатных (исключительных) ситуации.

Рассмотрим более подробно перечисленные выше факторы.

Под «воздействием» процесса понимается группа операций, которые как правило включает любая программа:

– чтение данных из памяти;

– запись данных в память;

– чтение данных из порта ввода/вывода;

– запись данных в порт ввода/вывода;

– прочие инструкции процессора (арифметические операции, команды ветвления, и т.д.).

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

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

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

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

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

Планирование задач

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

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

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

Ключевым вопросом планирования является выбор момента принятия решения:

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

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

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

г) решение по диспетчеризации должно приниматься после разблокировки процесса;

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

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

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

Существуют несколько схем назначения приоритетов.

Фиксированные приоритеты – приоритет задаче назначается при ее создании и не меняется в течение ее жизни. В схемах планирования ОСРВ требуется, чтобы приоритет каждой задачи был уникальным, поэтому часто ОСРВ имеют большое число приоритетов (обычно 255 и более).

Турнирное определение приоритета – приоритет последней исполнявшейся задачи понижается.

Приоритет по алгоритму round robin – приоритет задачи определяется ее начальным приоритетом и временем ее обслуживания. Чем больше задача обслуживается процессором, тем меньше ее приоритет (но не опускается ниже некоторого порогового значения). Эта схема применяется в большинстве UNIX систем. В разных системах различные алгоритмы планирования задач могут вводить новые схемы изменения приоритетов, так в системе OS-9 приоритеты ожидающих задач увеличиваются для избежания слишком больших времен ожидания.

Возможные типы алгоритмов диспетчеризации.

«Первым пришел – первым обслужен» (алгоритм FIFO). Является алгоритмом планирования без переключений. Процессам предоставляется доступ к процессору в том порядке, в котором они его запрашивают. При FIFO диспетчеризации процесс продолжает выполнение, пока не наступит момент, когда он:

· добровольно уступает управление;

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

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

«Кратчайшая задача–первая». Этот алгоритм без переключений предполагает, что временные отрезки работы известны заранее. В этом алгоритме первым выбирается самая короткая задача. Данная схема работает только в случае одновременного наличия задач.

«Наименьшее оставшееся время выполнения». Является версией предыдущего алгоритма с переключениями. В соответствии с этим алгоритмом планировщик выбирает процесс с наименьшим оставшимся временем выполнения. В этом случае необходимо знать заранее время выполнения каждого процесса. Когда поступает новый процесс, его время выполнения сравнивается с оставшимся временем выполнения текущего процесса. Если время выполнения нового процесса меньше, текущий процесс приостанавливается и управление передается новому процессу. Это позволяет быстро обслуживать короткие процессы.

Рис. 1.9. Карусельная диспетчеризация. Процесс A выполняется до тех пор, пока он не использовал свой квант времени; затем выполняется следующий процесс, находящийся в состоянии готовности (процесс B).

«Карусельная диспетчеризация (циклическое планирование)».При карусельной диспетчеризации процесс (рис. 1.9) продолжает выполнение, пока не наступит момент, когда он:

1.10. Адаптивная диспетчеризация. Процесс A использовал свой квант времени; его приоритет снизился на 1. Выполняется следующий процесс в состоянии готовности (процесс B)

· добровольно уступает управление (т.е. блокируется);

· вытесняется процессом с более высоким приоритетом;

· использовал свой квант времени (timeslice). После того, как процесс использовал свой квант времени, управление передается следующему процессу, который находится в состоянии готовности и имеет тот же уровень приоритета.

«Адаптивная диспетчеризация».При адаптивной диспетчеризации (рис. 1.10) процесс ведет себя следующим образом:

· Если процесс использовал свой квант времени (он не блокировался), происходит снижение приоритета (priority decay) (его приоритет уменьшается на 1). "Пониженный" процесс не продолжает "снижаться", даже если он использовал еще один квант времени и не блокировался – он снизится на один уровень ниже своего исходного приоритета.

· Если процесс блокируется, то ему возвращается первоначальное значение приоритета.

Планирование периодических процессов

Внешние события, на которые СРВ должна реагировать, разделяют на периодические (возникающие через регулярные промежутки времени) и непериодические (возникающие непредсказуемо). При нескольких обрабатываемых потоков событий в зависимости от времени, затрачиваемого на обработку каждого из событий, может оказаться, что система не в состоянии своевременно обработать все события. Если в систему поступает m периодических событий, событие с номером i поступает с периодом P_i и на его обработку уходит C_i секунд работы процессора, все потоки могут быть своевременно обработаны только при выполнении условия

.

СРВ, удовлетворяющая этому условию, называется поддающейся планированию (планируемой). Соотношение является просто частью процессорного времени, используемого процессом i, а сама сумма – это коэффициент использования (коэффициент загруженности) процессора, который не может быть больше 1.

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

Классическим примером статического алгоритма планирования реального времени для прерываемых периодических процессов является алгоритм RMS (Rate Monotonic Scheduling – планирование с приоритетом, пропорциональным частоте). Этот алгоритм может использоваться для процессов, удовлетворяющих следующим условиям:

1. Каждый периодический процесс должен быть завершен за время его периода.

2. Ни один процесс не должен зависеть от любого другого процесса.

3. Каждому процессу требуется одинаковое процессорное время на каждом интервале.

4. У непериодических процессов нет жестких сроков.

5. Прерывание процесса происходит мгновенно, без накладных расходов.

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

Другим популярным алгоритмом планирования является алгоритм EDF (Earliest Deadline First – процесс с ближайшим сроком завершения в первую очередь). Алгоритм EDF представляет собой динамический алгоритм, не требующий от процессов периодичности. Он не требует и постоянства временных интервалов использования процессора. Когда процессу требуется процессорное время, он объявляет о своем присутствии и о сроке выполнения задания. Планировщик хранит список процессов, сортированный по срокам выполнения заданий. Алгоритм запускает первый процесс в списке, у которого самый близкий по времени срок выполнения. Когда новый процесс переходит в состояние готовности, система сравнивает его срок выполнения со сроком выполнения текущего процесса. Если у нового процесса график более жесткий, он прерывает работу текущего процесса.

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

Взаимоблокировки

В компьютерной системе существует большое количество ресурсов, каждый из которых может использоваться в конкретный момент времени только одним процессом. Часто процесс для выполнения задачи нуждается в исключительном доступе не к одному, а к нескольким ресурсам. Предположим, что имеется два процесса A и B. Процесс A имеет в исключительном доступе ресурс R1, процесс B – ресурс R2. Если при этом процессу A для продолжения работы потребуется ресурс R2, то его запрос на получение ресурса будет отклонен до тех пор, пока ресурс не будет освобожден процессом B. Если же процессу B для продолжения работы окажется необходимым иметь в исключительном доступе ресурс R1, то и процесс B окажется, как и процесс A, заблокированным. Такая ситуация называется тупиком, тупиковой ситуацией или взаимоблокировкой.

Ресурсы могут быть разделены на два типа: выгружаемые и невыгружаемые. Выгружаемый ресурс можно безболезненно забрать у владеющего им процесса. Образцом такого ресурса является память. Невыгружаемый ресурс – это ресурс, который нельзя забрать у текущего процесса без уничтожения результатов вычислений.

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

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

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

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

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

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

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

При взаимоблокировках используются четыре стратегии:

1. Пренебрежение проблемой в целом. Если Вы проигнорируете проблему, возможно, затем она проигнорирует Вас.

2. Обнаружение и восстановление. При взаимоблокировке обнаружить ее и предпринять какие-либо действия.

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

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

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

Контрольные вопросы

1. Необходимые требования к ОС для обеспечения предсказуемости.

2. ОСРВ с монолитной архитектурой.

3. ОСРВ на основе микроядра.

4. Объектно-ориентированная ОСРВ?

5. Дайте определение алгоритма планирования?

6. В каких случаях необходима синхронизация?

7. Что такое связанные задачи?

8. Что такое ресурс?

9. Что такое критические секции?

10. С какими проблемами можно столкнуться в борьбе за ресурсы?

11. Что такое асинхронное взаимодействие? Преимущества и недостатки.

12. Что такое прерывание? Как оно работает?

13. Методы обработки прерываний в ОСРВ?

14. Как осуществляется аппаратная защита памяти?

15. Что такое исключение?

16. Что такое утечка памяти?

17. Как обрабатываются исключения в ядре ОС?

18. Чем характеризуется надежность ОСРВ?