최단 마감 우선 스케줄링
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.
1. 개요
최단 마감 우선 스케줄링(EDF)은 CPU 스케줄링 알고리즘의 하나로, 각 프로세스의 데드라인을 기준으로 우선순위를 할당하여 가장 마감 시간이 임박한 프로세스에 CPU를 할당한다. EDF는 CPU 사용률의 한계가 100%라는 장점이 있지만, 과부하 상태에서 데드라인을 지키지 못하는 프로세스를 예측하기 어렵고, 구현이 복잡하다는 단점도 있다. EDF는 고정 우선순위 스케줄링보다 높은 부하 환경에서 데드라인을 보장할 수 있으며, 프로세스 응답 시간의 최악의 경우를 계산하거나, 주기적 프로세스 외에도 적용할 수 있다는 장점이 있다. EDF 스케줄링은 다양한 연구가 진행되고 있으며, 오픈 소스 및 실시간 커널에서 구현되어 사용된다.
더 읽어볼만한 페이지
- 스케줄링 알고리즘 - 스케줄링 (컴퓨팅)
스케줄링은 운영 체제가 시스템의 목적과 환경에 맞춰 작업을 관리하는 기법으로, 장기, 중기, 단기 스케줄러를 통해 프로세스를 선택하며, CPU 사용률, 처리량 등을 기준으로 평가하고, FCFS, SJF, RR 등의 알고리즘을 사용한다. - 스케줄링 알고리즘 - 선입 선출
선입 선출(FIFO)은 먼저 들어온 데이터가 먼저 나가는 큐(Queue) 형태의 자료 구조로, 컴퓨터 과학, 전자 공학, 네트워크 장비 등에서 널리 활용된다. - 운영체제 기술 - 프로세스
프로세스는 컴퓨터에서 실행되는 프로그램의 인스턴스로, 운영 체제가 시스템 자원을 효율적으로 관리하며 멀티태스킹 환경에서 독립적인 실행 흐름을 유지한다. - 운영체제 기술 - 커널 (컴퓨팅)
커널은 운영 체제의 핵심으로, 하드웨어와 소프트웨어 간 상호 작용을 관리하며 시스템 보안, 자원 관리, 하드웨어 추상화, 프로세스 스케줄링, 프로세스 간 통신, 다중 작업 환경 지원 등의 기능을 제공하고, 모놀리식, 마이크로, 혼합형 커널 등으로 구현되며 가상화 및 클라우드 컴퓨팅 환경에서 중요성이 커지고 있다.
최단 마감 우선 스케줄링 | |
---|---|
기본 정보 | |
종류 | 스케줄링 알고리즘 |
분야 | 실시간 시스템 |
다른 이름 | EDF 스케줄링 (Earliest Deadline First Scheduling) |
상세 정보 | |
유형 | 동적 스케줄링 |
사용 환경 | 실시간 운영 체제 (RTOS) 임베디드 시스템 |
특징 | 마감 시간이 가장 빠른 작업에 우선순위 부여 이론적으로 최적 (단일 프로세서 시스템) |
장점 | 구현 용이 최적 스케줄링 가능 |
단점 | 문맥 교환으로 인한 오버헤드 발생 가능 프로세서 활용률 100%에 가까울수록 불안정 |
고려 사항 | 마감 시간, 실행 시간, 작업의 중요도 |
활용 예시 | 항공기 제어 시스템 의료 장비 로봇 제어 |
관련 연구 | 스케줄링 가능성 분석 우선순위 역전 현상 |
참고 자료 | 실시간 시스템 관련 서적, 논문 |
2. 특징
고정 우선순위 스케줄링과 같은 속도 단조 스케줄링에 비해 EDF는 더 높은 부하 환경에서도 모든 마감 시간을 지킬 수 있다. 그러나 시스템이 과부하 상태일 때 마감 시간을 지킬 수 없게 되는 프로세스를 예측하기 어렵고, 실제 산업용 실시간 시스템에서는 많이 사용되지 않는다. EDF 스케줄링에 대한 많은 연구가 진행되고 있지만, 멀티프로세싱 시스템에서는 제대로 작동하지 않는다.
2. 1. 이론적 배경
주기적으로 실행해야 하는 프로세스의 데드라인은 해당 주기에 해당하며, EDF (최단 마감 우선 스케줄링)에 의한 CPU 사용률의 한계는 100%이다. 즉, EDF는 CPU 사용률의 합계가 100%를 넘지 않는 한 모든 데드라인을 지킬 수 있음을 보장한다. 따라서 고정 우선순위 스케줄링과 같은 속도 단조 스케줄링에 비해 EDF는 더 높은 부하 환경에서도 모든 데드라인을 지킬 수 있다.그러나 시스템이 과부하 상태일 때 데드라인을 지킬 수 없게 되는 프로세스를 예측할 수 없다 (데드라인과 과부하 발생 시간에 따라 달라진다). 이 단점은 실시간 시스템 설계에서 심각하다. 또한 이 알고리즘을 구현하는 것도 어렵고, 데드라인을 몇 바이트로 나타내려면 약간의 기술이 필요하다 (데드라인은 수 밀리초일 수도 있고 수백일 수도 있다). 이 때문에 EDF는 실제 산업용 실시간 시스템에서는 많이 사용되지 않는다.
EDF 스케줄링에 관해서는 많은 연구가 진행되고 있다. EDF로 프로세스의 응답 시간 최악의 경우를 계산할 수 있으며, 주기적 프로세스 외에도 적용 가능하다. 단, 멀티프로세싱 시스템에서는 EDF가 제대로 작동하지 않는다.
2. 2. 장점
EDF(최단 마감 우선 스케줄링)는 CPU 사용률의 한계가 100%이다. 즉, EDF는 CPU 사용률의 합계가 100%를 넘지 않는 한 모든 마감 시간을 지킬 수 있음을 보장한다. 따라서 고정 우선순위 스케줄링과 같은 속도 단조 스케줄링에 비해 더 높은 부하 환경에서도 모든 마감 시간을 지킬 수 있다.2. 3. 단점
EDF 스케줄링에서는 바람직하지 않은 마감일 교환이 발생할 수 있다. 프로세스는 임계 구역 내에서 공유 자원을 사용하여 더 이른 마감일을 가진 다른 프로세스를 선호하여 선점적으로 디스케줄링되는 것을 방지할 수 있다. 이 경우 스케줄러가 실행 중인 프로세스에 해당 자원을 기다리는 다른 프로세스 중 가장 이른 마감일을 할당하는 것이 중요하며, 그렇지 않으면 더 이른 마감일을 가진 프로세스가 이를 놓칠 수 있다.이는 임계 구역을 실행하는 프로세스가 완료되고 해당 임계 구역에서 종료하는 데 훨씬 더 오랜 시간이 걸려 공유 자원 해제를 지연시킬 경우 특히 중요하다. 그러나 프로세스는 더 이른 마감일을 가지고 있지만 임계 자원을 공유하지 않는 다른 프로세스에 의해 선점될 수 있다. 이 마감일 교환의 위험은 고정 우선 순위 선점 스케줄링을 사용할 때의 우선 순위 역전과 유사하다.
시스템이 과부하 상태일 때 데드라인을 지킬 수 없게 되는 프로세스를 예측할 수 없다 (데드라인과 과부하 발생 시간에 따라 달라진다). 이 단점은 실시간 시스템 설계에서 심각하다. 또한 이 알고리즘을 구현하는 것도 어렵고, 데드라인을 몇 바이트로 나타내려면 약간의 기술이 필요하다 (데드라인은 수 밀리초일 수도 있고 수백일 수도 있다). 이 때문에 EDF는 실제 산업용 실시간 시스템에서는 많이 사용되지 않는다.
멀티프로세싱 시스템에서는 EDF가 제대로 작동하지 않는다.
3. 예시
EDF 스케줄링의 예시로, 주기적 프로세스 3개를 다룬다. 각 프로세스의 실행 시간과 주기는 아래 표와 같다.
프로세스 | 실행 시간 | 주기 |
---|---|---|
P1 | 1 | 8 |
P2 | 2 | 5 |
P3 | 4 | 10 |
실행 시간과 주기의 단위는 같으며, 1단위 시간을 10밀리세컨드로 가정한다. 예를 들어 P1은 8단위 시간(80밀리세컨드)마다 시작하여 1단위 시간(10밀리세컨드) 동안 동작한다. CPU 사용률은 다음과 같이 계산할 수 있다.
:
임의 개수의 프로세스를 동작시킬 때 논리적인 CPU 사용률의 상한은 100%이므로, 이 시스템은 스케줄링 가능하다.
3. 1. 타이밍 다이어그램

