비율 단조 스케줄링

3. 한계 및 개선

비율 단조 스케줄링(RMS)은 이론적으로 효율적이지만 몇 가지 중요한 한계점을 가지고 있으며, 이를 보완하기 위한 개선 방안들이 연구되었다.

RMS의 주요 가정 중 하나는 태스크들이 서로 독립적이며 자원을 공유하지 않는다는 것이지만, 실제 시스템에서는 자원 공유가 빈번하게 발생한다. 이로 인해 우선순위 역전 현상이나 교착 상태가 발생할 수 있다. 이러한 문제는 시스템의 예측 가능성을 저해하고 심각한 오작동을 유발할 수 있으며, 이를 해결하기 위해 선점 금지 구간 설정, 우선순위 상속 프로토콜, 락 프리 알고리즘 사용 등 다양한 기법이 적용된다. (자세한 내용은 하위 문단 참고)

또한, RMS는 모든 태스크의 데드라인이 자신의 주기와 같다고 가정한다. 하지만 실제로는 데드라인이 주기보다 짧거나 긴 경우가 존재한다. 데드라인과 주기가 같은 경우에는 RMS가 최적의 고정 우선순위 스케줄링 알고리즘이지만, 데드라인이 주기보다 짧은 경우에는 데드라인 모노토닉 스케줄링(DMS)이 최적이다.^[17] 데드라인이 주기보다 긴 경우에 대한 최적 고정 우선순위 스케줄링 방법은 아직 명확히 정립되지 않은 문제이다.

1973년 Liu와 Layland는 RMS가 주어진 태스크 집합을 성공적으로 스케줄링할 수 있는지 판단하는 충분 조건을 제시했다. n개의 주기적인 태스크가 있을 때, 총 CPU 이용률($U$)이 다음 조건을 만족하면 모든 태스크가 데드라인을 만족하며 스케줄링될 수 있다.

:$U\; =\; \backslash sum\_\{i=1\}^\{n\}\; \backslash frac\{C\_i\}\{T\_i\}\; \backslash leq\; n(\backslash sqrt[n]\{2\}\; -\; 1)$

여기서 $C\_i$는 태스크 $i$의 실행 시간, $T\_i$는 태스크 $i$의 주기이다. 태스크의 수가 무한히 많아질 경우, 이 상한값은 $\backslash ln\; 2$, 즉 약 69.3%로 수렴한다.

:$\backslash lim\_\{n\; \backslash rightarrow\; \backslash infty\}\; n(\backslash sqrt[n]\{2\}\; -\; 1)\; =\; \backslash ln\; 2\; \backslash approx\; 0.693147\backslash ldots$

이는 어떤 태스크 조합이 주어지더라도 RMS가 스케줄링 가능함을 보장하는 충분 조건이다. 즉, CPU 이용률이 69.3% 이하면 항상 스케줄링이 가능하지만, 69.3%를 넘는다고 해서 반드시 스케줄링이 불가능한 것은 아니다. 실제로 많은 경우, 특히 태스크들의 주기가 조화롭게 분포되어 있다면, 훨씬 높은 CPU 이용률(예: 85% 이상^[16])에서도 모든 데드라인을 만족하며 스케줄링될 수 있다. 그러나 이는 특정 조건 하에서의 통계적인 결과이며, 모든 경우에 보장되는 것은 아니다. 따라서 시스템 설계 시에는 이 충분 조건을 기준으로 안정성을 확보하거나, 개별 시스템의 특성을 고려한 정밀한 스케줄링 가능성 분석이 필요하다.

3. 1. 자원 공유 및 우선순위 역전

