RT System의 핵심은 short-term 스케줄러
Fairness와 average response time의 최소화는 최우선이 아님 (데드라인 준수가 중요)
하드 실시간 작업
데드라인을 반드시 지켜야 하며, 위반 시 치명적 결과를 초래하는 작업
소프트 실시간 작업
데드라인 준수가 필수는 아니며, 위반되어도 작업 수행 자체는 의미 있는 작업
주기적 작업
일정한 주기마다 반복적으로 실행되는 작업 (주기 T마다 한 번, 정확히 T 단위 간격으로)
비주기적 작업
특정 기한 내에 시작되거나 완료되어야 하는 비반복성 작업
RT-OS의 특징
- 엄격한 우선순위
- 선점형 스케줄링
- Interrupt latency가 짧다
- 예측 가능한 타이밍
Interrupt latency
인터럽트가 발생한 후, 그 인터럽트를 인식하고 컨텍스트 스위칭 후
인터럽트 서비스 루틴이 수행되기 직전까지 걸린 시간
RT-OS requirements in five areas:
Determinism: 작업이 미리 정해진 시간 내에 수행될 수 있어야 한다
Responsiveness: 인터럽트 인지 후 이를 처리하기까지 걸리는 시간
User control: 사용자가 시스템 동작과 우선순위를 세밀하게 제어할 수 있어야 한다.
Reliability: 시스템이 장기간, 안정적으로 오류 없이 동작할 수 있는 능력.
Fail-soft operation: 일부 고장이 발생해도 핵심 기능은 계속 유지되어야 한다.
Determinism
OS가 고정된 시간 내에 작업을 예측 가능하게 수행할 수 있는 능력으로
인터럽트 응답 속도와 시스템 처리 용량에 의해 결정됨
Determinism은 인터럽트 레이턴시(인터럽트를 인지하기 걸리는 시간)를 다룸
(인터럽트 발생 ~ 인터럽트 서비스 루틴 시작 전)까지 걸리는 시간
non-RT-OS에서는 지연 시간 ≤ 1초
RT-OS에서는 지연 시간 ≤ 1밀리초
Responsiveness
인터럽트를 처리하기까지 걸리는 시간
Deteminism + Responsiveness = Response time to externel events
다음이 포함됨:
- 인터럽트를 감지하고 ISR을 시작하는 데 걸리는 시간(인터럽트 레이턴시)
- ISR을 수행 시간
- 인터럽트 중첩(interrupt nesting)으로 인한 지연
(인터럽트 중첩으로 더 높은 우선순위 인터럽트가 중간에 실행되면서 중간에 딜레이된 시간까지 포함)
User Control
우선순위 별 세밀한 유저 컨트롤을 제공
RTOS에서 더 폭넓고 세밀하게 제공한다
사용자는 hard task와 soft task를 구분하고 각 범주 내에서
priority에 대해 user fine-grained control을 부여한다 (세밀하게 proiortity 명시)
다음 특성을 지정:
paging 또는 process swapping 사용 여부
항상 main memory에 상주하는 프로세스
사용할 디스크 전송 알고리즘
각 우선순위 대역에 있는 프로세스가 가지는 권한
Reliability
시스템이 장기간, 안정적으로 오류 없이 동작할 수 있는 능력
비실시간 시스템에서는 단순한 재부팅으로 해결될 수 있음
실시간 시스템은 성능 저하나 손실이 치명적인 결과로 이어질 수 있음
Fail-Soft Operation
실패가 발생하더라도 최대한 기능과 데이터를 보존하는 방식으로 동작
실시간 시스템은 corrective action를 시도한 후, 서비스 수준이 다소 낮아지더라도 동작을 계속해야 함
시스템 종료가 불가피할 경우, 데이터 일관성을 유지하려는 시도가 이루어져야 한다
Fail-Soft Operation의 중요한 측면은 Stability
실시간 시스템이 안정적이라는 것은, 일부 덜 중요한 작업의 데드라인은 항상 지켜지지 않더라도
가장 중요한 고-우선순위 작업들의 데드라인은 지켜저야 한다
RR preemptive scheduler
실시간 태스크는 다음 타임 슬라이스를 기다리기 위해 준비 큐에 추가,
실시간 어플리케이션에 적합하지 않음
Priority-driven non-preempitive scheduler
Ready 상태인 실시간 태스크는 현재 프로세스가 block되거나 종료될 때 스케줄됨
실시간 어플리케이션에 적합하지 않음
Priority-driven non-preempitive scheduler on preemption points
주기적 선점 포인트에서 대기 중인 더 높은 우선순위 태스크가 있으면 선점당함
(타임 인터럽트 발생시켜서, 더 높은 우선순위 있나 체크하고 있으면 그 작업으로 넘어간다)
Soft 실시간 어플리케이션에 적절 (Hard X, Soft O)
(어느 정도 대기 시간이 존재하고, 최악의 경우 선점 지점 주기만큼 기다려야 하므로 경성 실시간에는 적합하지 않다)
Immediate preempitive scheduler
시스템이 critical-code lockout 구간에 있지 않다면, 인터럽트에 거의 즉시 반응
스케줄링 지연은 100μs 이하
실시간 어플리케이션에 적절 (Hard O, Soft O)
1. 시스템이 schedulability analysis를 수행하는지 여부:
수행한다면 static하게 하는지 dynamic하게 하는 지
static: 스케줄링 전 오프라인 상태에서 이미 정해진 값들로 분석
dynamic: 수행 중에 새로운 태스크 들어오면 가능성 분석해서 새로 스케줄링
2. 분석 결과가 스케줄이나 계획을 생성하는지:
어떤 것은 분석, 표를 제시, 어떤 것은 우선순위만 제시
RT 스케줄링 알고리즘의 네 가지 접근 방식
Static table-driven: 주기적 작업의 정적 분석을 통해 실행 스케줄을 사전에 생성하는 방식.
Static priority-driven preemptive: 정적 분석을 통해 우선순위를 부여하고, 선점 기반 스케줄링을 수행하는 방식
Dynamic planning-based: 실행 시간에 스케줄을 분석하여, 기존 스케줄을 조정하여 새로운 스케줄을 생성하는 방식.
Dynamic best effort: 스케줄 분석 없이 도착한 태스크에 우선순위를 부여하며, 가능한 데드라인을 맞추려 시도하는 방식.
Static table-driven
feasibility에 대한 정적 분석을 수행함
실행 시간에 태스크가 언제 실행을 시작해야 하는지를 결정하는 스케줄을 생성
Static priority-driven preemptive
정적 분석은 수행되지만 스케줄 자체는 작성되지 않음
분석 결과를 기반으로 태스크에 우선순위를 부여하여, 이후 전통적인 우선순위 기반 선점 스케줄러처럼 동작
Dynamic planning-based
실행 시작 전 오프라인이 아니라 실행 시간에 feasibility가 결정됨
결과로 태스크를 언제 디스패치할지를 나타내는 스케줄을 생성
Dynamic best effort
feasibility 분석이 수행되지 않음
시스템은 모든 기한을 맞추려고 시도하며, 기한을 놓친 태스크는 중단시킴
Static table-driven scheduling
주기적 태스크에 적용 가능
입력으로는 주기적 도착 시간, 실행 시간, 주기적 마감 기한, 우선순위
예측 가능하지만 유연성이 떨어짐(조금이라도 변경되면 전체 스케줄을 다시 작성해야 한다)
예: earliest-deadline-first (데드라인 가장 적게 남은 애를 가장 먼저 스케줄링) 또는 다른 periodic deadline techniques
Static priority-driven preemptive scheduling
우선순위 기반 선점 스케줄링 메커니즘을 사용
각 태스크의 시간 제약을 기준으로 우선순위를 부여함
예: 태스크의 주기 길이에 따라 정적 우선순위를 부여하는 rate-monotonic algorithm
Dynamic planning-based scheduling
태스크가 도착한 후 실행이 시작되기 전에, 이전에 스케줄된 태스크들과 새로 도착한 태스크를 포함하는 스케줄을 생성하려 시도
(1) 새로 도착한 태스크가 deadline을 만족하면서, (2) 현재 스케줄된 어떤 태스크도 deadline을 놓치지 않도록 스케줄이 가능한 경우에만, 스케줄을 수정함 (그렇지 않으면 새로운 애를 받아들이지 않는다)
Dynamic best effort scheduling
태스크가 도착하면, 태스크의 특성에 따라 priority를 부여
예: Earliest-deadline scheduling
일반적으로 태스크는 비주기적이기 때문에 정적인 스케줄 분석은 불가능함
장점: 구현이 쉬움
단점: 기한 제약을 충족할 수 있을지 여부를 알 수 없다
RT-OS의 목표는
Interrupt handling과 task dispatching를 빠르게 수행하여
RT 태스크를 가능한 한 빠르게 시작하는 것
단순 속도보다, 태스크를 가장 가치 있는 시점에 완료(시작)하는 데 중점
priority만으로는 태스크를 가장 가치 있는 시점에 완료(시작)할 수 없음
(priority뿐만 아니라 더 많은 정보를 이용하여, 좀 더 중요한 시점에 스케줄링해서 데드라인을 맞추겠다는 뜻)
Deadline Scheduling
Deadline Scheduling을 위해 필요한 정보들
Ready time: 실행되기까지 준비 시간
Starting deadline: 태스크가 시작해야 하는 시간
Completion deadline: 태스크가 완료되어야 하는 시간
Processing time: 태스크를 완료하는 데 필요한 실행 시간
Resource requirements: 실행 중 필요한 자원의 집합
Priority:
태스크의 상대적 중요도
Hard real-time 태스크는 “절대” 우선순위를 가질 수 있음
Subtask scheduler:
태스크는 mandatory 서브태스크와 optional 서브태스크로 분해될 수 있음
하드 deadline을 가진 것은 필수 서브태스크뿐
A로부터 데이터 수집 deadline은 매 20ms마다 맞춰야 하고, B로부터는 매 50ms마다 맞춰야 함
A의 데이터를 처리하는 데 10ms, B의 데이터를 처리하는 데 25ms가 소요
(1) Earliest deadline
ready인 task가 있으면 스케줄하여 완료까지 실행함 (한 번 수행되면 완료될 때까지 수행)
ready인 task가 여러 개일 경우, 가장 deadline이 임박한 task 를 스케줄
위의 경우에서 A는 10에 들어와서 30까지 쭉 수행됨, B는 들어오자마자 수행되어야하지만
A가 수행되고 있기 때문에, B는 수행되지 못한다
(2) Earliest deadline with unforced idle times
deadline이 가장 이른 eligible task를 항상 스케줄하고 해당 task를 완료까지 실행
(starting deadline을 이용)
eligible task가 준비되지 않은 경우, ready인 task가 있더라도 프로세서는 idle 상태를 유지할 수 있음
(적합한 task 없다면(꼭 수행해야 하는 task 없다면), 프로세서를 idle하게 만듬)
프로세서가 최대 효율로 사용되지는 않지만, 모든 스케줄링은 가능하다
Rate Monotonic Scheduling
태스크의 주기가 짧을수록 높은 우선순위를 부여하는 static priority-driven preemptive scheduling algorithm
task period T = 한 태스크 인스턴스가 도착한 시점과 다음 인스턴스가 도착하는 시점 사이의 시간 간격
task rate R (in hertz) = 1/T
task execution time = C
cpu-utilization U = C / T
실시간 만족 cpu-utilization <= 1 (cpu 최대 성능 100%)
1 초과 시, 실시간 불가능하므로 task 수 조절 필요
static priority-driven preemptive scheduling algorithm이기 때문에
우선순위 밀리면 선점됨 (주기로 우선순위 세팅 후에, 전통적인 선점 알고리즘처럼)
Priority Inversion
우선순위가 가장 높은 태스크는 자원을 점유하고 있는 태스크를 기다리고,
자원을 점유하고 있는 태스크는 자신보다 우선순위가 높은 다른 태스크를 기다리고 있어서,
우선순위가 가장 높은 태스크가 관련도 없는 자신보다 우선순위가 낮은, 다른 태스크를 기다리고 있는 현상
Priority Inheritance
자원을 점유하는 낮은 우선순위 태스크가
자원을 기다리는 높은 우선순위 태스크의 블락과 동시에
우선순위를 일시적으로 상속받아 우선순위 역전을 해결하는 기법
(자원의 release와 동시에 우선순위를 돌려받게됨)
(따라서 마지막에 T3 -> T1 -> T2로 진행하게 된다)