Real-Time OS

Real-Time System

실시간 시스템은 논리적 정확성과 시간적 정확성을 충족해야 한다.

• 논리적 정확성(Logical Correctness): 올바른 결과를 생성해야 한다.
  • 매우 당연한 조건
• 시간적 정확성(Temporal Correctness): 결과를 적시에 제공해야 한다.

Real-Time System의 예시

• 에어백 시스템: Hard Deadline을 지켜야 하는 경우는 반드시 사전 분석과 설계가 필요하다.
• cf) 인포테인먼트 시스템과 같은 Soft Deadline은 약간의 지연이 허용된다.

Scheduling

Task and Job

• Task: 반복적으로 실행되는 작업 (프로그램 또는 함수)
• Job: 특정 태스크의 실행 인스턴스, task 각각
  • Task A의 Job이 반복적으로 실행된다.
• Task의 시간 속성
  • Release Time: Job이 실행 가능한 시점
    • Job은 release 이후에 시작된다.
    • Periodic task: Release 간격이 일정할 때
    • Sporadic task: Release 사이에 최소 간격이 지켜질 때 (엔진의 리듬 RPM)
    • Aperiodic task: Release 패턴에 규칙이 없을 때
  • Deadline: Job이 완료되어야 하는 시점
    • Job은 deadline 이전에 종료되어야 한다.
    • Implicit deadline: Deadline이 주기와 맞아 떨어지는 것
    • Constrained deadline: Deadline이 주기보다 짧은 것
    • Arbitrary deadline: Deadline이 period보다 긴 것으로 Job 두개 이상 몰릴 수 있어서 일반적으로 사용하지 않는다.
    • Hard deadlines: Deadline을 절대 어기면 안되는 경우
    • Soft deadlines: Deadline을 어기면 손해가 있지만 어느 정도 허용되는 경우
  • Execution Time: Job이 실행되는 데 필요한 시간
    • 각 job의 실행시간은 if-else, 캐시 등으로 인해 job의 실행때마다 변할 수 있다.
    • 각 task의 실행시간은 확률 분포로 주어지며 고정된 상수로 정의할 수 없다.
    • Worst-Case Execution Time (WCET): 시스템 설계를 위한 가장 중요한 기준으로, Upper Bound를 추측하여 Task 실행시간의 분포를 추정한다.
    • WCET는 upper bound보다 작아야 한다.
• Periodic Task Model
  • $N$ periodic task: $\{T_1, T_2, \cdots T_N\}$
  • 각 task $T_i$는 period, WECT, relative deadline으로 표현된다.
    • $p_i,e_i,d_i$
    • 암시적 deadline task인 경우 $p_i,e_i$

RM Optimal Scheduling

한 개의 CPU로 효율적인 스케줄링이 필요한 경우

• 우선순위 기반 스케줄링(Priority-Driven Scheduling)
  • 가장 많이 사용되는 스케줄링 방법
  • 각 Task에 우선순위를 부여하고, 높은 우선순위의 Job부터 실행
  • 스케줄링이 발생하는 주요 시점
    • 새로운 Job이 활성화될 때 (release, activate)
    • Job이 종료될 때 (completions, terminate)
    • Job이 선점될 때
• 고정 우선순위 할당(Fixed-Priority Assignment)
  • RM (Rate Monotonic): 주기가 짧은 태스크에 높은 우선순위를 부여
  • RM은 최적의 우선순위 할당 방식으로 증명되었다.
  • 단, 주기적 태스크와 암묵적 기한(Implicit Deadline)이라는 조건이 있다.
• Optimal Priority Assignment
  • Rate Monotonic: 최적의 우선순위 할당 방법
    • 짧은 주기 Task에 높은 우선순위를 부여한다.
    • Periodic Task이고 Implicit Deadline일 때 RM으로 스케줄링 못하는 워크로드는 다른 방법으로도 안 된다.

Scheduling Analysis

• Critical Instant Theorem
  • 최악의 지연 시나리오는 모든 Task가 같은 시점에 release될 때 발생한다.
  • 모든 Task가 동시에 release 되면 각 Task의 첫번째 Job이 가장 오래 기다려야 한다.
• Response Time
  • Release부터 끝날때까지의 시간
  • Job마다 다를 수 있다.
  • WCRT (Worst-Case Response Time): 가장 긴 response time
    • WCRT는 무조건 critical instant에서 발생한다.
• Schedulability 분석
  • 각 Task의 WCRT를 계산했을 때 주기보다 짧다면 scheduling 가능하다.
  • WCRT 대신 Utilization Bound를 사용할 수 있다.
  • Utilization: $U=\sum_{1\le i\le N}\frac{e_i}{p_i}$
  • Utilization이 Utilization Bound(69.3%) 이하이면 schedulable
  • RM Utilization Bound: $U_{RM}(n)=n(2^{\frac{1}{n}}-1)$
    • 계산에는 $n$만 필요하고 주기와 실행 시간에 독립적이다.
• 종합적인 Schedulability 분석 방법
  1. Utilization bound check
  2. 아니면 WCRT 분석
  3. 아니면 Not Schedulable