EDF (Earliest Deadline First) — 절대 데드라인이 가까운 Job에 높은 우선순위를 부여하는 Job-level Fixed Priority(JFP) 정책. Job 릴리스 시 우선순위가 확정되어 Job 수명 동안 유지된다. 태스크 관점에서는 Job마다 우선순위가 달라져 dynamic priority처럼 보이지만, Job 단위로는 고정 (JFP).
규칙
Deadline이 짧을수록 높은 우선순위.
현재 ready job 중 가장 가까운 (남은) 절대 데드라인을 가진 Job이 CPU를 점유.
Optimality
EDF는 JFP 영역에서 최적이다.
즉 어떤 JFP 알고리즘이 태스크 집합을 스케줄 가능하게 할 수 있다면 EDF도 가능. JFP 분류에는 EDF 외에 LLF (Least Laxity First), FIFO 등이 있다.
RM과의 대비
| 항목 | RM | EDF |
|---|---|---|
| 분류 | TFP (task-level fixed) | JFP (job-level fixed) |
| 우선순위 기준 | 주기 (rate) | 절대 데드라인 |
| 우선순위 확정 시점 | 시스템 설계 시 (정적) | 매 Job 릴리스 시 |
| 최적 영역 | FP (implicit deadline) | JFP |
EDF가 RM을 이기는 사례
에 대해
- RM(Fixed Priority): 데드라인 Miss
- EDF(Dynamic Priority): OK
RM이 “정적 공식”에 묶여 유연성이 낮기 때문. 그러나 RM은 FP 영역 내에서는 최적이므로 RM이 실패하면 다른 FP도 실패한다 — 이 사례의 교훈은 JFP로 확장하면 더 넓은 영역을 커버한다는 점.