- •Раздел 1 Основы теории операционных систем
- •Раздел 2 Машинно-зависимые свойства операционный систем
- •Раздел 3 Машинно-независимые свойства операционных систем
- •Раздел 1 основы теории ос
- •Общие сведения об операционных системах
- •Архитектура ос
- •Распределенная обработка в сетевых ос
- •Сетевые службы.
- •Раздел 2 машинно – зависимые компоненты ос
- •Архитектурные особенности модели микропроцессорной системы
- •Обработка прерываний
- •Планирование процессов
- •Обслуживание ввода-вывода
- •Управление реальной памятью
- •Управление виртуальной памятью
- •Раздел 3 машинно-независимые свойства операционных систем
- •Работа с файлами
- •Планирование заданий
- •Синхронизация процессов и потоков
- •Защищённость и отказоустойчивость ос
Планирование заданий
Планирование в системах реального времени
В системах реального времени, в которых главным критерием эффективности является обеспечение временных характеристик вычислительного процесса планирование имеет особое значение. Любая система реального времени должна реагировать на сигналы управляемого объекта в течение заданных временных ограничений.
В зависимости от характера возникновения запросов на выполнение задач разделяют их на два типа:
периодические;
спорадические.
Начиная с момента первоначального запроса все будущие моменты запроса периодической задачи можно определить заранее путем прибавления к моменту начального запроса величины, кратной известному периоду. Времена запросов на выполнение спорадических задач заранее не известны.
Предположим, что имеется периодический набор задач {Тi} с периодами pi предельными сроками di и требованиями ко времени выполнения ci. Для проверки возможности существования расписания достаточно проанализировать расписание на периоде времени, равном по крайней мере наименьшему общему множителю периодов этих задач. Необходимым критерием существования расписания для набора периодических задач является следующее достаточно очевидное утверждение: сумма коэффициентов использования µi=ci/pi должна быть меньше или равна k, где k — количество доступных процессоров, то есть:
µ = ∑ сi / рi <= k
При выборе алгоритма планирования следует учитывать данные о возможной зависимости задач. Эта зависимость может выступать, например, в виде ограничений на последовательность выполнения задач или их синхронизации, вызванной взаимными исключениями (запрете выполнения некоторых задач в течение определенных периодов времени).
Рассмотрим классический алгоритм для жестких систем реального времени с одним процессором, разработанный в 1973 году Лью (Liu) и Лейландом (Layland). Алгоритм является динамическим, то есть он использует вытесняющую многозадачность и основан на относительных статических (неизменяемых в течение жизни задачи) приоритетах. Алгоритм основан на следующих предположениях:
запросы на выполнение всех задач набора, имеющих жесткие ограничения на время реакции, являются периодическими;
все задачи независимы. Между любой парой задач не существует никаких ограничений на предшествование или на взаимное исключение;
срок выполнения каждой задачи равен ее периоду рi ;
максимальное время выполнения каждой задачи ci известно и постоянно;
время переключения контекста молено игнорировать;
максимальный суммарный коэффициент загрузки процессора ∑ ci/pi при существовании n задач не превосходит n (21/n - 1). Эта величина при стремлении n к бесконечности приблизительно равна In 2, то есть 0,7.
Суть алгоритма состоит в том, что всем задачам назначаются статические приоритеты в соответствии с величиной их периодов выполнения. Задача с самым коротким периодом получает наивысший приоритет, а задача с наибольшим периодом выполнения получает наименьший приоритет. При соблюдении всех ограничений этот алгоритм гарантирует выполнение временных ограничений для всех задач во всех ситуация.
Если же периоды повторения задач кратны периоду выполнения самой короткой задачи, то требование к максимальному коэффициенту загрузки процессора смягчается — он может доходить до 1.
Существуют также алгоритмы с динамическим изменением приоритетов, которые назначаются в соответствии с такими текущими параметрами задачи как, например, конечный срок выполнения (deadline). При необходимости назначения некоторой задачи на выполнение выбирается та, у которой текущее значение разницы между конечным сроком выполнения и временем, требуемым для ее непрерывного выполнения, является наименьшим.