Материал: 2. Процессы и потоки

6. Справедливое планирование

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

Критерий эффективности – способность системы выдерживать

заранее заданные интервалы времени между запуском программы и получением результата (реактивность системы)

гибкие

нарушения временного графика нежелательны, но

допустимы

взаимосвязанные

Ti - периодический набор задач pi - периоды

di - предельные сроки

сi - требования к времени выполнения

μ – коэффициент использования процессора

μi = сi / pi

Необходимое условие существования расписания:

μ =∑ сi / pi ≤ k,

где k - количество доступных процессоров.

Алгоритм Лью - Лейланда

Классический алгоритм для жестких систем реального времени с одним процессором. Алгоритм основан на следующих предположениях:

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

q Все задачи независимы.

q Срок выполнения задачи равен ее периоду.

q Максимальное время выполнения каждой задачи сi известно и постоянно. q Время переключения контекста можно игнорировать.

q Максимальный суммарный коэффициент загрузки процессора ∑ сi / pi ≤ n(21/n -1), где n – число задач.

Суть алгоритма: задача с самым коротким периодом получает наивысший приоритет, задача с наибольшим периодом получает наименьший приоритет.