Earliest Deadline First

Earliest Deadline First (EDF, «первый — самый ранний срок») — это динамический алгоритм планирования задач в операционных системах реального времени, при котором в каждый момент времени на исполнение выбирается задача с наименьшим (самым ранним) абсолютным дедлайном. Алгоритм относится к классу динамических приоритетных алгоритмов, где приоритет задачи не фиксирован, а изменяется в зависимости от близости её срока выполнения. EDF является оптимальным алгоритмом планирования для однопроцессорных систем в условиях вытесняющего планирования: если набор задач может быть запланирован каким-либо алгоритмом, то EDF также сможет его запланировать.

История и происхождение

Концепция планирования на основе дедлайнов была впервые формально описана в 1973 году американскими учёными Чарльзом Льюисом Льюином и Джоном Лейландом в контексте систем реального времени. Однако широкую известность алгоритм получил после работы Чанга и Лейланда (1973), где была доказана его оптимальность для однопроцессорных систем. В 1980-х годах EDF стал активно применяться в авионике, робототехнике и промышленной автоматике. В 1990-х годах алгоритм был адаптирован для многопроцессорных систем, хотя его оптимальность в таких условиях теряется из-за необходимости миграции задач между процессорами.

Принцип работы

Определение дедлайна

Каждая задача в системе реального времени характеризуется:

• Временем поступления (release time) — момент, когда задача готова к выполнению.
• Временем выполнения (execution time) — максимальное процессорное время, необходимое для завершения задачи.
• Дедлайном (deadline) — момент времени, к которому задача должна быть выполнена.

В EDF приоритет задачи обратно пропорционален её абсолютному дедлайну: чем раньше дедлайн, тем выше приоритет. Если две задачи имеют одинаковый дедлайн, выбор между ними произволен (обычно по порядку поступления).

Вытесняющее планирование

EDF является вытесняющим алгоритмом: если в момент выполнения задачи появляется новая задача с более ранним дедлайном, текущая задача приостанавливается (вытесняется), и процессор передаётся новой задаче. После завершения более приоритетной задачи выполнение прерванной задачи возобновляется с точки останова.

Пример работы

Пусть есть три задачи:

• Задача A: время выполнения = 2 мс, дедлайн = 4 мс, поступление в 0 мс.
• Задача B: время выполнения = 3 мс, дедлайн = 6 мс, поступление в 1 мс.
• Задача C: время выполнения = 1 мс, дедлайн = 3 мс, поступление в 2 мс.

В момент 0 мс выполняется задача A (дедлайн 4 мс). В момент 1 мс появляется задача B (дедлайн 6 мс) — дедлайн A (4 мс) раньше, поэтому A продолжает выполнение. В момент 2 мс появляется задача C (дедлайн 3 мс) — её дедлайн раньше, чем у A (4 мс), поэтому A вытесняется, и выполняется C. После завершения C (3 мс) возобновляется A, завершаясь к 4 мс. Затем выполняется B, завершаясь к 7 мс. Все задачи выполнены в срок.

Математическая модель

Условие планируемости

Для набора периодических задач с фиксированными временами выполнения и дедлайнами, равными периодам, необходимым и достаточным условием планируемости в однопроцессорной системе является: \[ \sum_{i=1}^{n} \frac{C_i}{T_i} \leq 1 \] где \(C_i\) — время выполнения задачи \(i\), \(T_i\) — её период (дедлайн). Если сумма загрузки процессора превышает 1, ни один алгоритм не сможет выполнить все задачи в срок.

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

Теорема об оптимальности

EDF оптимален в том смысле, что если существует какое-либо расписание, удовлетворяющее всем дедлайнам для данного набора задач, то расписание, построенное EDF, также будет удовлетворять всем дедлайнам. Это доказано для однопроцессорных систем с вытесняющим планированием. Для многопроцессорных систем оптимальность теряется, и используются модификации, такие как Global EDF или Partitioned EDF.

Классификация

По типу дедлайнов

• Абсолютные дедлайны — фиксированные моменты времени (например, «завершить к 10:00:00»). Используется в стандартном EDF.
• Относительные дедлайны — интервалы времени от момента поступления (например, «завершить через 5 мс после поступления»). Преобразуются в абсолютные добавлением времени поступления.

По способу учёта вытеснения

