Real-Time Systems & Deterministic Scheduling

1. Overview

실시간 시스템 및 결정론적 스케줄링(Real-Time Systems & Deterministic Scheduling, RTS)은 시스템의 '계산 결과가 정확한가'뿐만 아니라, **'그 결과가 도출되는 시점(Time)이 마감 시간(Deadline) 이내에 정확히 보장되는가'**가 시스템의 성공과 생존을 가르는 핵심 척도인 환경을 다룹니다.

자율 주행 자동차의 브레이크 제어, 심박 박동기 같은 의료 기기, 미사일 제어 시스템이나 초정밀 공장 로봇 암(Arm)에서 **'너무 늦은 정답(Late Answer)은 틀린 정답(Wrong Answer)보다 치명적인 재앙'**을 초래합니다. 학습자는 FreeRTOS, Zephyr, QNX 같은 실시간 운영체제(RTOS) 커널의 구조를 이해하고, RMS(Rate Monotonic Scheduling) 및 EDF(Earliest Deadline First)와 같은 결정론적(Deterministic) 스케줄링 이론을 통해 모든 태스크가 마감 시간을 어기지 않음을 수학적으로 증명(Schedulability Test)하는 기법을 익힙니다. 이를 통해 예측 불가능한 물리적/소프트웨어적 지연 시간(Jitter)을 최소화하여 시스템의 안전을 보장하는 고신뢰 아키텍처 설계 능력을 확보합니다.

2. Scope & Boundaries

In-Scope

• 결정론적 타이밍 기초 (Timeliness Foundations): Hard RT(생명/재산 직결) vs Soft RT(QoS 지향) 분류, 지터(Jitter) 물리적 분석, WCET(Worst-Case Execution Time, 최악 실행 시간) 정적/동적 측정.
• 실시간 스케줄링 이론 (Scheduling Theory): 주기적/비주기적 태스크 모델, 정적 우선순위 스케줄링(RMS, Rate Monotonic), 동적 우선순위 스케줄링(EDF, Earliest Deadline First), 스케줄링 가망성(Schedulability) 수학적 상한 검증.
• RTOS 커널 메커니즘 (RTOS Internals): 우선순위 기반 선점형 스케줄러(Preemptive Scheduler), 커널 틱(Tick) 인터럽트 제어, 우선순위 전도(Priority Inversion) 방어 프로토콜(상속/올림).
• 기능 안전 표준 검토 (Safety Standards): ISO 26262(자동차), DO-178C(항공) 등 하드 실시간 시스템 인증에 필요한 타이밍 톨러런스 요구사항 설계.

Out-of-Scope

• 범용 OS 처리량 최적화: Linux, Windows 등 일반 데스크톱 운영체제의 CFS(Completely Fair Scheduler) 등 전체 시스템 평균 처리량(Throughput) 중심 튜닝 → 03. Operating Systems & System Mechanics 영역으로 위임.
• 네트워크 지연 분석: 데이터 센터 통신망의 TCP/IP 프로토콜 지연, 라우터 큐잉 이론 분석 → 08. Networks & Communications 영역으로 위임.
• 클라우드 데이터 파이프라인 스케줄링: 하둡(Hadoop)이나 쿠버네티스(Kubernetes) 환경에서의 DAG(Directed Acyclic Graph) 기반 분산 작업 배치 → 07. System Architecture 영역으로 위임.

Boundaries

• RTS vs General OS Scheduling (03-02): 범용 OS의 스케줄링 알고리즘은 '모든 프로세스가 공평하게 실행'되고 '시스템 전체 평균 처리량'을 높이는 것을 목표로 합니다. 반면 RTS 스케줄링은 덜 중요한 태스크가 완전히 굶어 죽더라도(Starvation), **'생명과 직결된 최우선순위 태스크가 최악의 자원 경합 상황(WCET)에서도 반드시 마감 시간(Deadline)을 지켜냄'**을 수학적으로 증명하는 것을 절대 목표로 합니다.

3. Counterexample

