ЭКСПЕРИМЕНТАЛЬНОЕ СРАВНЕНИЕ АЛГОРИТМОВ ПЛАНИРОВАНИЯ РЕАЛЬНОГО ВРЕМЕНИ В ТИКОВОМ ЭМУЛЯТОРЕ ПЕРИОДИЧЕСКИХ ЗАДАЧ

Введение

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

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

Цель данной статьи — показать, как тиковая симуляция позволяет сопоставить эталонные алгоритмы планирования и проверить, соответствует ли поведение эмулятора базовым теоретическим ожиданиям: условиям перегрузки, свойствам EDF, достаточной границе RM и характерной стоимости LLF.

Модель симуляции

Время в эмуляторе является дискретным и измеряется в целых тиках. На каждом тике выполняется одинаковая последовательность действий: релиз новых экземпляров периодических задач, проверка незавершённых джобов, вычисление состояния готовой очереди, вызов функции scheduler_select, выполнение выбранной задачи на один тик и обновление статистики.

Каждая задача характеризуется периодом T, временем выполнения C и относительным дедлайном D. Теоретическая утилизация нагрузки вычисляется как U = Σ Cᵢ / Tᵢ. Если U > 1, одному процессору физически не хватает времени для выполнения всех работ, поэтому пропуски дедлайнов становятся неизбежными независимо от выбранного алгоритма [2, с. 46].

Для сравнения использовались алгоритмы RM, EDF, LLF, FP, FCFS, RR, SRTF и LRTF. RM назначает более высокий приоритет задачам с меньшим периодом. EDF выбирает джоб с ближайшим абсолютным дедлайном. LLF ориентируется на минимальную лаксити. Остальные алгоритмы используются как контрольные или контрастные политики, позволяющие увидеть влияние самого правила выбора задачи.

Таблица 1.

Краткая характеристика алгоритмов планирования

Наборы нагрузок и метрики

Для анализа использовались нагрузки разных классов: лёгкая, умеренно плотная, сбалансированная, стрессовая, всплесковая и нагрузка с взаимно простыми периодами. Такой набор позволяет проверить поведение алгоритмов как в условиях большого запаса процессорного времени, так и в режиме перегрузки.

Основные метрики делятся на три группы. Первая группа — сводка прогона: фактическая утилизация CPU, число пропусков дедлайнов, переключения контекста, средняя и максимальная длина очереди готовых задач. Вторая группа — показатели по отдельным задачам: время ожидания, число выполненных тиков, вытеснения, время отклика и jitter. Третья группа — временные ряды, позволяющие увидеть динамику выбранной задачи, длины очереди и минимальной лаксити.

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

Таблица 2.

Классы нагрузок для экспериментального анализа

Результаты сравнения

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

Умеренно плотная нагрузка из пяти задач лучше разделяет алгоритмы. При U = 0,922 алгоритмы EDF и LLF не допускают пропусков дедлайнов, тогда как RM и FP фиксируют по 12 нарушений. При этом LLF выполняет больше переключений контекста, чем EDF. Это согласуется с теоретическим ожиданием: динамический учёт срочности может улучшать соблюдение дедлайнов, но не всегда уменьшает стоимость исполнения.

Сбалансированная нагрузка из шести задач при U = 0,900 оказалась планируемой для проверенных алгоритмов. На таком наборе удобно демонстрировать отчёты и временные ряды, потому что алгоритмы работают без немедленного провала по дедлайнам, но нагрузка уже достаточно плотная для анализа очереди и переключений.

Стрессовая нагрузка из восьми задач имеет U = 1,430. Это означает, что суммарная потребность задач превышает доступное время одного процессора. В результате пропуски возникают у всех алгоритмов. Эксперимент здесь нужен не для поиска идеального алгоритма, а для проверки, что эмулятор не показывает невозможного расписания там, где его не должно быть.

Таблица 3.

Сводные экспериментальные наблюдения

Сопоставление с теорией

Первое теоретическое ожидание связано с перегрузкой. Если U > 1, пропуски дедлайнов неизбежны для одноядерной модели, потому что задачам требуется больше процессорного времени, чем доступно. Эксперименты на стрессовой и всплесковой нагрузках подтверждают это свойство: нарушения возникают у всех проверенных алгоритмов.

Второе ожидание связано с EDF. В идеальной вытесняющей модели независимых периодических задач EDF является оптимальным при условии U ≤ 1 [2, с. 46]. В экспериментах EDF не допускает пропусков на планируемых наборах и начинает фиксировать нарушения при перегрузке. Такое поведение соответствует учебной модели и подтверждает корректность расчёта абсолютных дедлайнов.

Третье ожидание касается RM. Граница Лю — Лейланда является достаточной, но не необходимой. Это значит, что нагрузка ниже границы гарантированно планируема для RM, но превышение границы само по себе ещё не доказывает невозможность расписания [2, с. 49]. В экспериментах гармоническая и сбалансированная нагрузки могут выполняться без пропусков, хотя находятся выше простой достаточной оценки.

Наконец, LLF демонстрирует характерную цену динамического выбора по лаксити. Алгоритм может учитывать срочность, но частое изменение лаксити приводит к росту переключений контекста. Это важно для учебного анализа: минимизация пропусков дедлайнов не всегда означает минимальную стоимость исполнения.

Таблица 4.

Сопоставление теоретических положений и наблюдений

Заключение

Экспериментальное сравнение показало, что тиковый эмулятор воспроизводит ожидаемое поведение классических алгоритмов планирования. При низкой утилизации дедлайны выполняются без нарушений, при U > 1 нарушения становятся неизбежными, а различия между алгоритмами проявляются в метриках дедлайнов, переключений контекста и очереди готовых задач.

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