기본 실시간 스케줄링 알고리즘 복습

실시간 스케줄링의 개요

실시간 시스템에서는 작업이 주어진 시간 내에 완료되는 것이 중요하다. 이는 하드 실시간 시스템과 소프트 실시간 시스템으로 나뉘며, 하드 실시간 시스템에서는 마감 시간의 준수가 필수적이고 소프트 실시간 시스템에서는 마감 시간의 준수가 중요하지만 필수적이지 않는다.

실시간 스케줄링 알고리즘은 시스템의 타이밍 요구사항을 충족시키기 위해 사용된다. 주요 알고리즘으로는 Rate Monotonic Scheduling (RMS)와 Earliest Deadline First (EDF)가 있다. 이 섹션에서는 이러한 기본 실시간 스케줄링 알고리즘에 대해 복습한다.

Rate Monotonic Scheduling (RMS)

개요

RMS는 주기적 작업들을 고정 우선순위 방식으로 스케줄링하는 알고리즘이다. 각 작업은 그 주기에 따라 우선순위가 정해지며, 주기가 짧을수록 높은 우선순위를 가진다.

RMS의 기본 개념

주기 (Period, $T_i$ ): 작업 $i$ 가 반복되는 주기이다.
실행 시간 (Execution Time, $C_i$ ): 작업 $i$ 를 완료하는 데 필요한 시간이다.
우선순위 (Priority): 주기가 짧을수록 높은 우선순위를 갖는다.

RMS 스케줄링 조건

RMS에서 주어진 작업 집합이 스케줄 가능하려면 다음과 같은 조건을 만족해야 한다:

$U = \sum_{i=1}^{n} \frac{C_i}{T_i} \leq n(2^{\frac{1}{n}} - 1)$

여기서 $U$ 는 시스템의 총 CPU 이용률이다.

Earliest Deadline First (EDF)

개요

EDF는 동적 우선순위 스케줄링 알고리즘으로, 가장 가까운 마감 시간(Deadline)을 가진 작업에 우선순위를 부여한다. 주기가 동일하지 않은 작업들에도 적용될 수 있으며, RMS보다 더 높은 CPU 이용률을 지원한다.

EDF의 기본 개념

마감 시간 (Deadline, $D_i$ ): 작업 $i$ 가 반드시 완료되어야 하는 시간이다.
우선순위 (Priority): 마감 시간이 가까울수록 높은 우선순위를 갖는다.

EDF 스케줄링 조건

EDF에서 주어진 작업 집합이 스케줄 가능하려면 다음과 같은 조건을 만족해야 한다:

$U = \sum_{i=1}^{n} \frac{C_i}{T_i} \leq 1$

여기서 $U$ 는 시스템의 총 CPU 이용률이다.

RMS와 EDF 비교

우선순위 결정 방식:
RMS: 고정 우선순위 (Fixed Priority) 방식
EDF: 동적 우선순위 (Dynamic Priority) 방식
스케줄 가능성:
RMS: 특정 조건을 만족해야 함 (CPU 이용률이 낮은 경우 적합)
EDF: 더 높은 CPU 이용률을 지원 (이론적으로 $U \leq 1$ 까지 스케줄 가능)

스케줄링 알고리즘의 실제 적용

RMS의 실제 적용

RMS는 주로 주기적 작업이 많고, 각 작업의 주기가 고정된 시스템에 적합한다. 예를 들어, 자동차의 엔진 제어 시스템이나 항공기 제어 시스템 등에서 RMS가 효과적으로 사용될 수 있다. 이러한 시스템에서는 주기적인 센서 데이터 수집, 신호 처리, 제어 명령 생성 등의 작업이 반복적으로 발생하므로 RMS의 고정 우선순위 방식이 유용하다.

EDF의 실제 적용

EDF는 주기적 작업뿐만 아니라 비주기적 작업이 혼합된 시스템에서도 사용될 수 있다. 예를 들어, 멀티미디어 시스템이나 네트워크 데이터 패킷 처리 시스템 등에서 EDF가 효과적으로 사용될 수 있다. 이러한 시스템에서는 작업의 마감 시간이 자주 변경되므로, 마감 시간에 따라 동적으로 우선순위를 부여하는 EDF가 유리한다.

RMS와 EDF의 한계 및 개선 방안

RMS의 한계

우선순위 역전 (Priority Inversion): 낮은 우선순위의 작업이 높은 우선순위의 작업보다 먼저 실행되는 상황이 발생할 수 있다.
비주기적 작업 처리: 비주기적 작업을 처리하는 데 제한적이다.

EDF의 한계

오버헤드 (Overhead): 동적 우선순위 부여로 인해 오버헤드가 발생할 수 있다.
스케줄링 복잡도: 주기적 작업과 비주기적 작업이 혼재된 시스템에서는 스케줄링 복잡도가 증가할 수 있다.

개선 방안

Priority Ceiling Protocol (PCP): 우선순위 역전 문제를 해결하기 위해 사용된다. 임계 구역(critical section)에서 높은 우선순위를 부여하여 우선순위 역전을 방지한다.
Bandwidth Reservation: 비주기적 작업에 대해 일정한 CPU 시간을 예약하여 안정적인 실시간 성능을 보장한다.
Mixed-Criticality Scheduling: 작업의 중요도에 따라 다른 스케줄링 정책을 적용하여 시스템의 성능을 최적화한다.

실시간 스케줄링 알고리즘인 RMS와 EDF는 각각의 장단점이 있으며, 시스템의 특성에 따라 적절한 알고리즘을 선택하여 적용해야 한다. RMS는 주기적 작업에 적합하며, EDF는 동적 우선순위 부여가 필요한 시스템에 유리한다. 또한, 우선순위 역전 문제와 같은 한계점을 보완하기 위한 다양한 개선 방안들이 존재한다.

이번 장에서는 기본적인 실시간 스케줄링 알고리즘에 대해 복습하고, 그 실제 적용 사례 및 한계점에 대해 알아보았다. 다음 장에서는 Preempt-RT 패치에 대해 자세히 다루겠다.