|
Алгоритм '''Алгоритм планирования по ближайшему сроку завершения''' ('''EDF''') является одним из динамических алгоритмов планирования и используется в [[Операционная система реального времени|операционных системах реального времени]] для установкипомещения очередипроцесов в очередь по процессовприоритетам. При наступлении события планирования (задача завершена, установленапоявилась новая задача и т. дп.) очередьв ищеточереди ближайшуюпроизводится кпоиск крайнемупроцесса, времениближайшего еёк выполнениясвоему задачу,крайнему исроку этотисполнения. Этот процесс назначаетсябудет запланирован для выполнения следующим.
Планирование по ближайшему сроку завершения ''оптимально'' для preemptiveоднопроцессорных uniprocessors,систем с [[Вытесняющая многозадачность|вытеснением]] в томследующем отношении, чтосмысле: если существует возможность гарантированно выполнить набор независимых задач, каждая из которых характеризуется временем наступленияпоступления, требованием выполнения и крайним сроком завершения, так, чтобы гарантировать выполнение всех задач к крайнему сроку, этотто алгоритм назначитEDF задачитоже ксможет выполнению так, чтобы все они были к крайнему срокуэто завершенысделать.
При назначениипланировании периодических процессов, которые имеют крайние сроки эквивалентныекоторых равны их периодам, алгоритмEDF планированияимеет попредел ближайшему сроку завершения использует загрузку наиспользования 100 %. СледовательноТаким образом, [http://portal.acm.org/citation.cfm?id=78285 тест на возможность планирования] для данного алгоритма будетEDF:
При назначении периодических процессов, которые имеют крайние сроки равные их периодам, алгоритм планирования по ближайшему сроку завершения использует полную загрузку. Следовательно, тестом на возможности планирования для данного алгоритма будет<ref>Jia Xu, David Parnas. Scheduling Processes with Release Times, Deadlines, Precedence, and Exclusion Relations.IEEE TRANSACTIONS ON SOFTWARE ENGINEERING, VOL. 16. NO. 3. MARCH 1990</ref>:
: <math>U = \sum_{i=1}^{n} \frac{C_i}{T_i} \leq 1,</math>
где <math>\left\{C_i\right\}</math> — наихудшее время выполнения <math>n</math> процессов, а <math>\left\{T_i\right\}</math> — их соответствующий период между сроками наступленияих поступления (подразумевая, что он равен соответствующим крайним срокам).
То есть, назначение по ближайшему сроку завершения гарантирует, что все крайние сроки будут соблюдены, при условии что общая загрузка процессора не превышает 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сейчас»). Поэтому '''планирование по ближайшему сроку завершения''' не является общепринятым в индустриальных компьютерных системах реального времени.
Вместо этого большинство компьютерных систем реального времени используют планирование с фиксированным приоритетом. При фиксированном приоритете легче гарантировать, что при перегрузке процессы с низким приоритетом пропустят крайние сроки, в то время как процессы с высоким приоритетом по-прежнему будут выполнены вовремя.
СуществуетПроведено множество исследований по части '''планирования по ближайшему сроку завершения'''; существует возможность вычислить наихудшее время отклика процессов при этом алгоритме, для работы с иными типами процессов чем периодические процессы и использованию серверов для регулирования перегрузок.
== См. также ==
| 