문서요약 - 실시간 운영체제 소개: 스케쥴링 이론 by Mercer

제목: 실시간 운영체제 소개: 스케쥴링 이론(An Introduction to Real-Time Operating Systems: Scheduling Theory)

저자: Clifford Mercer, 미국

문서유형: 튜토리얼 자료(총 67페이지), 1992년

 

실시간 시스템의 여러 스케쥴링 이론을 소개한 자료(실시간 시스템 테스팅을 하는데 있어 이해가 필요한 기본 지식)

---

 

실시간 시스템의 스케쥴링

• 실시간 컴퓨터 시스템은 현실 세계(physical world)의 이벤트에 반드시 특정 시간 주기 내에 반응해야 하는 점에서 비실시간 컴퓨터 시스템과 다르다.
• 전형적인 실시간 시스템은 외적 프로세스(external process)를 모니터 및 통제하며, 외적 프로세스에 변화가 있을 때 이를 적시에 알아채고 반응해야 한다.
• 외적 프로세스가 단순한 경우는 외적 이벤트에 신속하게 반응하는데 단일 마이크로컴퓨터로 충분하지만, 대개 실시간 시스템의 복잡도가 높기 때문에 다수의 프로세서와 소프트웨어 구조, 여러 액티비티를 조정하는 스케쥴링 방법이 요구된다.
• 따라서 실시간 애플리케이션이 운영체제(OS)로부터 요구하는 기능은 시간 제약이 없는 타임 쉐어링 애플리케이션이 OS로부터 요구하는 기능과 차이가 있다(특히 job scheduling에 있어 많은 차이점이 존재)

실시간 태스크(Tasks)

• 스케쥴링은 태스크 명세(task specifications)를 기반으로 하며, 특히 태스크의 도착시간(arrivals)과 마감시간(deadline)의 두 가지 속성이 중요시 된다.
• 태스크 도착은 주기적이거나(특정 태스크의 연속적인 호출 간에 일정한 시간 간격이 존재) 또는 통계적 분포를 보인다(즉, inter-arrival time이 랜덤 변수).
• 태스크는 자신의 데드라인 이전에 실행(컴퓨테이션)을 완료해야 한다. 명세된 데드라인 준수가 절대적인 경우는 하드 데드라인(hard deadlines), 되도록이면 데드라인 준수가 바람직하지만 이를 넘기는 것이 허용되는 경우는 소프트 데드라인(soft deadline)으로 불린다.

태스크의 컴퓨테이션과 시간 제약(Computations and Time Constraints)

• 실시간 시스템에서 컴퓨테이션 활동(Computational activities)은 대개 타이밍 제약을 가진다(즉, 언제 시작되고, 얼마나 오래 지속되고, 마감시간은 언제인지가 명시됨)
• 컴퓨테이션 활동들의 선후 관계(A precedence relation)도 정의 될 수 있으며, 이는 컴퓨테이션 순서(ordering)에 제약을 가한다. 컴퓨테이션 활동들은 또한 자원(resources)을 공유할 수도 있으므로 이로 인한 제약사항도 반드시 명세 되고 준수되어야 한다.
• 시간 제약을 가지는 컴퓨테이션에는 아래 그림처럼 스케쥴링 준비가 된 준비시간(ready time, r)이 존재하며, 이후 스케쥴링이 되어 프로세싱이 시작되고 일정 기간(p)이 경과한 후에 프로세싱이 완료된다. 데드라인 d는 준비시간(ready time)으로부터 일정 기간 후로 설정되며, 컴퓨테이션 완료시점 C는 원칙적으로 데드라인 보다 앞서야 한다.
• 컴퓨테이션의 준비시간(ready time)은 클록 이벤트, 외부 인터럽트, 타 컴퓨테이션이 생성시킨 소프트웨어 이벤트 등에 의해 시작될 수 있으며, 이런 준비 이벤트의 발생은 주기적(periodic)이거나, 비주기적이지만 예측 가능(aperiodic but predictable)하거나, 예측 불가능(unpredictable) 할 수도 있다.
• 컴퓨테이션 시간(computation time)은 일정 기간으로 고정되어 있거나 또는 가변적이고 예측 불가능할 수도 있다.
• 컴퓨테이션은 더 높은 우선순위의 타 태스크에 의해 선점 당할 수도 있으며(preemptible) 또는 선점이 불가능한 임계구역(a non-preemptible critical region)을 형성하고 있을 수도 있다.

