Билет №25

1. Стратегия планирования «Наиболее ранняя задача первая» (Earliest Task First - etf). Стратегия планирования «Наиболее ранняя задача первая» (Earliest Task First - etf)

С тратегия ETF использует статические приоритеты задач и учитывает ограничение на число процессоров. Тем не менее, задача с более высоким приоритетом не обязательно планируется перед задачей с менее высоким приоритетом. Причиной является то, что на каждом шаге ETF вычисляет наиболее раннее время запуска всех готовых к планированию задач и выбирает задачу с минимальным временем запуска. Задача готова к планированию, если все предшествующие задачи уже спланированы. Наиболее раннее время запуска задачи вычисляется путем оценивания времен запуска задачи на всех возможных процессорах, включая ранее не использовавшийся процессор. Если две задачи имеют одинаковое наиболее раннее время запуска, выбирается задача с более высоким статическим приоритетом. Статические приоритеты вычисляются на основе применения стратегии ALAP и оценивания наиболее поздних времен запуска задач.

Рассмотрим стратегию на примере графа задач, показанного на рис.1. Предварительно выполняется упорядочение задач с присвоением им статического приоритета на основе применения стратегии ALAP (рис.1а):

Задача	n1	n2	n3	n4
Наиболее позднее время начала выполнения	0	24	25	45
Приоритет	1	2	3	4

Построение плана происходит на четырех шагах (число шагов равно числу узлов в графе задач).

Шаг 1. Задача n₁ готова к планированию, имеет наивысший статический приоритет 1 и соответственно минимальное время начала выполнения. Поскольку ни одного процессора еще не задействовано, назначаем узел n₁ на процессор PE0 (рис.2).

Ш аг 2. Задачи n₂ и n₃ готовы к планированию. Наиболее раннее время запуска обеих задач равно 5. Задача n₂ имеет более высокий статический приоритет 2, поэтому выбирается на шаге 2. Поскольку один процессор уже задействован, рассматриваем попытку введения второго процессора и исследуем два варианта I и II назначения узла n₂ на процессор PE0 и на новый процессор PE1 (рис.3). В варианте I время запуска задачи n₂ равно 5. В варианте II время запуска равно 6. Следовательно, предпочтительным является вариант I, его и выбираем для дальнейшего рассмотрения.

Шаг 3. Задача n₃ готова к планированию, имеет с татический приоритет 3 и наиболее позднее время запуска 25. Поскольку задачи n₁ и n₂ назначены на шаге 2 на процессор PE0, рассматриваем попытку введения второго процессора и снова исследуем два варианта I и II назначения узла n₃ на процессор PE0 и на новый процессор PE1 (рис.4). В варианте I время запуска задачи n₃ равно 25. В варианте II время запуска также равно 25. Для дальнейшего рассмотрения выбираем вариант I, поскольку он использует только один процессор.

Шаг 4. Задача n₄ готова к планированию, имеет наиболее раннее время запуска 45, статический приоритет 4 и наиболее позднее время начала выполнения 45. Поскольку задачи n₂ и n₃ назначены на шаге 3 на процессор PE0, снова рассматриваем попытку введения второго узла и исследуем два варианта I и II назначения узла n₄ на процессор PE0 и на новый процессор PE1 (рис.5). В варианте I время запуска задачи n₄ равно 35. В варианте II время запуска также равно 45. В качестве искомого асинхронного плана выбираем вариант I, поскольку он имеет меньшее время запуска задачи n₄. Как показано на рис.6, время реализации плана равно 43 единицам.