실시간 시스템 스케줄링: EDF·RM·데드라인 기반 알고리즘

실시간 시스템에서는 입력을 처리해 출력하는 데 걸리는 시간이 기능적 정합성에 직접 영향을 준다. 따라서 스케줄러는 작업을 실행하는 순서뿐 아니라, 각 태스크가 정해진 데드라인 안에 끝날 수 있는지를 관리해야 한다. 여기서는 Real-Time Scheduling과 Deadline-Driven Algorithms를 중심으로 태스크 모델, 분석, 동기화, 과부하 대응을 정리한다.

태스크의 시간 조건을 먼저 모델링한다

주기 태스크는 period T, 희소 태스크는 최소 도착 간격 T, 비주기 태스크는 정해지지 않은 도착 시점을 가진다. 태스크 τ_i는 보통 다음 값으로 표현한다.

• C_i: WCET
• T_i: 주기
• D_i: 데드라인
• r_i: 릴리스 시점

기본 이론은 단일 코어, 선점 가능, 독립 태스크, D_i ≤ T_i를 가정할 때 적용하기 쉽다. 실제 시스템에는 Jitter, 응답시간 변동, 컨텍스트 스위치 비용이 들어온다.

데드라인은 릴리스 시점을 기준으로 한 절대 데드라인과, 릴리스 후 허용 시간을 뜻하는 상대 데드라인으로 나뉜다. Deadline-Driven 방식은 절대 데드라인을 스케줄링 키로 사용한다.

실시간 요구 수준도 정책 선택에 영향을 준다. Hard RT는 미스를 허용하지 않으며, Firm RT와 Soft RT는 미스가 발생했을 때 성능 저하를 허용한다. 과부하 상황에서 어떤 태스크를 보호하거나 포기할지는 이 등급에 따라 달라진다.

우선순위를 고정할지 데드라인에 따라 바꿀지

고정 우선순위 스케줄링(FPS)에는 Rate Monotonic(RM)과 Deadline Monotonic(DM)이 있다. RM은 T가 짧을수록 높은 우선순위를 부여하고, DM은 D가 짧을수록 우선순위를 높인다. 이 방식은 응답시간 분석(RTA)으로 검증할 수 있다.

동적 우선순위 스케줄링(DPS)에는 Earliest Deadline First(EDF)와 Least Laxity First(LLF)가 있다. EDF는 절대 데드라인이 가장 이른 태스크를 먼저 선택한다. 단일 코어, 독립 태스크, D_i=T_i 조건에서는 활용도 100%를 달성한다. LLF는 이론상 EDF 수준이지만 라크시티 변화로 선점이 빈번해질 수 있다.

알고리즘	성능(활용도/오버헤드)	확장성(멀티코어)	일관성(예측가능성)	안정성(과부하)	운영 편의
RM (Fixed)	활용도 충분조건 ≤ ~69%, 오버헤드 낮음	파티셔닝 쉬움, 글로벌 확장 어려움	높음, RTA 성숙	과부하 시 고우선 태스크 보호	구현 단순, 튜닝 용이
DM (Fixed)	D≤T 모델에 유리, RM과 유사	파티셔닝 쉬움	높음	유사	구현 단순
EDF (Dynamic)	단일 코어 U≤1 필요충분, 힙 관리 오버헤드	글로벌/파티션 모두 연구 많음	높음(이상적 가정), 힙 변동성 존재	과부하 시 스래싱 가능	우선순위 관리 자동, 분석 간결
LLF (Dynamic)	이론상 EDF 수준, 선점 빈번	확장성 낮음(오버헤드 큼)	낮음(라크시티 변동)	불안정	운영 부적합(교육/연구용)

실제 성능은 타이머 해상도, 컨텍스트 스위치, 캐시와 락 비용에 따라 달라진다.

스케줄러는 큐와 시간 정보를 함께 관리한다

EDF의 준비 큐는 절대 데드라인을 키로 하는 최소 힙으로 구성할 수 있다. FPS는 우선순위 큐를 사용한다. 더 이른 데드라인 또는 더 높은 우선순위의 태스크가 도착하면 실행 중인 태스크를 선점할 수 있으며, 이때 컨텍스트 스위치 비용도 분석에 포함해야 한다.

시간 관리는 고해상도 타이머, 필요 시 타임슬라이스, 실행·대기 시간을 기록하는 타임어카운팅으로 구성한다. WCET는 프로파일과 분포 상한을 이용하는 측정 기반 방식, 경로 탐색과 캐시·분기 모델을 이용하는 분석 기반 방식으로 산정할 수 있다. 어느 방식이든 보수적 상계를 사용한다.

공유자원에서는 임계구역 시간과 블로킹 상한값 B_i가 필요하다. 우선순위 상속(PIP), 우선순위 천장(PCP, SRP)은 우선순위 역전을 제한하는 데 사용한다. PCP와 SRP는 데드라인·우선순위 단조성을 유지하고, 블로킹 상한을 제공하며, 데드락을 예방한다. 멀티코어에서는 글로벌 락 대신 파티션 자원을 두거나 MPCP, OMLP 같은 RT 락 프로토콜을 검토할 수 있다.

스케줄 가능 여부는 활용도와 응답시간으로 검증한다

활용도 검사에서는 U=Σ(C_i/T_i)를 사용한다.

• RM은 U=Σ(C_i/T_i) ≤ n(2^(1/n)−1)이고, n→∞일 때 ≈ 0.693이면 충분조건이 된다.
• EDF는 독립·선점·D_i=T_i 조건에서 U=Σ(C_i/T_i) ≤ 1이면 필요충분조건이다.