• '''CPU 인터럽트 잠금''': 실시간 커널(uC-OS II 등)에서 ''OSIntEnter()'' 및 ''OSIntExit()''와 같은 함수를 사용하여 CPU 인터럽트를 일시적으로 비활성화한다.
• '''장치 인터럽트 잠금''': 리눅스 커널 등에서 ''splx()''와 같은 함수를 사용하여 특정 장치 인터럽트를 잠근다.
• '''최고 로커 프로토콜''' (Highest Locker Protocol): 모든 태스크 간의 자원 충돌 가능성을 미리 분석하여 각 자원에 접근할 수 있는 태스크 중 가장 높은 우선순위를 "상한 우선순위"로 설정한다.
• '''기본 우선순위 상속 프로토콜''' (Basic Priority Inheritance Protocol)^[18]: 낮은 우선순위 태스크가 보유한 락을 높은 우선순위 태스크가 요청하면, 락을 해제할 때까지 낮은 우선순위 태스크의 우선순위를 높은 우선순위 태스크의 수준으로 올린다.
• '''우선순위 상한 프로토콜''' (Priority Ceiling Protocol)^[19]: 기본 우선순위 상속 프로토콜을 개선한 방식으로, 각 세마포어에 해당 세마포어를 사용할 가능성이 있는 모든 태스크 중 가장 높은 우선순위를 "상한 우선순위"로 할당한다. 낮은 우선순위 태스크가 세마포어를 획득하면, 그 태스크의 현재 우선순위를 상한 우선순위와 자신의 우선순위 중 더 높은 값으로 즉시 올린다. 이를 통해 상한 우선순위보다 낮은 다른 태스크가 선점하는 것을 막는다.

수학적으로는 지연 알고리즘과 즉시 알고리즘 간에 큰 차이가 없으나, 즉시 알고리즘이 구현하기 더 효율적이어서 많은 실제 시스템에서 사용된다.

기본 우선순위 상속 프로토콜은 "블로킹 연쇄"(chain blocking) 문제를 일으킬 수 있다. 즉, 높은 우선순위 태스크가 임계 구역(critical section)에 진입하기 위해 여러 개의 낮은 우선순위 태스크들이 순차적으로 자원을 점유하고 해제하기를 기다려야 하는 상황이 발생하여 대기 시간이 길어질 수 있다. 반면, 우선순위 상한 프로토콜 등 다른 프로토콜들은 높은 우선순위 태스크가 임계 구역 진입 전에 최대 하나의 낮은 우선순위 태스크의 임계 구역 실행만 기다리도록 보장한다.

우선순위 상한 프로토콜은 VxWorks와 같은 실시간 운영체제에서도 사용 가능하지만, 실제로는 자주 사용되지 않는 경향이 있다.

기본 우선순위 상속 기법이 문제 해결에 사용된 대표적인 사례로 마스 패스파인더 탐사선의 소프트웨어 버그 해결 과정이 있다. 화성 탐사 중 발생한 시스템 리셋 문제를 해결하기 위해 우선순위 상속 기법이 적용되었다.

3. 2. 우선순위 상속 프로토콜

