Алгоритм планирования по ближайшему сроку завершения

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

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

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

$U=\sum _{i=1}^{n}{\frac {C_{i}}{T_{i}}}\leq 1,$

где $\left\{C_{i}\right\}$ — наихудшее время выполнения $n$ процессов, а $\left\{T_{i}\right\}$ — их соответствующий период между сроками наступления (подразумевая, что он равен соответствующим крайним срокам).

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

Тем не менее, если система перегружена, то набор процессов, для которых крайний срок будет упущен, окажется крайне непредсказуем (it will be a function of the exact deadlines and time at which the overload occurs.) Это заметный недостаток для проектировщиков систем реального времени. Кроме того, алгоритм трудно реализовать аппаратно, и существуют сложности для представления крайних сроков в различных диапазонах (сроки не могут назначаться точнее чем такты, использованные для планирования). Если для вычисления будущих крайних сроков используется modular arithmetic, поля, хранящие будущие крайние сроки должны accommodate как минимум значение ((«duration» {of the longest expected time to completion} * 2) + «now»). Поэтому планирование по ближайшему сроку завершения не является общепринятым в индустриальных компьютерных системах реального времени.

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

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

См. также

• SCHED_DEADLINE — реализация планировщика задач по ближайшему времени завершения в ядре Linux

Литература

• Pierre G. Jansen, Sape J. Mullender, Paul J.M. Havinga, Hans Scholten. Lightweight EDF Scheduling with Deadline Inheritance
• Stankovic, J.A. Deadline Scheduling for Real-Time Systems: Edf and Related Algorithms. — Springer US, 1998. — 273 p. — ISBN 9780792382690.
• Leung, J.Y.T. Handbook of Scheduling: Algorithms, Models, and Performance Analysis. — CRC Press, 2004. — 1224 p. — ISBN 9780203489802.

Алгоритм планирования по ближайшему сроку завершения