• 단순 고속 하드웨어 성능 맹신 (Faster is better): 실시간 시스템 성능을 높이기 위해 "3GHz의 빠른 프로세서와 32GB RAM을 달았으니 데드라인을 놓칠 일은 없을 것"이라 추측하는 것은 대형 사고로 이어집니다. 속도가 아무리 빨라도 **공유 자원 경합에 의한 데드락이나 우선순위 전도(Priority Inversion)**가 발생하면 무한 대기에 빠질 수 있습니다. 저속 마이크로컨트롤러 환경에서라도 **스케줄링 가망성 테스트(Schedulability Test)**를 거쳐 모든 태스크가 마감 시간을 준수함을 수식으로 완벽히 증명할 수 있어야 합니다.
• 평균 실행 시간 기준 설계 (Average-case Fallacy): 기능 테스트를 1만 번 돌려 얻은 '평균 실행 시간'을 기준으로 마감 시간을 설정하는 것은 안티패턴입니다. 캐시 미스(Cache Miss), 인터럽트 폭풍(Interrupt Storm), 시스템 버스 포화 등이 동시에 겹치는 희박하지만 가능한 **최악의 시나리오(Worst-Case)**를 정적 분석 도구로 산출해 내야만 진정한 하드 리얼타임 검증을 할 수 있습니다.

4. Prerequisites

• 하드웨어-소프트웨어 인터페이스 물리 (Basic): 하드웨어 타이머 구조와 인터럽트(Interrupt) 처리 및 컨텍스트 스위칭 지연(Latency) 메커니즘을 알아야 RTOS 틱(Tick)을 이해할 수 있습니다. (02-05. HSI)
• 운영체제 프로세스 및 병행성 (Recommended): 뮤텍스(Mutex), 세마포어(Semaphore) 개념 및 데드락(Deadlock)에 대한 논리적 선행 지식이 필수적입니다. (03-02. CP)

5. Learning Map

6. Learning Topics

Basic

Core Topic 01: 실시간성 기초와 결정론 물리 (Real-Time Basics & Determinism)

• Why to Learn: 단순히 '속도가 빠른 시스템'과 '모든 작업이 지정된 시간 윈도우 안에 오차 없이 들어맞는 고신뢰 결정론 시스템'의 차이를 명확히 구분하기 위함입니다.
• What to Learn:
  • Concepts: 하드 실시간(Hard RT, 1ms 늦어도 치명적) vs 소프트 실시간(Soft RT, 영상 스트리밍 지연), 태스크 모델 특성(주기적 Periodic / 간헐적 Sporadic / 비주기적 Aperiodic).
  • Skills: 태스크의 최악 실행 시간(WCET, $C_i$), 주기($T_i$), 상대 데드라인($D_i$)의 상관 관계 도식화, 지터(Jitter) 노이즈 분석.
  • Tools: 타이밍 간트 차트(Gantt Chart), 하드웨어 오실로스코프 지터 파형 관측.
  • Trade-offs: 완벽한 타이밍 예측성(Determinism)을 위해 CPU 캐시나 파이프라인 비순차 실행을 강제 비활성화하여 잃게 되는 프로세서의 전반적인 처리 성능(Throughput) 간의 딜레마.
• How to Learn:
  • 1단계: 자동차 에어백 제어 컨트롤러(Hard-RT)와 차량 내비게이션 경로 탐색(Soft-RT)에서 각각 마감 시간이 100ms 지연되었을 때 시스템이 맞이할 물리적/비즈니스적 리스크 차이를 시나리오로 서술합니다.
  • 2단계: 범용 리눅스 커널과 FreeRTOS 보드에서 동일하게 1ms 간격으로 LED를 켜고 끄는 코드를 돌리고, 오실로스코프 파형을 통해 리눅스에서 Jitter(오차)가 어떻게 무작위로 치솟는지 원인을 분석합니다.
• Implement: 특정 센서 값을 읽어오도록 지시받았을 때, 지정된 마감 시간(예: 5ms) 초과(Deadline Miss)가 발생하면 즉시 안전 모드(Safe State)로 강제 진입하고 UART로 경보 로그를 남기는 파수꾼(Watchdog) 기반 펌웨어.

Recommended

Core Topic 02: 실시간 스케줄링 이론 수학 (Scheduling Theory: RMS & EDF)