타이밍 다이어그램에서 열은 시간이 오른쪽으로 증가하는 시간 슬라이스를 나타내며, 모든 프로세스는 시간 슬라이스 0에서 주기를 시작한다. 타이밍 다이어그램의 파란색과 흰색 음영이 번갈아 나타나는 것은 각 프로세스의 주기를 나타내며, 색상 변경 시 마감 시간이 적용된다.
EDF에 의해 스케줄링된 첫 번째 프로세스는 P2인데, 주기가 가장 짧아 가장 빠른 마감 시간을 갖기 때문이다. 마찬가지로, P2가 완료되면 P1이 스케줄링되고, 그 다음 P3이 스케줄링된다.
시간 슬라이스 5에서 P2와 P3 모두 시간 슬라이스 10 전에 완료해야 하는 동일한 마감 시간을 가지므로 EDF는 둘 중 하나를 스케줄링할 수 있다.
4. 마감일 교환 (Deadline Interchange)
EDF 스케줄링에서는 바람직하지 않은 마감일 교환이 발생할 수 있다. 프로세스는 임계 구역 내에서 공유 자원을 사용하여 더 이른 마감일을 가진 다른 프로세스를 선호하여 선점적으로 디스케줄링되는 것을 방지할 수 있다. 이 경우 스케줄러가 실행 중인 프로세스에 해당 자원을 기다리는 다른 프로세스 중 가장 이른 마감일을 할당하는 것이 중요하다. 그렇지 않으면 더 이른 마감일을 가진 프로세스가 이를 놓칠 수 있다.
이는 임계 구역을 실행하는 프로세스가 완료되고 해당 임계 구역에서 종료하는 데 훨씬 더 오랜 시간이 걸려 공유 자원 해제를 지연시킬 경우 특히 중요하다. 그러나 프로세스는 더 이른 마감일을 가지고 있지만 임계 자원을 공유하지 않는 다른 프로세스에 의해 선점될 수 있다. 이 마감일 교환의 위험은 고정 우선 순위 선점 스케줄링을 사용할 때의 우선 순위 역전과 유사하다.
준비 큐 내에서 마감일 검색 속도를 높이기 위해 큐 항목을 마감일에 따라 정렬할 수 있다. 새 프로세스 또는 주기적 프로세스에 새 마감일이 주어지면, 더 늦은 마감일을 가진 첫 번째 프로세스 앞에 삽입된다. 이러한 방식으로 가장 이른 마감일을 가진 프로세스가 항상 큐의 시작 부분에 있다.
5. 과밀 트래픽 분석 (Heavy Traffic Analysis)
최단 마감 우선 스케줄링 (EDF) 정책에 따른 이탈이 있는 단일 서버 큐의 동작에 대한 과밀 트래픽 분석에서, 프로세스는 마감 시간을 가지며 마감 시간이 경과될 때까지만 서비스된다. "이탈 작업"의 비율, 즉 마감 시간 경과로 인해 서비스되지 않은 잔여 작업으로 정의되는 것은 중요한 성능 지표이다.
6. 고정 우선순위 스케줄링과의 비교
일반적으로 고정 우선순위 선점형 스케줄링(FPS) 구현이 EDF와 같은 동적 우선순위 스케줄러보다 간단하다고 여겨진다. 그러나 고정 우선순위에서 최적 스케줄링의 최대 활용률을 비교할 때 (각 스레드의 우선순위는 율-단조 스케줄링에 의해 부여됨), EDF는 100%에 도달할 수 있는 반면, 율-단조 스케줄링의 이론적 최대값은 약 69%이다.[5] 주기적으로 실행해야 하는 프로세스의 데드라인은 해당 주기에 해당하며, EDF(최단 마감 우선 스케줄링)에 의한 CPU 사용률의 한계는 100%이다. 즉, EDF는 CPU 사용률의 합계가 100%를 넘지 않는 한 모든 데드라인을 지킬 수 있음을 보장한다. 따라서 속도 단조 스케줄링과 같은 고정 우선순위 스케줄링에 비해 EDF는 더 높은 부하 환경에서도 모든 데드라인을 지킬 수 있다.
그러나 시스템이 과부하 상태일 때 데드라인을 지킬 수 없게 되는 프로세스를 예측할 수 없다(데드라인과 과부하 발생 시간에 따라 달라진다). 이 단점은 실시간 시스템 설계에서 심각하다. 또한 이 알고리즘을 구현하는 것도 어렵고, 데드라인을 몇 바이트로 나타내려면 약간의 기술이 필요하다. 이 때문에 EDF는 실제 산업용 실시간 시스템에서는 많이 사용되지 않는다.
7. 커널 구현
EDF 스케줄링을 구현한 커널은 상업용 실시간 커널에서는 흔하지 않지만, EDF를 구현한 몇 가지 오픈 소스 및 실시간 커널이 존재한다.
- http://shark.sssup.it SHARK : 다양한 버전의 EDF 스케줄링 및 자원 예약 스케줄링 알고리즘을 구현한 SHaRK RTOS이다.
- https://web.archive.org/web/20090123013029/http://www.evidence.eu.com/content/view/27/254/ ERIKA Enterprise : OSEK API와 유사한 API를 사용하여 소형 마이크로컨트롤러에 최적화된 EDF 구현을 제공한다.
- http://www.barrywatson.se/?p=3 The Everyman Kernel : 사용자의 구성에 따라 EDF 또는 데드라인 단조 스케줄링을 구현한다.
- http://marte.unican.es/ MaRTE OS : Ada 응용 프로그램을 위한 런타임 역할을 하며 EDF를 포함한 광범위한 스케줄링 알고리즘을 구현한다.
- AQuoSA 프로젝트 : EDF 스케줄링 기능을 사용하여 프로세스 스케줄러를 개선하는 리눅스 커널 수정으로 구성된다. AQuoSA는 적절하게 설계된 접근 제어 모델을 통해 제어된 방식으로 시스템에서 권한이 없는 사용자에게 실시간 스케줄링 기능을 제공하는 몇 안 되는 프로젝트 중 하나이다.[6]
- 리눅스 커널 : 릴리스 3.14부터 사용할 수 있는 `SCHED DEADLINE`이라는 최단 데드라인 우선 구현을 가지고 있다.
- http://www.irmosproject.eu/ IRMOS : 유럽 프로젝트의 맥락에서 개발된 이 실시간 스케줄러는 리눅스 커널을 위한 멀티 프로세서 실시간 스케줄러이다. 결합된 EDF/FP 계층적 스케줄러를 특징으로 한다.
- Xen : EDF 스케줄러를 가지고 있다. http://man.cx/xm(1) man page 매뉴얼 페이지에서 확인할 수 있다.
- http://doc.cat-v.org/plan_9/ 벨 연구소의 Plan 9 OS : EDF와 데드라인 상속을 공유하는 자원을 결합한 "경량 실시간 스케줄링 프로토콜"인 EDFI를 통합한다.[7]
- https://www.rtems.org/ RTEMS : EDF 스케줄러는 버전 4.11에서 사용할 수 있다. https://web.archive.org/web/20160306154953/https://docs.rtems.org/doxygen/cpukit/html/group__ScoreSchedulerEDF.html RTEMS SuperCore
- https://www.litmus-rt.org/ Litmus-RT : 멀티 프로세서 실시간 스케줄링 및 동기화에 초점을 맞춘 리눅스 커널의 실시간 확장이다. 실시간 알고리즘 세트에는 분할 EDF, 전역 EDF 및 클러스터 EDF 스케줄러가 포함된다.
- https://github.com/apple-oss-distributions/xnu/blob/rel/xnu-6153/osfmk/kern/sched_clutch.md#scheduling-bucket-level XNU Clutch Scheduler : 2018년 현재, 애플의 XNU 커널은 응답성을 개선하기 위해 Clutch Scheduler에서 EDF 알고리즘을 구현한다.
참조
[1]
논문
Scheduling processes with release times, deadlines, precedence and exclusion relations
http://portal.acm.or[...]
[2]
서적
Hard Real-Time Computing Systems: Predictable Scheduling Algorithms and Applications
https://books.google[...]
Springer
[3]
서적
2011 IEEE International Conference on Emerging Technology and Factory Automation
https://ieeexplore.i[...]
[4]
논문
Heavy traffic analysis for EDF queues with reneging
http://www.math.cmu.[...]
[5]
서적
2010 16th IEEE Real-Time and Embedded Technology and Applications Symposium
2010-04
[6]
서적
2008 IEEE Real-Time and Embedded Technology and Applications Symposium
[7]
간행물
Lightweight EDF Scheduling with Deadline Inheritance
http://doc.cat-v.org[...]
본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.
문의하기 : help@durumis.com