타이밍 요구사항을 가진 태스크 집합 예: 홈 컴퓨터 시스템

• 본 문서는 스케쥴링 알고리즘을 설명하기 위한 예로 홈 컴퓨터 시스템을 제시함.
• 커뮤니케이션스테이션과 워크스테이션으로 사용되는 홈 컴퓨터는 가내의 여러 기기를 통제하고, 외부 전화선으로의 전화 인터페이스를 지원하며, 내부 인터콤 서비스 및 멀티미디어 통신 서비스를 제공하고, 전통적인 홈 컴퓨터 역할도 한다.
• 아래 표는 홈 컴퓨터 시스템의 태스크 집합을 기술하고 있다. 서로 다른 타이밍 요구사항을 가진 태스크들 간의 다양한 충돌이 발생 가능함

Task	t	p	작업	설명
τ1	15s	2ms	화재 탐지기(smoke detector)	매 15초 마다 정기적으로 체크가 필요, 실패 시 심각한 피해를 초래(하드 데드라인)
τ2	15s	2ms	움직임 탐지기(motion detector)	매 15초 마다 정기적으로 체크가 필요, 실패 시 심각한 피해를 초래(하드 데드라인)
τ3	40ms	5ms	디지털 오디오 인터콤(digital audio intercom)	40ms 간격으로 음성 패킷이 전송되어야 하지만 몇몇 패킷을 놓친다고 해서 생명에 위협을 가하지는 않음(소프트 데드라인)
τ4	40ms	5ms	디지털 폰(digital telephone)	40ms 간격으로 음성 패킷이 전송되어야 하지만 몇몇 패킷을 놓친다고 해서 생명에 위협을 가하지는 않음(소프트 데드라인)
τ5	20ms	12ms	CD 고품질 오디오	20ms 주기로 패킷 전달, 일부 패킷 손실 시 청취자의 짜증을 초래하지만 생명을 위협하지는 않음(소프트 데드라인)
τ6	15s	2ms	화장실 범람 탐지기(toilet overflow detector)	매 15초 마다 태스크가 호출되어야 하지만 실패 해도 그 결과가 심각하지는 않음(소프트 데드라인)
τ7	1d	60s	홈컴퓨터에서 뉴스 다운로드(download newspaper)	백그라운드 활동, 주기적인 태스크는 아니지만 얼마나 자주 호출될지 그리고 컴퓨테이션에 대략 얼마나 소요될지 추정 가능
τ8	1h	20s	홈컴퓨터에서 프로그래밍 작업 컴파일	백그라운드 활동, 주기적인 태스크는 아니지만 얼마나 자주 호출될지 그리고 컴퓨테이션에 대략 얼마나 소요될지 추정 가능
τ9	1s	1ms	키누름(keystroke)	상호적인(interactive) 활동, 키누름이 언제 일어날지 예측 불가능하지만 적절한 반응 시간이 요구됨

• 의도하지 않은 동작이 발생하지 않도록 신중하게 위 태스크들을 스케쥴 해야 함. 예를 들어 선착순에 따른 FCFS 스케쥴링 적용 시 뉴스 다운로딩 태스크는 시스템의 다른 활동들을 모두 셧다운 시키는 심각한 결과를 초래할 수 있다. 즉, 1분 정도 되는 다운로드 시간 동안 화재 탐지기와 움직임 탐지기가 완전히 비활성화 상태가 되고 또한 인터콤과 전화 대화도 방해를 받게 된다.
• 할당된 일정 시간 주기가 경과하면 태스크 선점이 일어나는 라운드로빈 스케쥴링(round robin scheduling)을 적용하는 경우에도 문제가 있을 수 있다. 컴퓨테이션 시간이 짧은 화재 탐지기(τ1) 같은 경우는 할당된 주기 내에 시간 요구사항을 충족시킬 수 있지만 오디오 태스크(τ5)는 필요한 충분한 컴퓨테이션 시간을 얻지 못할 수도 있다.
• 따라서 각 태스크의 그리고 모든 태스크의 타이밍 요구사항을 충족시킬 수 있는 스케쥴링 정책이 요구된다.

