Operating System : EDF(Earliest Deadline First) Algorithm

---

EDF 란?

Earliest-Deadline-First(EDF) 란?

“Deadline 에 가장 가까운 process 를 탐색하여 execute 시킨다.”
——> “Deadline 에 가장 가까워진 process 일수록 Higher priority 를 부여한다.”

• Real-time Scheduling 에서 사용하는 Optimal(가장 최적) 한 dynamic priority Scheduling.
• 각각 process 마다의 Deadline 에 맞추어 Priority를 부여한다.
• Process를 우선순위 큐(Priority queue) 를 통해 execute 한다.
• 어떠한 process 간의 Deadline 이 동일한 경우에는 사용자가 지정한 priority 부여 기준을 따른다.
• 사용률에 제약이 있는 RM Scheduling 에 비해 EDF Scheduling은
  사용률(Utilization) 이 1 이하 이기만 하면 스케줄링이 가능하다.
• EDF 알고리즘은 최소 응답 시간과 최소 deadline miss rate을 보장 한다.
• EDF 알고리즘에서는 작업의 실행 중간에 "preemption" 을 수행할 수 있다.
• “preemption” 은 시스템의 응답 시간(response time)을 최소화하고, deadlock을 방지하는 데 도움이 된다.
  ——-> 더 높은 Priority를 가진 process가 실행 중이던 기존 process 를 중단하고 CPU Resources 를 차지할 수 있다.
  

=============> ("Dynamic Priority Scheduling")

EDF_Comparator 코드

• Processes 의 Deadline 이 동일 할 경우 :
  저는 each process 마다의 activeTime (실제 실행시간) == (releaseTime - execTime) 이 가장 짧은 것에 Higher priority를 부여했습니다.

EDF 예시

EDF Scheduling 예시

출처: 위키백과 EDF_Scheduling

RM / EDF Compare Simulation

Rate Monotonic Scheduling / EDF Scheduling 비교 시뮬레이션

- FF: (RM|EDF) == (실패|실패)
- FT: (RM|EDF) == (실패|성공)
- TF: (RM|EDF) == (성공|실패)
- TT: (RM|EDF) == (성공|성공)

• 도합 10000 가지의 Tasks 를 Random create 하여 시뮬레이션을 한 결과이다.
• 한번의 시뮬레이션에 1000개의 Task(Random created)를 사용.
• 총 10번(10000개의 Tasks) execute.
  
  

1.EDF와 RM 모두 실패한 경우(Deadline miss)는 10번의 시뮬레이션 모두 0번.

2. RM은 실패하였으나, EDF는 성공한 경우 - 1168개의 tasks. (1168/10000)

3. EDF는 실패하였으나, RM은 성공한 경우 - 0개의 tasks.

4.EDF와 RM 모두 성공한 경우 - 8832 개의 tasks. (8832/10000)

RM / EDF Compare Simulation Results

Rate Monotonic Scheduling / EDF Scheduling 비교 시뮬레이션 결과

실험 결과, RM 이 성공한 task라면 무조건 EDF 도 성공한다.

- 하지만, RM 이 Deadline miss 한 tasks 에 대해 EDF 는 성공한 case가 존재한다.

• 위와 같이 EDF Scheduling은 RM Scheduling 보다 Optimal 할 수 있다.

.....고 생각하기 쉽지만, 현실적으로 Processes 들의 Deadline을 예측하기 어렵기 때문에,
 실제로는 RM Scheduling 을 사용하는 경우가 많다고 한다.

Task Lists

• Earliest-Deadline-First(EDF) 란?
• EDF Scheduling 예시
• Rate Monotonic Scheduling / EDF Scheduling 비교 시뮬레이션
• Rate Monotonic Scheduling / EDF Scheduling 비교 시뮬레이션 결과