실시간 스케줄링 (RM, EDF)

실시간 스케줄링 (RM, EDF)

실시간 시스템에서 태스크가 마감시한(Deadline)을 충족하도록 스케줄링하는 알고리즘으로, Rate Monotonic(RM)과 Earliest Deadline First(EDF)가 대표적

목적: 마감시한 보장, 예측 가능성, 실시간 시스템 요구사항 충족

특징: Deadline 기반, 주기적 태스크, 스케줄 가능성 분석

용어

• •주기(Period, T): 태스크 반복 주기
• •실행시간(Execution Time, C): 1회 실행에 필요한 CPU 시간
• •마감시한(Deadline, D): 실행 완료 기한
• •이용률(Utilization): U = C/T

Rate Monotonic (RM)

• •정적 우선순위: 주기가 짧을수록 높은 우선순위
• •최적성: 정적 우선순위 중 최적 (스케줄 가능하면 RM으로 가능)
• •스케줄 가능 조건 (충분조건): Σ(C_i/T_i) ≤ n(2^(1/n) - 1) ≈ 69.3% (n→∞)
• •장점: 단순, 오버헤드 낮음, 분석 용이
• •단점: 이용률 한계(~69.3%), EDF 대비 이용률 낮음

Earliest Deadline First (EDF)

• •동적 우선순위: 마감시한이 가장 가까운 태스크 우선
• •최적성: 단일 프로세서에서 최적 (스케줄 가능하면 EDF로 가능)
• •스케줄 가능 조건 (필요충분): Σ(C_i/T_i) ≤ 1 (100%)
• •장점: 최대 이용률(100%), 최적
• •단점: 오버헤드 높음(동적 우선순위), 과부하 시 예측 어려움

비교: RM(정적/단순/69%) vs EDF(동적/최적/100%)

적용사례: 자동차 ECU, 항공기 제어, 의료기기, RTOS

연관: 실시간 시스템, RTOS, 스케줄링, 마감시한