2. Планирование заданий

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

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

В зависимости от характера возникновения запросов на выполнение задач разделяют их на два типа:

1. периодические;

2. спорадические.

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

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

µ = ∑ с_i / р_i <= k

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

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

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

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

3. срок выполнения каждой задачи равен ее периоду р_i ;

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

5. время переключения контекста молено игнорировать;

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

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

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

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