Сетевые операционные системы

Глава 4. Процессы и потоки

2004-12-05

Продолжение

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

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

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

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

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

ПРИМЕЧАНИЕ. При рассмотрении в качестве примеров подсистем планирования пото-ков/процессов в операционных системах Windows NT, OS/2 и UNIX System V Release 4 было отмечено, что во всех этих системах имеется приоритетный класс реального време-ни. Для потоков/процессов, относящихся к этому классу, каждая из вышеназванных сис-тем не гарантирует выполнение заданных временных ограничений, а лишь обеспечивает предпочтение в скорости обслуживания. Следовательно, эти ОС могут быть основой для построения мягких систем реального времени, но непригодны для жестких систем реаль-ного времени.

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

Предположим, что имеется периодический набор задач {Ti} с перио-дами pi, предельными сроками di и требованиями ко времени выполнения сi. Для проверки возможности существования расписания достаточно проанали-зировать расписание на периоде времени, равном по крайней мере наимень-шему общему множителю периодов этих задач. Необходимым критерием существования расписания для набора периодических задач является сле-дующее достаточно очевидное утверждение: сумма коэффициентов исполь-зования mi = ci/pi должна быть меньше или равна k, где k - количество дос-тупных процессоров, то есть:

M=S сi/рi <= k

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

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

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

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

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

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

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

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

Запросы на выполнение всех задач набора, имеющих жесткие ограничения на время реакции, являются периодическими.
Все задачи независимы. Между любой парой задач не существует никаких ограничений на предшествование или на взаимное исключение.
Срок выполнения каждой задачи равен ее периоду pi.
Максимальное время выполнения каждой задачи сi известно и постоянно.
Время переключения контекста можно игнорировать.
Максимальный суммарный коэффициент загрузки процессора S ci/pi при существовании n задач не превосходит n(2^1/n - 1). Эта величина при стремлении n к бесконечности приблизительно равна 1 n 2, то есть 0,7.

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

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

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

Моменты перепланировки

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

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

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

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

Первые четыре цикла работы планировщика, приведенные на рисунке, были инициированы прерываниями от таймера по истечении квантов време-ни (эти события обозначены на рисунке как Т).

Следующая передача управления планировщику была осуществлена в результате выполнения потоком 3 системного запроса на ввод-вывод (собы-тие I/O). Планировщик перевел этот поток в состояние ожидания, а затем пе-реключил процессор на поток 2. Поток 2 полностью использовал свой квант, произошло прерывание от таймера, и планировщик активизировал поток 1.

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

В следующем цикле работы планировщик активизировал поток 4, а затем, после истечения кванта и сигнала от таймера, управление получил по-ток 2. Этот поток не успел использовать свой квант, так как был снят с вы-полнения в результате возникшей ошибки (событие ER).

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

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

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

Продолжение следует...