• Why to Learn: 자원과 처리 능력이 극도로 제한된 환경에서, 시스템이 마감 시간을 어길 가능성이 0% 임을 배포 전에 수학적으로 철저히 증명하기 위해서입니다.
• What to Learn:
  • Concepts: RMS(Rate Monotonic Scheduling, 정적 우선순위), EDF(Earliest Deadline First, 동적 우선순위).
  • Skills: Liu & Layland의 가망성 상한계 공식(Schedulability Bound) 계산, CPU 이용률($U$) 산출.
  • Tools: 스케줄링 시뮬레이터 소프트웨어 (Cheddar, SimSo).
  • Trade-offs: 태스크 실행 주기가 짧을수록 높은 우선순위를 주는 RMS의 예측 용이성 및 설계 단순성 vs CPU 사용률 100%까지 꽉 채워 설계할 수 있는 EDF의 뛰어난 자원 활용률 및 런타임 우선순위 재계산 오버헤드.
• How to Learn:
  • 1단계: 3개의 주기적 태스크($T_1, T_2, T_3$)의 주기와 실행 시간이 주어졌을 때, RMS 이용률 상한 공식을 대입하여 CPU 병목 없이 안전하게 실행 가능할지 수기 계산 증명을 해봅니다.
  • 2단계: EDF 스케줄링 규칙 하에서 한 태스크가 주기보다 빨리 실행되어야 할 때, 동적으로 스케줄러가 우선순위를 뒤집어 배치하는 과정을 간트 차트로 그립니다.
• Implement: $N$개 태스크의 주기와 실행 시간 배열을 입력받아, CPU 이용률(Utilization)을 도출하고 RMS 스케줄링 가망성 테스트 상한치와 비교하여 'Schedulable' 혹은 'Miss Risk' 판별 결과를 리턴하는 파이썬 수학 스크립트 작성.

Practical

Core Topic 03: RTOS 커널 구조 해부와 실무 설계 (RTOS Internals & Mechanics)

• Why to Learn: 산업 표준으로 쓰이는 실제 RTOS 커널 소스 코드 레벨의 동작을 통제하여, 임베디드 기기 내 자원 경합을 막고 극한의 응답성을 조율하기 위함입니다.
• What to Learn:
  • Concepts: 커널 틱(Tick) 타이머 인터럽트, 준비/대기 큐(Ready/Blocked Queue) 자료구조, 우선순위 전도(Priority Inversion)와 해결책(상속/올림, PIP/PCP).
  • Skills: FreeRTOS 기반 태스크 생성(xTaskCreate), 블로킹 큐 통신(xQueueSend/Receive), 인터럽트 톱/바텀 하프(Top/Bottom Half) 분할 아키텍처 구현.
  • Tools: RTOS 시각화 프로파일러 (Percepio Tracealyzer, SEGGER SystemView).
  • Trade-offs: 커널 틱 주파수(Tick Frequency)를 10kHz 단위로 높여 마이크로초 단위 반응 속도를 챙기는 이득 vs 인터럽트 문맥 교환 오버헤드로 인해 실질적으로 태스크가 연산할 수 있는 유효 CPU 사이클이 소멸되는 부하 트레이드오프.
• How to Learn:
  • 1단계: 세마포어를 통해 하드웨어 모터를 제어하는 도중 저우선순위 태스크가 고우선순위 태스크를 하염없이 대기하게 만드는 '화성 탐사선 패스파인더 우선순위 전도 결함' 사례를 코드로 재현하고, RTOS의 우선순위 상속(Priority Inheritance) 프로토콜을 켜서 문제가 극복되는 과정을 관찰합니다.
  • 2단계: 데이터가 준비될 때까지 while 루프를 도는 폴링 코드와 RTOS 블로킹 API(xQueueReceive)를 호출해 Sleep 상태에 빠지는 코드의 CPU 점유율 차이를 프로파일러에서 막대그래프로 비교해 봅니다.
• Implement: 1. 온도 센서를 주기적으로 읽는 태스크(우선순위 中), 2. 화재 경보를 처리하는 비주기적 인터럽트 핸들러(우선순위 高), 3. 상태 LED 점멸(우선순위 低)로 구성된 FreeRTOS 기반 시스템 설계 모듈.

