Earliest Deadline First

정의

Earliest deadline first(EDF)는 현재 요청들의 데드라인을 보고 우선순위를 매기는 스케줄링 방식이다. 데드라인이 가장 가까운 요청이 최고 우선순위를 받고 가장 먼 요청이 최저 우선순위를 받으며, 매 순간 우선순위가 가장 높고 아직 처리되지 않은 요청이 실행된다.[1]

Liu와 Layland는 1973년 논문에서 이 방식을 데드라인 구동 스케줄링이라 부르며 rate monotonic과 나란히 분석했다. 두 방식은 지금까지도 실시간 응용에서 가장 널리 논의되는 우선순위 배정이다.[2]

우선순위의 성격

우선순위가 태스크에 한 번 붙어 고정되지 않고 요청마다 달라지므로 정적 배정과 대비되는 동적 배정이다.[1] 다만 한 job의 우선순위는 그 job이 사는 동안 다른 job에 대해 뒤집히지 않으므로, 분류상으로는 우선순위가 job 단위로 정해지는 부류에 속하고 실행 도중에도 순서가 바뀌는 완전 동적 부류와는 구별된다.[3] 부류 구분 자체는 우선순위 기반 스케줄링에서 다룬다.

우선순위의 근거가 되는 절대 데드라인은 job이 활성화될 때마다 그 job의 release 시각에 상대 데드라인을 더해 새로 계산된다.[2] 두 데드라인의 구분은 데드라인에서, 주기와 실행 시간을 붙여 태스크를 적는 표기는 주기 태스크 모델에서 다룬다.

최적성과 이용률

데드라인이 주기와 같은 독립 주기 태스크 집합에 대해, EDF로 데드라인을 모두 지킬 수 있을 필요충분조건은 이용률이 1을 넘지 않는 것이다.

$$\frac{C_1}{T_1}+\frac{C_2}{T_2}+\cdots +\frac{C_m}{T_m}\le 1$$

이용률이 1을 넘으면 어떤 알고리즘으로도 스케줄할 수 없으므로, 이 조건은 EDF가 어떤 우선순위 배정으로 스케줄 가능한 집합이든 스케줄한다는 뜻이 된다. 이용률 상한이 일률적으로 100%라는 표현이 여기서 나온다.[1] 고정 우선순위 쪽의 상한과의 대비는 이용률 상한에서 다룬다.

최적성이 성립하는 조건은 프로세서가 하나이고, 선점이 허용되며, job이 자원을 두고 경쟁하지 않는 경우다. job을 선점할 수 없거나 프로세서가 둘 이상이면 EDF는 더 이상 최적이 아니다.[4]

구현 비용

고정된 우선순위 레벨 집합만 제공하는 커널 위에 EDF를 얹기는 쉽지 않다. 절대 데드라인을 우선순위 레벨로 사상해야 하는데, 이미 인접한 두 레벨에 배정된 데드라인 사이로 새 데드라인이 들어오면 넣을 레벨이 없어 기존 사상을 다시 흩어 놓아야 하고 최악의 경우 활성 데드라인 전부를 다시 사상해야 한다. 반면 커널 안에서 리스트로 준비 큐를 구현하는 경우라면 준비 큐를 절대 데드라인의 오름차순으로 유지한다는 점만 다를 뿐, 삽입·추출·디스패치 연산의 복잡도는 고정 우선순위 방식과 같다. 우선순위 레벨 수가 많지 않을 때 고정 우선순위 쪽이 레벨마다 FIFO 큐를 둬 삽입을 상수 시간에 끝낼 수 있는 것은 EDF가 따라 할 수 없는 이점인데, 데드라인 값마다 큐를 두면 큐 수가 감당할 수 없이 많아지기 때문이다.[2]

런타임 오버헤드

EDF가 rate monotonic보다 런타임 오버헤드가 크다는 것은 흔한 오해다. 절대 데드라인을 job마다 갱신해야 하므로 활성화 처리 비용이 조금 늘어나는 것은 사실이지만, 컨텍스트 스위치까지 함께 세면 결과가 뒤집힌다. 고정된 우선순위 순서를 지키려면 주기가 짧은 태스크가 긴 태스크의 job마다 끼어들어야 하는 반면 EDF에서는 같은 집합에서 선점이 훨씬 드물게 일어나며, 태스크 수가 늘수록 이 차이가 벌어진다.[2]

과부하에서의 거동

이용률이 1을 넘는 영구 과부하에서 EDF는 각 태스크의 주기가 이용률 배로 늘어난 것처럼 동작한다 — 정상 상태에서 태스크의 평균 주기는 원래 주기에 전체 이용률을 곱한 값이 된다. 고정 우선순위 쪽에서는 같은 상황에서 낮은 우선순위 태스크들이 아예 실행되지 못하고 막힐 수 있다. 두 거동 모두 예측 가능하며 어느 쪽이 나은지는 응용에 달렸다.[2]

과부하 시 위반 순서

일시적인 과부하에서 주기가 가장 긴 태스크부터 데드라인을 놓친다는 예상은 고정 우선순위에서도 EDF에서도 성립하지 않는다. 고정 우선순위에서는 최고 우선순위 태스크만 보호될 뿐 나머지는 주기와 무관하게 어느 것이든 놓칠 수 있고, EDF에서는 그런 보호마저 없다. 어느 태스크가 실행 시간을 넘길지 미리 알 수 없다면 고정 우선순위 쪽의 보호도 실익이 크지 않다.[2]

[1]

C. L. Liu and J. W. Layland, “Scheduling Algorithms for Multiprogramming in a Hard-Real-Time Environment,” Journal of the ACM, vol. 20, no. 1, pp. 46–61, 1973, doi: 10.1145/321738.321743.

[2]

G. C. Buttazzo, “Rate Monotonic vs. EDF: Judgment Day,” Real-Time Systems, vol. 29, no. 1, pp. 5–26, 2005, Accessed: Aug. 26, 2026. [Online]. Available: https://retis.santannapisa.it/~giorgio/paps/2005/rtsj05-rmedf.pdf

[3]

J. Carpenter, S. Funk, P. Holman, A. Srinivasan, J. Anderson, and S. Baruah, “A categorization of real-time multiprocessor scheduling problems and algorithms,” in Handbook of Scheduling: Algorithms, Models, and Performance Analysis, J. Y.-T. Leung, Ed., 2004. [Online]. Available: https://www.cs.unc.edu/~anderson/papers/multibook.pdf

[4]

C. Perkins, “Overview of real-time scheduling.” Lecture 3, Real-Time and Embedded Systems (M), University of Glasgow, 2008. Accessed: Aug. 26, 2026. [Online]. Available: https://csperkins.org/teaching/2008-2009/rtes/lecture03.pdf