[운영체제] CPU 스케줄링: 실시간 CPU 스케줄링 - (3)

 

Earliest-Deadline-First 스케줄링(EDF Scheduling)

---

 

Earliest-Deadline-First(EDF) 스케줄링 기법은 마감시간(deadline)에 따라서 우선순위를 동적으로 부여한다.

 

마감시간이 빠를수록 우선순위가 높아지고, 늦을수록 우선순위가 낮아진다.

 

프로세스는 실행 가능한 상태가 되면, 시스템에 마감시간을 알려야 한다.

 

우선순위는 새로 실행 가능한 프로세스의 마감시간을 반영해서 조정된다.

 

 

RM 스케줄링과 달리, EDF 스케줄링은 프로세스들이 주기적일 필요도 없고, CPU burst time이 상수일 필요도 없다.

 

대신 프로세스는 실행 가능할 때 스케줄러에게 마감시간을 알려야 한다.

 

 

이론적으로 EDF 스케줄링은 각 프로세스의 마감시간 요구를 만족시키고 CPU 이용률이 100%이므로 최적(optimal)이다.

 

실제로는 프로세스 간 문맥 교환(cotext switching), 인터럽트 처리(interrupt handling)로 인해 100% CPU 이용률은 불가능하다.

 

 

 

 

 

 

Proportionate Share 스케줄링

---

 

proportionate share 스케줄러는 모든 애플리케이션에 총 T개의 시간 몫을 할당하여 실행한다.

 

한 개의 애플리케이션이 N개의 시간 몫을 할당받으면, 그 애플리케이션은 총 프로세서 시간(total processor time)의 N/T 시간을 할당받은 것이다.

 

 

proportionate share 스케줄러는 애플리케이션이 시간 몫을 할당받는 것을 보장하기 위해 승인-제어 정책(admission-control policy)과 함께 동작해야 한다.

 

승인-제어 정책은 사용 가능한 충분한 몫이 존재할 때만 특정한 몫을 요구하는 client를 허용한다.