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

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

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

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

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

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

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

Тем не менее, если система перегружена, то набор процессов, для которых крайний срок будет упущен, окажется крайне непредсказуем (он будет зависеть от точных сроков и времени возникновения перегрузки.) Это — заметный недостаток для проектировщиков систем реального времени. Кроме того, алгоритм трудно реализовать аппаратно, и существуют сложности для представления крайних сроков в различных диапазонах (сроки не могут назначаться точнее, чем такты, использованные для планирования). Если для вычисления будущих крайних сроков используется модульная арифметика, поля, хранящие будущие крайние сроки должны содержать как минимум значение «удвоенная продолжительность наибольшего ожидаемого времени выполнения» + «сейчас». Поэтому планирование по ближайшему сроку завершения не является общепринятым в индустриальных компьютерных системах реального времени.

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

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

См. также

• 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.