FCFS 스케쥴링	라운드로빈 스케쥴링

순환 실행 스케쥴링(Cyclic executive)

• 설계 단계 동안에 오프라인으로 결정된 스케쥴(또는 태스크들의 목록)을 반복적으로 실행 하는 소프트웨어 구조로 시간 제약적인 컴퓨테이션이 결정적이며(deterministic) 예측가능(predictable) 할 것을 요구함
• 이 방법은 주기적 프로세스, 이벤트 기반 프로세싱, 백그라운드 프로세싱이 우세한 환경에서 주로 사용된다. 특히 주기적 프로세스는 순환 실행에 적절하며 종종 실행의 메이저 사이클(major cycle)과 마이너 사이클(minor cycle)을 결정한다(메이저 사이클을 동일한 주기로 분할하는 마이너 사이클은 프레임으로도 불려짐)
• 실현 가능한 스케쥴을 찾기 위한 정형화된 규칙이나 알고리즘이 존재하지 않아서 설계자 자신의 기지나 직관에 의존해야 하므로 순환 실행 스케쥴 구축이 쉽지는 않음
• 장점으로 이해 및 구현이 쉽고 실행이 효율적이고 예측 가능하다. 또한 컴퓨테이션들 간의 문맥 전환(context switching)도 매우 빠르다. 따라서 빠르고 예측 가능한 실행이 필수적인 하드 리얼타임 시스템에서 가장 흔하게 사용되는 방법이다.
• 단점은 시스템이 유연하지 못하고 유지보수가 어렵다는 점이다. 새로운 태스크 추가나 기존 태스크의 컴퓨테이션 시간 변경이 사전 계산된 스케쥴을 무효로 만들 수 있다. 

홈 컴퓨터 예제에 순환 실행 스케쥴링 적용

• 메이저 사이클 동안 각 태스크가 적어도 한번은 실행될 필요가 있으므로 메이저 사이클 주기를 15s로 함. 빈도가 가장 높은 태스크의 주기가 20ms이므로 마이너 사이클 주기를 20ms로 결정
• 먼저 20ms 주기로 발생 빈도가 가장 높은 τ5를 각 마이너 사이클 주기 동안 한번씩은 실행되도록 아래 그림처럼 타임라인에 위치시킴

• 다음은 태스크 τ3과 τ4를 타임라인에 위치 시킴(이들은 40ms 주기를 가지므로 한 쌍의 마이너 사이클 간격으로 등장해야 함). τ5가 자리잡고 있는 하나의 마이너 스케쥴에 τ3와 τ4가 함께 들어가기에는 부족하므로 이들을 서로 다른 마이너 스케쥴에 각각 위치시킴

• 여기까지는 20ms의 각 마이너 사이클 중 17ms를 소비함. 남아 있는 주기적 태스크 τ1, τ2, τ6은 각각 2ms의 컴퓨테이션 시간이 필요하므로 한 마이너 사이클에 함께 들어가지 못하고 서로 다른 마이너 사이클에 각각 자리를 잡음. 15s의 주기를 가진 이 태스크들은 하나의 메이저 사이클마다 한번씩만 등장하면 되므로 아래 그림처럼 처음 3개의 마이너 사이클에 각각 자리잡은 후로는 다음 메이저 사이클까지 잠잠하다(즉, 더 이상 시간 프레임을 차지하지 않음).
  

• 모든 주기적인 태스크는 이제 타임라인 상에 위치되었고 5개의 고유한 마이너 스케쥴이 나타남. 첫 번째 마이너 스케쥴은 C1 = τ5τ3τ1, 두 번째는 C2 = τ5τ4τ2, 세 번째는 C3 = τ5τ3τ6이며, 남은 메이저 사이클 동안 번갈아 가며 반복되는 나머지 두 개의 마이너 스케쥴은 C4 = τ5τ4와 C5 = τ5τ3 이다.
• 메이저 스케쥴은 아래 식처럼 마이너 스케쥴의 시퀀스로 표현될 수 있다. (C4C5)¹¹은 하나의 메이저 스케쥴 동안에 서브시퀀스 C4C5가 11번 반복되는 것을 의미함.
  

