최단 마감 우선 스케줄링

최단 마감 우선 스케줄링(Earliest Deadline First Scheduling, 줄여서 EDF 스케줄링)은 실시간 운영 체제에서 사용되는 동적 CPU 스케줄링 알고리즘의 하나이다. 프로세스를 우선순위 큐를 통해 수행한다. 스케줄링 이벤트가 일어날 때마다, 큐에서 마감시간이 가장 가까운 프로세스를 탐색하여 다음에 수행되도록 한다. 주기적인 작업 뿐만 아니라 단일 처리기 환경에서 선점형 프로세스들을 스케줄링할 수 있다. 작업(task)이 N개일 때 복잡도는 $O(n^{2})$이다.

RM 스케줄링은 사용률에 제약이 있는 반면 EDF 스케줄링은 사용률이 1이하이기만 하면 스케줄링 가능하다. 또한, 수학적으로 최적이라는 것이 증명되어 있다. 하지만 현실적으로 프로세스의 마감시간을 예측하는 것이 어렵기 때문에, 실제로는 RM 스케줄링을 사용하는 경우가 많다.

예시

주기적 프로세스 3개를 EDF로 스케줄링해보자.

프로세스	수행시간	주기
P1	1	8
P2	2	5
P3	4	10

실행시간과 주기의 단위시간은 같으며, 1단위시간이 10밀리세컨드라고 하자. P1는 8단위시간(80밀리세컨드)에 시작하여 1단위(10밀리세컨드)동안 동작한다. CPU 사용율은 다음과 같이 된다.

${\frac {1}{8}}+{\frac {2}{5}}+{\frac {4}{10}}=0.925$

임의 개수의 프로세스를 동작시킬 때 논리적인 CPU 사용율의 상한은 100%이다. 따라서 이 시스템은 스케줄링 가능하다.

같이 보기

• RM 스케줄링