Текст лекции

Ключевые вопросы

Лекция № 5. Процессы и внешние события. Часть 3

Продолжительность:2 часа (90 мин.)

· Основные понятия и определения: операционная система (ОС), программное обеспечение (ПО), системное программное обеспечение.

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

· Смешанные алгоритмы планирования

12.2.1 Планирование в системах реального времени— до 15 мин.

В системах реального времени, в которых главным критерием эффективности является обеспечение заданного времени реакции, планирование имеет особое значение. Любая система реального времени должна реагировать на сигналы управляемого объекта в течение заданных временных ограничений. Необходимость тщательного планирования работ облегчается тем, что в системах реального времени весь набор выполняемых задач известен зара­нее. Кроме того, часто в системе имеется информация о временах выполнения задач, моментах активизации, предельно-допустимых сроках ожидания ответа и т. д. Эти данные могут быть использованы планировщиком для создания ста­тического расписания или для построения адекватного алгоритма динамическо­го планирования.

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

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

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

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

Предположим, что имеется периодический набор задач {T_i} с периодами p_i, пре­дельными сроками d_i, и требованиями ко времени выполнения c_i. Для проверки возможности существования расписания достаточно проанализировать расписа­ние на периоде времени, равном, по крайней мере, наименьшему общему множи­телю периодов этих задач. Необходимым критерием существования расписания для набора периодических задач является следующее достаточно очевидное ут­верждение: сумма коэффициентов использования m_i = c_i/p_i должна быть меньше или равна k, где k – количество доступных процессоров, то есть:

m_i = S c_i/p_i £ k

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

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

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

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

- Введение ограничивающих предположений о поведении набора задач.

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

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

Алгоритм основан на следующих предположениях:

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

- Все задачи независимы. Между любой парой задач не существует никаких ог­раничений на предшествование или на взаимное исключение.

- Срок выполнения каждой задачи равен ее периоду p_i.

- Максимальное время выполнения каждой задачи c_i известно и постоянно.

- Время переключения контекста можно игнорировать.

- Максимальный суммарный коэффициент загрузки процессора S c_i/p_i при су­ществовании n задач не превосходит n (2^{1/ n} – 1). Эта величина при стремле­нии n к бесконечности приблизительно равна In 2, то есть 0,7.

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

Если же периоды повторения задач кратны периоду выполнения самой короткой задачи, то требование к максимальному коэффициенту загрузки процессора смяг­чается – он может доходить до 1.

12.2.2 Смешанные алгоритмы планирования— до 15 мин.

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

Рассмотрим более подробно алгоритм планирования в операционной системе UNIX System V Release 4. В этой ОС понятие «поток» отсутствует, и планирова­ние осуществляется на уровне процессов. В этой системе реализована вытесняющая многозадачность, основанная на использовании при­оритетов и квантования.

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

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

Процессы разделения времени были до появления UNIX System V Release 4 един­ственным классом процессов, и по умолчанию эта система назнача­ет новому процессу именно этот класс. Состав класса процессов разделения вре­мени наиболее неопределенный и часто меняющийся в отличие от системных процессов и процессов реального времени. Для справедливого распределения времени процессора между процессами в этом классе используется стратегия ди­намических приоритетов. Величина приоритета, назначаемого процессам разде­ления времени, вычисляется пропорционально значениям двух составляющих: пользовательской части и системной части. Пользовательская часть приоритета может быть изменена администратором и владельцем процесса, но в последнем случае только в сторону его снижения.

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

Другой пример относится к операционной системе OS/2. Планирование здесь основано на использовании квантования и абсолютных динамических приори­тетов. На множестве потоков определены приоритетные классы – критический (time critical), серверный (server), стандартный (regular) и остаточный (idle), в каждом из которых имеется 32 приоритетных уровня. Потоки критического класса имеют наивысший приоритет. В этот класс могут быть отнесены, напри­мер, системные потоки, выполняющие задачи управления сетью. Следующий по приоритетности класс предназначен, как это следует из его названия, для потоков, обслуживающих серверные приложения. К стандартному классу могут быть отнесены потоки обычных приложений. Потоки, входящие в остаточный класс, имеют самый низкий приоритет. К этому классу относится, например, по­ток, выводящий на экран заставку, когда в системе не выполняется никакой ра­боты.

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

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

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

- Если поток ушел на выполнение операции ввода-вывода, то после ее заверше­ния он получит наивысшее значение приоритета своего класса.

- Приоритет потока автоматически повышается, когда он поступает на выпол­нение.

ОС динамически устанавливает величину кванта, отводимого потоку для выпол­нения. Величина кванта зависит от загрузки системы и интенсивности подкачки. Параметры настройки системы позволяют явно задать границы изменения кван­та. В любом случае он не может быть меньше 32 мс и больше 65 536 мс. Если по­ток был прерван до истечения кванта, то следующий выделенный ему интервал выполнения будет увеличен на время, равное одному периоду таймера (около 32 мс), и так до тех пор, пока квант не достигнет заранее заданного при настрой­ке ОС предела.

Благодаря такому алгоритму планирования в OS/2 ни один поток не будет «за­быт» системой и получит достаточно процессорного времени.