2.4.3 Планирование в системах реального времени

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

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

. (2)

Если в систему поступает m периодических событий, событие с номером i поступает с периодом P_i, и на его обработку уходит C_i секунд работы процессора, все потоки могут быть своевременно обработаны только при выполнении этого условия.

2.5 Понятие взаимоблокировки

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

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

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

Для возникновения ситуации взаимоблокировки должны выполняться четыре условия [15].

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

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

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

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

Для исключения взаимоблокировки необходимо исключить какое-нибудь из этих условий.

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

Рисунок 17 – Графы распределения ресурсов: ресурс R отдан процессу A (а); процесс B ждёт ресурса S (б); взаимоблокировка (в)

На рисунке 18 изображена ситуация возникновения взаимоблокировки. Есть 3 процесса и 3 ресурса. На шагах 1-3 каждый процесс получает свой ресурс. На шагах 4-6 каждый процесс впадает в режим ожидания освобождения ресурса. Возникает взаимоблокировка. Данной ситуации можно избежать, если на время заблокировать один из процессов.

Рисунок 18 – Ситуация возникновения взаимоблокировки

Существуют 4 стратегии действий при взаимоблокировке:

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

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

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

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

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

Контрольные вопросы по разделу

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

2 В системе с потоками на уровне пользователя каждому потоку соответствует собственный стек или каждому процессу? А в системе с потоками на уровне ядра? Поясните.

3 Что такое состояние состязания?

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

5 Будет ли решение Петерсона проблемы взаимного исключения работать в случае планирования процессов с переключениями? В случае планирования без переключений?

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

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

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

9 Пусть в системе существует два процесса и три одинаковых ресурса. Каждому процессу требуется два ресурса. Возможна ли взаимоблокировка? Объясните ваш ответ.