• Вытесняющий EDF — стандартный вариант, описанный выше.
• Невытесняющий EDF — задача выполняется до завершения, даже если появляется более срочная задача. Используется в системах, где вытеснение невозможно или нежелательно (например, при работе с критическими ресурсами). Планируемость при этом ухудшается.

По числу процессоров

• Однопроцессорный EDF — классический вариант.
• Многопроцессорный EDF:
• Global EDF — единая очередь задач для всех процессоров; задачи могут мигрировать между процессорами. Требует сложных механизмов синхронизации.
• Partitioned EDF — задачи статически распределяются между процессорами; на каждом процессоре работает свой экземпляр EDF. Проще в реализации, но может привести к неравномерной загрузке.

Применение

Операционные системы реального времени

EDF используется в ядрах операционных систем реального времени, таких как RTEMS, QNX (в некоторых конфигурациях), VxWorks (с поддержкой динамических приоритетов). В Linux алгоритм реализован в виде планировщика SCHED_DEADLINE, добавленного в версии 3.14 (2014 год). SCHED_DEADLINE позволяет задавать для потоков параметры времени выполнения, периода и дедлайна.

Промышленная автоматика

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

Авионика и космическая техника

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

Мультимедиа и потоковая передача

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

Преимущества и недостатки

Преимущества

• Оптимальность для однопроцессорных систем — максимальная загрузка процессора (до 100% при равных периодах и дедлайнах).
• Динамическая адаптация — приоритеты автоматически корректируются при изменении загрузки.
• Простота реализации — требуется только сравнение дедлайнов.

Недостатки

• Чувствительность к перегрузке — при превышении загрузки процессора (сумма > 1) происходит каскадное нарушение дедлайнов (эффект «домино»).
• Высокие накладные расходы на вытеснение — при большом числе задач частые переключения контекста снижают производительность.
• Сложность анализа планируемости для задач с произвольными дедлайнами или взаимодействующих через ресурсы.
• Неоптимальность на многопроцессорных системах — требуется дополнительная координация.

Сравнение с другими алгоритмами

Rate Monotonic Scheduling (RMS)

RMS — статический алгоритм, где приоритет обратно пропорционален периоду задачи. RMS проще в реализации и анализе, но допускает загрузку процессора не более ~69% для произвольного набора задач (при дедлайнах, равных периодам). EDF позволяет достичь 100% загрузки, но требует больше вычислительных ресурсов на переключение приоритетов.

Deadline Monotonic Scheduling (DMS)

DMS — статический алгоритм, где приоритет обратно пропорционален относительному дедлайну. Он оптимален для задач с дедлайнами, меньшими периодов, но уступает EDF в гибкости.

Least Laxity First (LLF)

LLF выбирает задачу с наименьшим резервом времени (laxity = deadline - current_time - remaining_execution_time). LLF также оптимален, но требует больше вычислений и может вызывать частые переключения контекста (эффект «дрожания»). EDF менее чувствителен к этому эффекту.

Интересные факты

• В алгоритме SCHED_DEADLINE в Linux используется модификация EDF с поддержкой группового планирования и ограничений на время выполнения (runtime enforcement).
• В некоторых реализациях EDF для предотвращения «голодания» задач с большими дедлайнами применяется механизм «бюджета времени» (budget), аналогичный алгоритму Constant Bandwidth Server.
• EDF лежит в основе планировщика многих систем управления дронами и роботами, где требуется одновременно обрабатывать данные с нескольких датчиков.

Критика

Основная критика EDF связана с его поведением при перегрузке: в отличие от статических алгоритмов (например, RMS), где при превышении загрузки нарушаются только дедлайны задач с низким приоритетом, в EDF могут быть пропущены дедлайны всех задач, включая критические. Для смягчения этого эффекта используются механизмы приоритетных наследований и резервирования ресурсов.

Источники

• Liu, C. L., & Layland, J. W. (1973). Scheduling algorithms for multiprogramming in a hard-real-time environment. Journal of the ACM, 20(1), 46–61.
• Buttazzo, G. C. (2011). Hard Real-Time Computing Systems: Predictable Scheduling Algorithms and Applications. Springer.
• Sha, L., Abdelzaher, T., & Cervin, A. (2004). Real-time scheduling theory: A historical perspective. Proceedings of the IEEE, 92(1), 109–127.
• Документация ядра Linux: SCHED_DEADLINE (kernel.org/doc/Documentation/scheduler/sched-deadline.txt).