FPS의 응답시간 분석은 다음 식으로 표현한다.

R_i* = C_i + B_i + Σ_{j∈hp(i)} ceil(R_i/T_j)·C_j

고정점 반복 계산 결과 R_i ≤ D_i이면 해당 태스크는 스케줄러블하다. B_i는 자원 프로토콜 아래에서 상계화한다.

새 태스크를 추가할 때는 U 또는 RTA를 기준으로 Admission Control을 수행한다. 런타임 과부하가 발생하면 skip-next 또는 skip-k, 가치 기반 스케줄링(value-density), 고장·비상 모드 전환, 해상도 저하나 주기 증가 같은 QoS 저하 정책을 사용할 수 있다.

절대 데드라인으로 디스패치하는 흐름

⤢✕

제어·통신·미디어 파이프라인에서의 선택

산업 제어와 로보틱스에서는 주기 제어루프(1 kHz 등)에 RM 또는 DM을 적용하고, 고정 우선순위와 SRP로 블로킹을 제어할 수 있다. 장애 모드에서는 제어주기를 낮추는 방식의 모드 전환도 설계 대상이다.

자율주행과 ADAS에서는 인지-계획-제어 파이프라인에 EDF를 적용해 프레임 데드라인을 관리한다. ISO 26262 아래에서는 WCET를 보수적으로 잡고, 미스가 발생했을 때 페일-오퍼레이셔널 정책을 둔다.

통신과 네트워킹에서는 패킷 스케줄러에 EDF와 가치 기반 방식을 결합해 지연 민감 큐를 우선 처리할 수 있다. 소프트 RT 트래픽은 skip-over로 혼잡을 완화한다. 임베디드 멀티미디어에서는 오디오·비디오 디코드 파이프라인에 EDF를 적용해 버퍼 언더런을 막고, Aperiodic 요청은 Sporadic Server 또는 Deferrable Server로 통합한다.

분석 결과가 런타임까지 이어지게 한다

태스크마다 WCET C_i를 산정하고 T_i, D_i를 정의하며 Jitter와 CS 길이를 측정한다. 공유자원을 식별한 뒤 임계구역 경로와 최장 구간을 기록한다.

EDF를 고르면 Σ(C_i/T_i) ≤ 1을 확인하고, D_i ≠ T_i라면 유효 간섭 분석을 고려한다. RM 또는 DM을 고르면 B_i를 포함한 RTA 반복 계산으로 모든 i에 대해 R_i ≤ D_i인지 검증한다.

런타임에서는 타이머 해상도와 선점·큐 자료구조(힙/비트맵)를 정하고, skip-k, 가치 기반 드롭, 모드 전환을 포함한 미스 핸들러 정책을 정의한다. 릴리스, 디스패치, 선점, 락 대기, 완료 시점은 타임스탬프로 남긴다. HIL/SiL 테스트에서는 WCET와 지터를 검증하고, 과부하 인젝션 테스트도 수행한다.

단일 코어 EDF 시뮬레이션

전제조건: Python 3.10+, 선점 오버헤드 0 가정, D_i = T_i.

# Python 3.10+, EDF discrete-time simulator (time unit = 1)
from heapq import heappush, heappop

class Task:
    def __init__(self, name, C, T, D=None):
        self.name, self.C, self.T = name, C, T
        self.D = D if D is not None else T

def edf_schedule(tasks, horizon=50):
    time = 0
    ready = []  # (abs_deadline, job_id, name, remaining)
    releases = {t.name: 0 for t in tasks}
    job_seq = 0
    timeline = []

    while time < horizon:
        # release jobs
        for t in tasks:
            if time == releases[t.name]:
                heappush(ready, (time + t.D, job_seq, t.name, t.C, t.T, t.D))
                job_seq += 1
                releases[t.name] += t.T

        if ready:
            dl, jid, name, rem, T, D = heappop(ready)
            # execute 1 unit
            rem -= 1
            timeline.append((time, name))
            time += 1
            if rem > 0:
                heappush(ready, (dl, jid, name, rem, T, D))
            else:
                if time > dl:
                    print(f"Deadline miss: {name} at t={time}, dl={dl}")
        else:
            timeline.append((time, "idle"))
            time += 1

    return timeline

if __name__ == "__main__":
    tasks = [Task("A", C=1, T=4), Task("B", C=2, T=5), Task("C", C=1, T=10)]
    U = sum(t.C / t.T for t in tasks)
    print(f"Utilization = {U:.3f} (≤ 1 ⇒ EDF schedulable ideal)")
    tl = edf_schedule(tasks, horizon=40)
    # Compact print
    print("Timeline:", " ".join(f"{t}:{n}" for t, n in tl))

U ≤ 1이면 이상적 가정 아래 EDF 스케줄러블하다. D_i ≠ T_i이거나 자원을 공유하고 선점 비용이 존재하면 추가 분석이 필요하다.

EDF는 동일 태스크 집합에서 RM 대비 최대 44%p 높은 활용도 상한(0.693→1.0)을 달성할 수 있다. RTA와 PCP, SRP를 적용하면 블로킹 상한을 보장하고 최악 응답시간 경계를 확보할 수 있다. Sporadic Server와 Deferrable Server로 비주기 요청을 통합하면 평균 응답시간 2040% 개선 사례 다수(시스템 의존)가 있다.