C = C1C2C3(C4C5)¹¹

• 시스템은 이렇게 결정된 스케쥴 C를 영구 반복한다. 아래의 최종 타임라인에서 볼 수 있는 것처럼 마이너 스케쥴의 말단에 다양한 크기의 유휴시간(idle time)이 남는데, 이 타임 슬롯들은 비주기적인 태스크의 백그라운드 활동을 위해 사용된다.

• 이 방법의 단점은 시스템에 새로운 시간 제약적인 태스크를 추가하고자 할 때 이를 최종 타임라인에 반영하는 일이 쉽지 않다는 것이다. 예를 들어, 40ms 주기와 4ms 컴퓨테이션 시간을 가진 새로운 태스크 τ10(t10=40ms, p10=4ms)을 추가해야 하는 경우, 처음 두 개의 마이너 스케쥴의 남은 여유 시간이 τ10을 받아 들이기에 충분하지 않다. 따라서 이미 스케쥴링 된 태스크 중 빈도가 낮은 태스크를 밀어내고 타임 슬롯을 확보하는 등의 변경이 요구된다(즉, 아래 그림처럼 신규 태스크 추가를 위해 기 결정된 스케쥴의 재설계가 요구됨)
  

결정적 스케쥴링(Deterministic scheduling)

• 조합 최적화(combinatorial optimization) 분야의 한 갈래인 결정적 스케쥴링 이론은 프로세서로의 태스크 할당이 각 시점마다 정확하게 알려진 스케쥴을 생성한다.
• 이 방법은 태스크의 정확한 타이밍 정보가 사전에(a priori) 알려져 있을 것을 요구한다. 즉, 결정적 스케쥴링 알고리즘은 도착시간(arrival times), 준비시간(ready times), 계산 시간(computation times), 마감시간(deadlines)의 타이밍 정보를 가지고 여러 대안 중 최적화된 안을 선택해 정확한 스케쥴을 생성한다.
• 이 스케쥴링은 태스크를 수행하는데 걸리는 시간이 스케쥴을 분석 및 생성하는데 걸리는 시간보다 훨씬 큰 공장의 job shop(각 태스크가 임의의 프로세서 집합에 의해 임의의 순서로 처리됨)이나 flow shop(각 태스크가 모든 프로세서에 의해 같은 순서로 처리됨) 환경에서 사용되도록 의도되었으며, 온라인 컴퓨터 스케쥴링에서는 아래와 같은 이유로 그 가치가 제한적이다
  1) 태스크의 컴퓨테이션 시간이 대개 미리 알려져 있지 않고
  2) 태스크를 수행 하는데 걸리는 시간에 비해 스케쥴을 생성하는 시간이 너무 길며
  3) 태스크가 동적으로 도착하므로 최적화된 성능을 위해 새로 업데이트된 스케쥴 계산이 요구됨. 대부분의 결정적 스케쥴링 알고리즘은 본질적으로 점진적(incremental)인 특성이 결여되어 있어서 신규 태스크를 쉽게 받아들이지 못한다.

자원 가용량 기반 스케쥴링(Capacity-based scheduling)

• 자원 가용량 기반 알고리즘은 태스크 집합이 필요로 하는 컴퓨테이션 양과 프로세싱 인자의 가용한 컴퓨테이션 양에 대한 정보만을 요구한다. 스케쥴링 의사결정을 하는데 있어 태스크의 정확한 타이밍 정보에 의존하는 결정적 스케쥴링 알고리즘(deterministic scheduling algorithms)과는 차이가 있음
• Liu와 Layland의 비율 단조 알고리즘(rate monotonic algorithm)은 가용량 기반 스케쥴링 알고리즘의 대표적인 예이다. 

비율 단조 스케쥴링 분석(rate monotonic scheduling analysis: RMS)