Advanced

Core Topic 04: 최악 실행 시간(WCET) 분석과 안전 규격 인증 (WCET & Safety Standards)

• Why to Learn: 항공기 비행 제어기나 자동차 브레이크 시스템처럼 단 한 번의 타이밍 오류도 묵과할 수 없는 극한 환경에서, 정적 물리 도구로 안전성을 증명하고 ISO 표준 인증(Certification) 마크를 획득하기 위해서입니다.
• What to Learn:
  • Concepts: WCET(Worst Case Execution Time), BCET(Best Case), 정적 분석(Static Analysis) vs 측정 기반 분석(Measurement-based Analysis)의 맹점.
  • Skills: 소스 코드 분기문(Branching)에 따른 최악의 제어 흐름 경로 도출, 캐시/파이프라인 레이턴시 불확실성을 고려한 여유값(Margin) 산정, ISO 26262/DO-178C 기능 안전 규격(Functional Safety) 대응.
  • Tools: 상용 정적 WCET 분석기 (AbsInt aiT, Bound-T), LLVM 프로파일 도구.
  • Trade-offs: 최고 등급 안전 표준(ASIL-D / DAL-A) 인증 통과를 위해 요구되는 막대한 정적 코드 분석 비용 및 런타임 제약 조건 vs 이를 포기하여 빠르게 시장에 출시하는 소프트 시스템 전개 기회 간의 기업 전략 차이.
• How to Learn:
  • 1단계: 버블 정렬(Bubble Sort)과 퀵 정렬(Quick Sort) 함수 코드에서 빅오 표기법 평균 성능이 아닌 물리적 최악 시나리오(모든 분기문을 타는 역순 정렬 케이스)의 CPU 명령 사이클 총합을 수기로 계산해 봅니다.
  • 2단계: 멀티코어 환경에서 칩의 내부 버스나 L2 캐시를 다른 코어와 공유할 때 발생하는 타이밍 간섭(Interference) 현상이 WCET를 어떻게 망가뜨리는지 캐시 분석 도구를 통해 시뮬레이션합니다.
• Implement: 소스 코드를 스캔하여 깊이 우선 탐색(DFS) 알고리즘으로 반복문(Loop)의 최대 깊이와 조건 분기문(Branch) 비용을 전부 누적한 뒤, 이론적으로 가능한 최악 실행 소요 사이클(WCET)을 경고로 출력해 내는 모의 정적 분석 파이썬 린터.

7. Terminology

8. References

Primary References

• [P1] CS2023 - ES/Real-time Systems — Scheduling and timing analysis.
• [P2] SWEBOK - Software Engineering Process — Quality and runtime constraints.

Secondary References

• [Real-Time Systems] Jane W. S. Liu — Classic academic textbook for scheduling.
• [Hard Real-Time Computing Systems] Giorgio C. Buttazzo — Predictable scheduling focus.

Industry References

• [FreeRTOS Reference Manual] — Real-world open source RTOS implementation.
• [ISO 26262 Standard] — Functional Safety for Automotive systems (Timing part).

9. Final Checklist

Primary Checklist

• 시스템의 마감 시간(Deadline)을 식별하고 위반 시의 물리적 리스크를 정량화할 수 있는가? (P1, P5)
• 특정 태스크 셋에 대해 RMS 기반의 가망성 테스트를 수행하여 스케줄링 가능 여부를 판별 가능한가? (P1)

Secondary Checklist

• 우선순위 역전 문제를 예방하기 위한 하드웨어/소프트웨어적 프로토콜을 시스템 설계에 적용했는가?
• '평균 성능'이 아닌 '최악의 케이스 지터'를 기준점으로 삼아 스케줄링 시뮬레이션을 수행했는가?

Industry Checklist

• WCET 분석을 통해 실무 수준의 코드 상한 시간을 도출하고 안전성을 최종 검토할 수 있는가? (SFIA)
• RTOS 커널의 스케줄러 틱 설정을 하드웨어 타이머 사양에 맞춰 최적화할 수 있는가?