• '''기본 우선 순위 상속 프로토콜'''(Basic Priority Inheritance Protocol)^[8][18]은 낮은 우선순위 태스크가 자원을 점유하고 있을 때, 더 높은 우선순위의 태스크가 해당 자원을 요청하면, 자원을 점유한 낮은 우선순위 태스크의 우선순위를 요청한 높은 우선순위 태스크의 수준으로 일시적으로 승격시키는 방식이다. 자원이 해제되면, 해당 태스크는 원래의 우선순위로 복원된다. 이 방법은 교착 상태를 방지하지 못하며, '''체인 블로킹'''(chain blocking)으로 인해 어려움을 겪는다. 즉, 높은 우선 순위의 태스크가 여러 공유 자원에 순차적으로 접근하는 경우, 각 자원에 대해 낮은 우선 순위의 태스크를 기다려야(블로킹) 할 수 있다.^[9] Linux 커널의 [https://rt.wiki.kernel.org/index.php/Main_Page 실시간 패치]에는 이 프로토콜의 구현이 포함되어 있다.^[10] 마스 패스파인더 탐사선의 재설정 버그^[13][14]는 이 프로토콜과 관련된 유명한 사례로, 화성 현지에서 세마포어 생성 플래그를 변경하여 우선순위 상속을 활성화함으로써 문제를 해결했다.

• 우선 순위 천장 프로토콜(Priority Ceiling Protocol)^[11][19]은 기본 우선 순위 상속 프로토콜을 개선한 방식이다. 각 세마포어에 ''천장 우선순위''(priority ceiling)를 할당하는데, 이는 해당 세마포어에 접근할 수 있는 가장 높은 태스크의 우선 순위이다. 태스크는 해당 섹션의 천장 우선 순위보다 우선 순위가 낮으면 낮은 우선 순위의 임계 섹션을 선점할 수 없다. 이 방법은 교착 상태를 방지하고 블로킹 시간을 최대 하나의 낮은 우선 순위 임계 섹션 실행 시간으로 제한한다. 하지만 때로는 불필요한 블로킹을 유발할 수 있어 최적이 아닐 수 있다. 우선 순위 천장 프로토콜은 VxWorks 실시간 커널에서 사용할 수 있으며, '''가장 높은 로커의 우선 순위 프로토콜'''(Highest Locker's Priority Protocol, HLP)이라고도 한다.^[12] 그러나 실제 사용 빈도는 낮은 것으로 알려져 있다.

실제로 지연 알고리즘과 즉시 알고리즘 사이에는 수학적 차이가 없으며, 즉시 알고리즘이 구현하기에 더 효율적이므로 대부분의 실제 시스템에서 사용되는 경향이 있다.

4. 인터럽트 서비스 루틴 (ISR)

모든 인터럽트 서비스 루틴(ISR)은 하드 실시간 데드라인 유무와 관계없이, ISR의 우선순위가 모든 스케줄러 제어 작업보다 높다면 RMS 분석에 포함되어 스케줄 가능성을 결정해야 한다.

ISR의 처리 주기가 가장 짧은, ISR이 아닌 작업의 주기보다 짧으면, RMS 규칙에 따라 이미 적절하게 우선순위가 지정될 수 있다. 그러나 중요한 데드라인을 가진 ISR이 아닌 작업의 주기보다 긴 주기/데드라인을 가진 ISR은 RMS 규칙을 위반하며, 작업 세트의 스케줄 가능성 분석을 어렵게 만든다.

이렇게 잘못된 우선순위를 가진 ISR 문제를 해결하는 방법은 다음과 같다.

• 주기 조정 분석: 분석 과정에서 ISR의 주기를 실제보다 짧게, 즉 가장 짧은 주기를 가진 작업의 주기와 같다고 가정하는 방법이다. 이렇게 하면 분석상으로는 RMS 규칙을 만족하는 우선순위를 부여할 수 있다. 다만, 이 경우 ISR의 사용률 계수($U\_\{isr\}$)와 전체 시스템의 총 사용률 계수가 실제보다 높게 계산된다. 이 계산된 총 사용률이 스케줄 가능성 상한선보다 낮다면, 시스템은 스케줄 가능하다고 판단할 수 있다.
• 예시: ISR의 계산 시간($C\_\{isr\}$)이 500 마이크로초이고 주기($T\_\{isr\}$)가 4 밀리초라고 가정하자. 만약 가장 짧은 주기를 가진 스케줄러 제어 작업의 주기($T\_1$)가 1 밀리초라면, ISR은 우선순위는 높지만 주기가 더 길어 RMS 규칙을 위반한다. 스케줄 가능성을 분석하기 위해 ISR의 주기를 $T\_\{isr\}\; =\; T\_1\; =\; 1$ 밀리초로 가정한다. 그러면 ISR의 사용률 계수 $U\_\{isr\}\; =\; C\_\{isr\}\; /\; T\_\{isr\}$는 원래 $0.5\; ms\; /\; 4\; ms\; =\; 0.125$에서 $0.5\; ms\; /\; 1\; ms\; =\; 0.5$로 증가한다. 이 증가된 사용률 계수를 사용하여 총 사용률을 계산하고 스케줄 가능성 상한과 비교한다.
• 주의: 이 주기 조정은 어디까지나 분석을 위한 가정일 뿐, 실제 ISR의 실행 주기가 바뀌는 것은 아니다.

• 작업 분리: ISR 자체는 새로운 세마포어나 뮤텍스를 설정하는 간단한 작업만 수행하도록 하고, 시간이 많이 소요되는 실제 처리는 별도의 새로운 프로세스로 분리하는 방법이다. 이 새로운 프로세스는 RMS 규칙에 따라 적절한 우선순위를 부여받고, ISR이 설정한 세마포어/뮤텍스 신호를 기다리도록(block) 설계한다. 스케줄 가능성을 분석할 때는, ISR이 소모하는 최소한의 CPU 사용률만큼을 스케줄 가능성 상한에서 제외해야 한다. 만약 ISR의 CPU 사용률이 무시할 수 있을 정도로 작다면 분석에서 제외할 수도 있다.

5. 예제

RMS가 적용된 시스템에서 스케줄링 가능성을 분석하는 예시는 다음과 같다.

=== 예제 1 ===

다음과 같이 3개의 프로세스가 있다고 가정한다.

RMS에서는 주기가 가장 짧은 프로세스에 가장 높은 우선순위를 부여한다. 따라서 우선순위는 P2(주기 5) > P1(주기 8) > P3(주기 10) 순서가 된다.

이 프로세스들의 총 CPU 사용률(Utilization Factor)은 다음과 같이 계산된다.

:$U\; =\; \backslash frac\{C\_1\}\{T\_1\}\; +\; \backslash frac\{C\_2\}\{T\_2\}\; +\; \backslash frac\{C\_3\}\{T\_3\}\; =\; \backslash frac\{1\}\{8\}\; +\; \backslash frac\{2\}\{5\}\; +\; \backslash frac\{2\}\{10\}\; =\; 0.125\; +\; 0.4\; +\; 0.2\; =\; 0.725$

Liu와 Layland의 정리에 따르면, n개의 프로세스가 있을 때 스케줄링이 가능하기 위한 충분조건은 다음과 같다.

:$U\; \backslash leq\; n(2^\backslash frac\{1\}\{n\}\; -\; 1)$

이 예제에서는 프로세스가 3개(n=3)이므로, 스케줄링 가능성을 보장하는 CPU 사용률의 상한($U\_\{lub\}$, Least Upper Bound)은 다음과 같다.

:$U\_\{lub\}\; =\; 3(2^\backslash frac\{1\}\{3\}\; -\; 1)\; \backslash approx\; 3(1.2599\; -\; 1)\; \backslash approx\; 0.7797$

계산된 총 CPU 사용률 $U\; =\; 0.725$는 상한 $U\_\{lub\}\; \backslash approx\; 0.7797$보다 작으므로 (), 이 프로세스 집합은 RMS에 의해 스케줄링이 가능하다고 결론 내릴 수 있다.

=== 예제 2 ===

다음과 같이 3개의 프로세스가 주어졌다고 가정한다.

RMS에 따라 우선순위는 P2(주기 5) > P3(주기 10) > P1(주기 16) 순서가 된다. 총 CPU 사용률은 다음과 같다.

:$U\; =\; \backslash frac\{3\}\{16\}\; +\; \backslash frac\{2\}\{5\}\; +\; \backslash frac\{2\}\{10\}\; =\; 0.1875\; +\; 0.4\; +\; 0.2\; =\; 0.7875$

Liu와 Layland의 스케줄링 가능성 충분조건 상한은 예제 1과 같이 $U\_\{lub\}\; \backslash approx\; 0.7797$이다. 계산된 총 CPU 사용률 $U\; =\; 0.7875$는 이 상한보다 크므로 ($0.7875\; >\; 0.7797$), Liu와 Layland의 조건만으로는 스케줄링 가능성을 보장할 수 없다.

이 경우, 더 정확한 분석 방법인 쌍곡선 경계(Hyperbolic Bound) 조건을 사용할 수 있다.

:$\backslash prod\_\{i=1\}^n\; (U\_i\; +1)\; \backslash leq\; 2$

여기서 $U\_i\; =\; C\_i\; /\; T\_i$이다.

:$(\backslash frac\{3\}\{16\}+1)\; \backslash times\; (\backslash frac\{2\}\{5\}+1)\; \backslash times\; (\backslash frac\{2\}\{10\}+1)\; =\; (1.1875)\; \backslash times\; (1.4)\; \backslash times\; (1.2)\; =\; 1.995$

계산 결과 $1.995\; \backslash leq\; 2$이므로, 쌍곡선 경계 조건에 따라 이 프로세스 집합은 스케줄링이 가능하다고 판단할 수 있다.

=== 예제 3 ===

다음과 같이 3개의 프로세스가 주어졌다고 가정한다.

RMS에 따른 우선순위는 P2(주기 5) > P3(주기 10) > P1(주기 32) 순서이다. 총 CPU 사용률은 다음과 같다.

:$U\; =\; \backslash frac\{7\}\{32\}\; +\; \backslash frac\{2\}\{5\}\; +\; \backslash frac\{2\}\{10\}\; =\; 0.21875\; +\; 0.4\; +\; 0.2\; =\; 0.81875$

Liu와 Layland의 충분조건 상한 $U\_\{lub\}\; \backslash approx\; 0.7797$보다 크므로($0.81875\; >\; 0.7797$), 이 조건으로는 스케줄링 가능성을 보장할 수 없다.

쌍곡선 경계 조건을 적용해 본다.

:$(\backslash frac\{7\}\{32\}+1)\; \backslash times\; (\backslash frac\{2\}\{5\}+1)\; \backslash times\; (\backslash frac\{2\}\{10\}+1)\; =\; (1.21875)\; \backslash times\; (1.4)\; \backslash times\; (1.2)\; =\; 2.0475$

계산 결과 $2.0475\; >\; 2$이므로, 쌍곡선 경계 조건으로도 스케줄링 가능성을 보장할 수 없다.

하지만 이 경우, 프로세스 P2와 P3의 주기가 각각 5와 10으로, P3의 주기가 P2 주기의 정확히 2배($T\_3\; =\; 2\; \backslash times\; T\_2$)인 조화 관계(harmonic relationship)에 있음을 알 수 있다. 이렇게 주기가 서로 정수배 관계인 프로세스들을 조화 태스크 부분 집합(harmonic task subset)으로 묶을 수 있다. 여기서는 {P2, P3}가 하나의 조화 부분 집합을 이루고, P1은 자체적으로 또 다른 부분 집합을 형성한다. 따라서 조화 태스크 부분 집합의 수 K는 2이다.

조화 태스크 부분 집합을 고려한 스케줄링 가능성 충분조건 상한은 다음과 같다.

:$U\_\{lub,\; harmonic\}\; =\; K(2^\backslash frac\{1\}\{K\}\; -\; 1)$

이 예제에서는 K=2이므로,

:$U\_\{lub,\; harmonic\}\; =\; 2(2^\backslash frac\{1\}\{2\}\; -\; 1)\; \backslash approx\; 2(1.4142\; -\; 1)\; \backslash approx\; 0.8284$

계산된 총 CPU 사용률 $U\; =\; 0.81875$는 조화 태스크 부분 집합을 고려한 상한 $U\_\{lub,\; harmonic\}\; \backslash approx\; 0.8284$보다 작으므로 (), 이 프로세스 집합은 스케줄링이 가능하다고 결론 내릴 수 있다.

이처럼 Liu & Layland 조건이나 쌍곡선 경계 조건으로 스케줄링 가능성이 보장되지 않더라도, 조화 태스크 부분 집합 분석 등 더 세밀한 분석을 통해 스케줄링 가능성을 확인할 수 있는 경우가 있다.

참조

_[1] 논문 Scheduling algorithms for multiprogramming in a hard real-time environment
_[2] 간행물 Understanding the Linux Kernel http://oreilly.com/c[...] 2014-09-21
_[3] 논문 On the complexity of fixed-priority scheduling of periodic, real-time tasks
_[4] 서적 Real-Time Systems and Programming Languages Addison-Wesley
_[5] 서적 "[1991] Proceedings Twelfth Real-Time Systems Symposium"
_[6] 간행물 IEEE Real-Time Systems Symposium
_[7] 논문 Rate Monotonic Analysis: the Hyperbolic Bound
_[8] 논문 Experience with processes and monitors in Mesa
_[9] 서적 Hard Real-Time Computing Systems: Predictable Scheduling Algorithms and Applications Springer
_[10] 웹사이트 Real-Time Linux Wiki https://rt.wiki.kern[...] kernel.org 2008-03-26
_[11] 논문 Priority inheritance protocols: an approach to real-time synchronization
_[12] 서적 Hard Real-Time Computing Systems: Predictable Scheduling Algorithms and Applications Springer
_[13] 웹사이트 Mike Jones at Microsoft Research http://research.micr[...]
_[14] 웹사이트 Mars Pathfinder Reset Bug - Anthology of Interest http://anthology.spa[...] 2008-09-09
_[15] 논문 Scheduling algorithms for multiprogramming in a hard real-time environment
_[16] 간행물 The Rate monotonic scheduling algorithm: exact characterization and average case behavior 1989-12
_[17] 논문 On the complexity of fixed-priority scheduling of periodic, real-time tasks 1982-12
_[18] 논문 Experience with Processes and Monitors in Mesa 1980-02
_[19] 논문 Priority inheritance protocols: an approach to real-time synchronization 1990-09
_[20] 웹사이트 경성 실시간 태스크를 위한 확장된 스케줄 가능성 검사를 갖는 비율단조 스케줄러 http://www.dbpia.co.[...]