• 태스크 집합의 자원 사용율(utilization) 계산을 통해 스케쥴링이 가능한지(즉, 실시간 작업들이 설계대로 실행될 수 있는지)를 판단하는 RMS 분석은 아래와 같은 실시간 태스크를 가정한다.
  - 태스크 집합에 포함된 각 태스크가 주기적(periodic)이다
  - 태스크 주기의 끝을 태스크의 데드라인으로 간주한다
  - 각 주기적 태스크의 컴퓨테이션 시간이 일정하다
  - 태스크들이 서로 커뮤니케이션 하거나 동기화 하지 않는다
  - 태스크는 컴퓨테이션의 어느 시점에서든 선점 당할 수 있다. 즉, 컴퓨테이션의 어디에도 임계구역(critical regions)이 존재하지 않는다.
• 위 가정 사항을 만족하는 태스크 집합의 스케쥴링에서 태스크들은 발생 빈도에 따라 순서가 정해지고 우선순위를 할당 받는다. 즉, 발생 빈도가 가장 높은(다시 말하면 주기가 가장 짧은) 태스크에 가장 높은 우선순위가 주어진다.
• 태스크 집합의 사용율(utilization)을 계산하고 이를 스케쥴가능경계값(a schedulable bound)과 비교함으로써 이 방법에 따라 스케쥴링 된 태스크들의 모든 데드라인이 준수될 수 있는지 예측 가능하다. 사용율이 스케쥴가능경계값보다 작거나 같은 경우 스케쥴 가능성이 보장된다(아래 식 참조). 반면 사용율이 경계값보다 큰 경우 해당 태스크 집합의 스케쥴 가능 여부를 보장할 수 없다(가능할 수도 있고 그렇지 못할 수도 있어서 추가적인 분석이 요구됨). 

(Ci는 태스크 τi의 컴퓨테이션 시간, Ti는 태스크 τi의 주기를 나타냄)

• 아래 표는 사용율과 비교되는 스케쥴가능경계값(schedulable bounds)을 태스크 집합 크기에 따라 나열하고 있다.

• Lehoczky는 태스크 집합이 스케쥴 가능한지를 판단하는 더 정확한 기준을 제시함. τ₁, τ₂,…, τ_n의 태스크 집합에서 태스크들이 우선순위 순서대로인 경우(i<j, τi의 우선순위가 τj의 우선순위 보다 높음), 아래 식이 충족되면 태스크들의 데드라인이 준수되며 해당 태스크 집합이 스케쥴 가능(schedulable) 하다.

RMS의 장단점

• 가용량 기반 알고리즘의 핵심은 태스크의 실제 소프트웨어 구조에 대해 너무 상세하게 파고들지 않고 단지 몇몇 패러미터(실행시간, 동기화봉쇄시간, 커뮤니케이션봉쇄시간, 주기, 최소 interarrival 시간)만을 사용하여 태스크 집합의 스케쥴가능성(schedulability)을 판단하는데 있다.
• 실시간 시스템의 작업들은 종종 서로 동기화되고 커뮤니케이션 될 필요가 있는데 RMS 알고리즘은 이런 태스크를 가진 시스템의 성능을 예측할 수 없다(RMS에서는 태스크들이 서로 독립적이고, 주기적이고, 완전히 선점가능하고, 태스크가 모두 단일 프로세서 상에서 동작함을 가정함). 이를 개선하기 위해 기본적으로는 RMS 틀을 따르지만 태스크에 대한 가정을 위반하는 태스크도 받아들일 수 있는 알고리즘을 개발하려는 여러 노력이 있어 왔음
• RMS 알고리즘은 또한 주기적 태스크에 한정되어 있다. 이런 환경에서 비주기적 태스크들을 지원하기 위해서는 이들을 백그라운드 모드로 실행시키거나 또는 비주기적 태스크 큐를 정기적으로 체크하여(polling) 준비된 비주기적 태스크가 있는지 확인하는 방법이 있다. 첫 번째 방법의 백그라운드 서버에서는 모든 주기적 활동이 완료될 때까지 비주기적 태스크가 기다려야 하므로 비주기적 액티비티들의 성능(평균 반응 시간)이 좋지 못하다. 두 번째 폴링 서버의 경우는 성능이 더 양호하지만 비주기적 태스크가 폴링이 일어난 직후에 도착하면 다음 폴링 주기까지 기다려야만 비로소 실행 기회를 얻게 된다.
  

