최단 마감 우선 스케줄링 문서 원본 보기

{{위키데이터 속성 추적}}
{{출처 필요|날짜=2010-9-17}}
'''최단 마감 우선 스케줄링'''(Earliest Deadline First Scheduling, 줄여서 EDF 스케줄링)은 [[실시간 운영 체제]]에서 사용되는 동적 [[CPU 스케줄링]] [[알고리즘]]의 하나이다.
[[프로세스]]를 [[우선순위]] [[큐 (자료 구조)|큐]]를 통해 수행한다. 스케줄링 이벤트가 일어날 때마다, 큐에서 마감시간이 가장 가까운 프로세스를 탐색하여 다음에 수행되도록 한다. 주기적인 작업 뿐만 아니라 단일 처리기 환경에서 선점형 프로세스들을 스케줄링할 수 있다. 작업(task)이 N개일 때 복잡도는 <math>O(n^2)</math>이다.

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

== 예시 ==
주기적 프로세스 3개를 EDF로 스케줄링해보자.
{| class="wikitable"
|-
!프로세스!!수행시간!!주기
|-
|P1||1||8
|-
|P2||2||5
|-
|P3||4||10
|}
실행시간과 주기의 단위시간은 같으며, 1단위시간이 10밀리세컨드라고 하자.
P1는 8단위시간(80밀리세컨드)에 시작하여 1단위(10밀리세컨드)동안 동작한다. CPU 사용율은 다음과 같이 된다.
:<math>\frac{1}{8} + \frac{2}{5} + \frac{4}{10} = 0.925</math>

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

== 같이 보기 ==
* [[RM 스케줄링]]

[[분류:스케줄링 알고리즘]]
[[분류:운영체제 기술]]