홈 컴퓨터 예제에 RMS 적용

• 홈 컴퓨터 시스템에서 처음 6개의 태스크(τ1~τ6)가 주기적인 태스크임. 이 태스크들이 RMS 분석에서 요구하는 모든 조건을 만족한다고 가정함
• 먼저 아래 테이블처럼 빈도(주기 길이)에 따라 6개의 태스크의 순서를 결정하고, 이 순서에 따라 태스크 이름을 다시 부여한 후 우선순위를 할당한다.

• 위 태스크 집합이 스케쥴 가능한지(schedulable)를 결정하기 위해 아래와 같이 사용율(utilization)을 계산한다.

• 계산된 사용율(0.8504)을 RMS 스케쥴가능경계값과 비교한다. 6개의 태스크를 가진 태스크 집합의 스케쥴가능경계값이 0.735이므로 사용율이 스케쥴가능경계값보다 더 크고 따라서 이 태스크 집합이 스케쥴 가능한지 여부를 결론 낼 수 없다.
• 하지만 아래의 더 정확한 기준을 사용해서 홈 컴퓨터 예제의 주기적 태스크들을 계산하면 RMS 스케쥴링이 가능하다는 결과가 나옴
  

• 홈 컴퓨터 시스템 태스크 집합에 포함된 3개의 비주기적 태스크들은 순환 실행 스케쥴링에서 그랬던 것처럼 주기적 태스크 수행 사이에 남는 유휴시간을 통해 서비스할 수 있다.

동적 우선순위 스케쥴링(Dynamic priority scheduling)

• 리퀘스트(request)마다 태스크 우선순위가 변경될 수 있으며 또한 하나의 리퀘스트 내에서도 시간 경과에 따라 태스크 우선순위가 동적으로 변할 수 있음. 태스크 우선순위가 일단 할당되면 다시 변경되지 않는 정적 우선순위 스케쥴링(static priority scheduling)과 구분됨
• 결정적 스케쥴링 알고리즘(deterministic scheduling algorithms)은 대개 사전에 완전하게 정의된 태스크 집합을 기준으로 태스크 스케쥴을 생성하는 반면 우선순위 스케쥴링(Priority scheduling)이 적용되는 환경에서는 태스크들이 예측 불가능하게 도착할 수 있다.
• 동적 우선순위 기법들은 절대적인 예측가능성(absolute predictability)이 요구되는 시스템에서는 대개 사용되지 않는다. 이 기법들은 또한 과부하 조건(overload conditions)에서도 적절하지 않다. 과부하 상황에서는 스케쥴링 알고리즘이 덜 중요한 것은 제쳐두고 가장 중요한 태스크를 선택하여 실행할 수 있어야 하는데, 대부분의 동적 우선순위 알고리즘이 우선순위에 이런 태스크 중요도 정보를 포함시키지 않는다.
• 정적 우선순위는 변경이 없으므로 재계산이 필요 없지만 동적 우선순위는 각 의사결정 시점마다 반드시 재계산 되어야 하기 때문에 동적 우선순위 기법들이 더 높은 스케쥴링 오버헤드(scheduling overhead)를 가진다.

최단 마감 우선 스케쥴링(Earliest-Deadline-First)

• 동적 우선순위 스케쥴링 알고리즘 중 가장 잘 알려진 알고리즘
• 아래 예와 같이 데드라인이 임박한 태스크들을 우선적으로 스케쥴링 한다(검은 막대가 데드라인을 나타냄)

최소 슬랙 타임 스케쥴링(Least-Slack-Time)

• 태스크의 슬랙 타임(slack-time)은 데드라인을 놓치지 않으면서 최대한 지연될 수 있는 시간양이다. 시간 t에서 태스크 τ_i의 슬랙 타임은 d_i-p_i-t로 산정됨
• 이 스케쥴링 알고리즘은 슬랙 타임을 기준으로 우선순위를 할당한다(어떤 태스크가 데드라인을 놓칠 위험에 가장 높게 처해있는지에 대한 정보에 기반하여 실행할 다음 태스크를 선택)