속도 단조 스케줄링

컴퓨터 과학에서 RMS(^[1]Rate-Monotonic Scheduling)는 정적인 우선순위 스케줄링 클래스가 있는 실시간 운영 체제(RTOS)에서 사용되는 우선 순위 할당 알고리즘이다.^[2]정적 우선순위는 작업의 주기 지속시간에 따라 할당되므로, 주기 지속시간이 짧을수록 작업 우선순위가 높아진다.

이러한 운영 체제는 일반적으로 선제적이며 대응 시간에 관한 결정론적 보증을 가지고 있다.속도 단조 분석은 특정 애플리케이션에 대한 일정 보증을 제공하기 위해 그러한 시스템과 함께 사용된다.

소개

단순 버전의 속도 단조 분석에서는 스레드에 다음과 같은 속성이 있다고 가정한다.

• 리소스 공유 없음(프로세스는 리소스를 공유하지 않음(예: 하드웨어 리소스, 대기열 또는 모든 종류의 세마포어 차단 또는 비차단(버스위트)))
• 결정론적 마감일은 기간과 정확히 동일하다.
• 정적 우선 순위(즉시 실행할 수 있는 가장 높은 정적 우선 순위를 가진 태스크가 다른 모든 태스크를 선점함)
• 단일 비율 규칙에 따라 할당된 정적 우선 순위(기간/마감일이 짧은 작업에는 우선 순위가 더 높은 작업이 부여됨)
• 컨텍스트 스위치 시간 및 기타 스레드 작동이 자유롭고 모델에 영향을 미치지 않음

이 모델은 순환 로빈과 시간 공유 스케줄러가 다른 스케줄링 요구를 충족하지 못하는 폐쇄 시스템에서 기간의 계산된 시뮬레이션을 포함하는 수학적 모델이다.속도 단조 스케줄링은 시스템 내 모든 스레드의 실행 모델링을 살펴보고 문제의 스레드 집합에 대한 보증을 충족하기 위해 필요한 시간을 결정한다.

최적성

속도-단조 우선 순위 할당은 주어진 가정 하에서 최적이며, 이는 정적 우선 순위 스케줄링 알고리즘이 모든 마감일을 충족할 수 있다면 속도 단조 알고리즘도 마찬가지라는 것을 의미한다.마감일 단조 스케줄링 알고리즘은 또한 동일한 기간과 마감일에 최적이다. 사실 이 경우 알고리즘은 동일하다. 게다가 마감일수가 기간보다 짧을 때는 마감일 단조 스케줄링이 최적이다.^[3]마감일이 기간보다 클 수 있는 태스크 모델의 경우, 이 모델에 대한 정확한 스케줄링 가능성 테스트를 부여한 Audsley 알고리즘은 최적의 우선 순위 할당을 찾는다.^[4]

활용도 상한

최소 상한

류앤레이랜드(1973)는 고유한 기간을 가진 n개의 주기적 과제의 집합에 대해 CPU 활용도가 특정 경계(과제 수에 따라 달라짐) 미만일 경우 항상 마감시한을 충족하는 실현 가능한 스케줄이 존재함을 증명했다.RMS에 대한 스케줄링 성능 테스트:

${\displaystyle U=\sum _{i=1}^{n}{n}{U_{i}}=\sum _{i=1}^{n}{\frac {C_{i}}}{{{i}}}{{n}}}{{n}}}}{{n}}T_{i}}\leq n({2}^{1/n}-1)}$

여기서 U는 활용률 계수, C는_i 공정 i의 연산 시간, T는_i 공정 i의 출시 기간(마감일로부터 1년 후)이며 n은 공정 스케줄링할 공정의 수입니다.예를 들어, 두 공정에 대해 U 0 0.8284이다.공정의 수가 무한대로 향하는 경향이 있을 때, 이 표현은 다음과 같은 경향이 있을 것이다.

${\displaystyle \lim_{n\rightarrow \infit }n}\sqrt[{n}]{2}}-1)=\ln 2\약 0.693147\ldots}}}$

따라서 총 CPU 활용률 U가 70% 미만일 경우 RMS가 모든 마감일을 충족할 수 있다고 n${\displaystyle }n{\displaystyle }$ ${\displaystyle 10}$ ${\$일 때 대략적으로 추정한다.CPU의 나머지 30%는 낮은 우선순위의 실시간이 아닌 작업에 전용될 수 있다.n의 작은 값이나 U가 이 추정치에 근접한 경우 계산된 활용률 한계를 사용해야 한다.

실제로 $i{\displaystyle {}^{}}$ ${\displaystyle t^{}}$ ${\displaystyle h^{}}$ ${\$ 공정의$$ 경우, $C{\displaystyle {}_{}}$ ${\displaystyle i_{}}${\$displaystyle$$${$C_{i}}}$은(는) 최악의 경우(즉, 가장 긴) 계산 시간을 나타내야$$ 하며,$$ {\$displaystyle {T_{i$}}}}은 모든 처리가 발생해야 하는 최악의 경우 마감 시간(즉, 최단 시간)을 나타내야 한다$$.

고조파 작업 세트의 상한

류와 레이랜드는 T ${\displaystyle m_{}}$ ${\$ $T{\displaystyle {}_{}}$ i ${\$ > ${\$에 대해 이 바인드가 가능한 최대값 1.0으로 완화될 수 있다고 언급했다.$T_{i}}}$ and ${\displaystyle i=1...m-1}$, ${\displaystyle {T_{m}}}$ is an integer multiple of ${\displaystyle {T_{i}}}$, which is to say that all tasks have a period that is not just a multiple of the shortest period, ${\displaystyle {T_{1}}}$, but instead that any task's period모든 짧은 기간의 배수다.이것은 조화 작업 집합으로 알려져 있다.An example of this would be: ${\displaystyle [{T_{1}},{T_{2}},{T_{3}},{T_{4}}]=[1,3,6,12]}$. It is acknowledged by Liu and Layland that it is not always feasible to have a harmonic task set and that in practice other mitigation measures, such as buffering for tasks with 소프트 타임 마감일 또는 동적 우선순위 할당 접근법을 사용하여 더 높은 경계를 허용할 수 있다.

조화 사슬에 대한 일반화

K 고조파 작업 하위 집합(일명 고조파 체인)으로 구성된 작업 세트의 경우, 최소 상한 테스트는 다음과 같이 된다는 것을 궈와 목은^[5] 보여주었다.

${\displaystyle U=\sum _{i=1}^{n}{\frac {C_{i}}{{n}}{\frac}}{{i}}}}}}{T_{i}}\leq K({2}^{1/K}-1)}$

작업 주기가 다른 작업 주기의 정수 배수가 아닌 경우 작업 세트는 크기 1의 n 조화 작업 하위 집합으로 구성되어 있다고 생각할 수 $있으며{\displaystyle }$,${\displaystyle 따라서}$ K =$$n {\$displaystyle{$K}{=}{$n$이 일반화를 류와 레이랜드의 최소 상한과 동등하게 만든다.$K{\displaystyle }$= ${\displaystyle 1\mathrm{}}$ ${\$1}이$($가) 되면 상한은 1.0이 되어 완전한 활용도를 나타낸다.

확률 한계

그것은 이용은 높이 88%또는 less,[6] 하지만 이 사실 모든 작업 세트를 위해 보장될 수 없는 정확한 과제 통계(기간 마감일)법을 알고 있는, 어떤 점에서 저자들은 활용 최소한 상부 보신탕에 달려 있기 무작위로 생성된 주기적인 과제 시스템은 주로 모든 마감 시간을 맞춘다는 것을 보여 주고 있다.운트류와 라일랜드가 발표했다.

쌍곡선 바운드

쌍곡선 결합은^[7] 류와 라일랜드가 제시한 것보다 스케줄링하기에 충분한 조건이다.

${\displaystyle \prod _{}^{}}$ ${\displaystyle \underset{}{\overset{}{i}}}$= ${\displaystyle \underset{}{\overset{}{}}}$ ${\displaystyle \underset{}{\overset{}{}}\mathrm{U}}$ ${\displaystyle i_{}}$+ 1${\displaystyle }$) ${\displaystyle \le }$ ${\displaystyle 2}$ ${\displaystyle \prod _{i=1}^{n}(U_{i}+1)\leq 2$

여기서 U는_i 각 작업에 대한 CPU 사용률이다.개별적인 업무 활용 요소만을 사용하여 찾을 수 있는 가장 엄격한 상한이다.

리소스 공유

많은 실제 적용에서 자원은 공유되며 수정되지 않은 RMS는 우선순위 반전 및 교착 위험의 대상이 될 것이다.실제로 이것은 선취점을 무력화하거나 우선적 상속으로 해결된다.다른 방법은 잠금 없는 알고리즘을 사용하거나 우선순위가 다른 스레드 간에 뮤텍스/세마포어를 공유하는 것을 피하는 것이다.자원 갈등이 애초에 초래될 수 없도록 하기 위해서다.

선점 비활성화

• 그OS_ENTER_CRITICAL()그리고OS_EXIT_CRITICAL()실시간 커널에서 CPU 인터럽트를 잠그는 원시 요소(예: MicroC/OS-II)
• 그splx()장치 인터럽트의 잠금을 중첩하는 원시 요소 제품군(FreeBSD 5.x/6.x)

우선상속

• 기본 우선 순위 상속 프로토콜은^[8] 리소스를 요청 시 해당 리소스를 요청하는 태스크의 우선 순위로 유지하는 태스크의 우선 순위를 촉진한다.자원이 공개되면 프로모션 전 원래 우선순위 레벨이 복원된다.이 방법은 교착 상태를 예방하지 못하고 쇠사슬로 묶인 차단에 시달린다.즉, 높은 우선순위 태스크가 여러 공유 리소스에 순차적으로 액세스하는 경우 각 리소스에 대해 낮은 우선순위 태스크에서 대기(차단)해야 할 수 있다.^[9]리눅스 커널에 대한 실시간 패치는 이 공식의 구현을 포함한다.^[10]

• 우선 순위 상한 프로토콜은^[11] 각 세마포어에 상한 우선 순위를 할당함으로써 기본 우선 순위 상속 프로토콜을 강화하는데, 이것은 그 세마포어에 접근하게 될 가장 높은 직업의 우선 순위다.우선순위가 해당 섹션의 상한 우선순위보다 낮은 경우, 작업은 우선순위가 낮은 임계 영역을 선점할 수 없다.이 방법은 교착상태를 방지하고 차단 시간을 최대 한 개의 낮은 우선순위 임계 구간 길이까지 제한한다.이 방법은 불필요한 차단을 유발할 수 있다는 점에서 차선책이 될 수 있다.우선 순위 상한 프로토콜은 VxWorks 실시간 커널에서 사용할 수 있다.그것은 또한 최고 로커의 우선 순위 프로토콜(HLP)으로도 알려져 있다.^[12]

우선순위 상속 알고리즘은 두 개의 매개변수로 특징지어질 수 있다.첫째, 상속이 게으르거나(필수적일 때만) 즉시(갈등이 생기기 전에 우선 순위 상승)이다.둘째는 상속 낙관(최소 금액 증가) 또는 비관적(최소 금액보다 증가)이다.

	비관적인	낙천적인
당장의	OS_ENTER_CRITICAL()/OS_EXIT_CRITICAL()	splx(), 가장 높은 사물함
게을러진		우선 순위 상한 프로토콜, 기본 우선 순위 상속 프로토콜

실제로 게으른 알고리즘과 즉각적인 알고리즘 사이에는 수학적 차이(Rui-Layland 시스템 활용률의 측면에서)가 없고, 즉각적인 알고리즘은 구현이 더 효율적이기 때문에 대부분의 실용적인 시스템에서 사용되는 알고리즘이다.^{[citation needed]}

우선 순위 상속을 할 수 있도록 세마포어의 생성 플래그를 변경해 화성에 고정시킨 '마스 패스파인더 리셋 버그'가 기본 우선순위 상속의 이용 사례로 꼽힌다.

인터럽트 서비스 루틴

ISR이 모든 스케줄러 제어 작업보다 우선 순위를 갖는 경우 스케줄러 가능 여부를 결정하기 위해 모든 인터럽트 서비스 루틴(ISR)을 RMS 분석에 포함시켜야 한다.ISR의 처리 기간이 최단 비 ISR 프로세스의 처리 기간보다 짧은 경우, ISR은 이미 RMS 규칙에 따라 적절하게 우선순위를 정할 수 있다.그러나 중요한 마감일이 있는 비 ISR 프로세스 기간보다 긴 기간/데드라인을 가진 ISR은 RMS를 위반하게 되며, 작업 세트의 스케줄링 여부를 결정하기 위해 계산된 한계를 사용하지 못하게 한다.

잘못 사전 설정된 ISR 완화

잘못 사전 설정된 ISR을 완화하는 한 가지 방법은 가능한 한 ISR의 기간을 최단 기간과 동일하게 줄여 분석을 조정하는 것이다.이 짧은 기간을 부과하면 RMS를 준수하는 우선순위화가 이루어지지만, ISR의 활용률이 더 높아지며, 따라서 총 활용률 인자의 활용도가 여전히 허용 한계 미만일 수 있으므로 스케줄링 가능성이 입증될 수 있다.예를 들어 계산 시간, ${\displaystyle {\mathrm{Ci}}_{}}$ ${\displaystyle s_{}}$ r$${\$displaystyle {C_{isr}},$ 마침표 ${\displaystyle {Ti}_{}}$ ${\displaystyle s_{}}$ r ${\$이$($가) 4밀리초인 하드웨어 ISR을 고려해 보십시오.최단 스케줄러 제어 작업에 기간이 있는 $경우$ ${\displaystyle {T\mathrm{}}_{}}$1 {\$displaystyle$ {$T_{1}}$이 1밀리초인 경우 ISR은 우선 순위가 더 높지만 RMS를 위반하는 낮은 비율이 적용된다. 스케줄러성을 증명하기 위해 ${\displaystyle {Ti}_{}}$ s ${\displaystyle r_{}}$= ${\displaystyle T{}_{}}$ ${\displaystyle {1\mathrm{}}_{}}$ ${\$ {$T_{$isr$}}}={{}}}}}}}}}={{{$$disr$}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}$T_{1}}$을(를) 선택하고 ISR에 대한 활용률 계수(총 활용률 계수도 상승)를 다시 계산한다.이 경우 ${\displaystyle {Ui}_{}}$ ${\displaystyle s_{}}$ ${\displaystyle r_{}}$= ${\displaystyle C{}_{}}$ ${\displaystyle i_{}}$ ${\displaystyle s_{}}$ r${\displaystyle {}_{}}$/ ${\displaystyle T{}_{}}$ ${\displaystyle i_{}}$ s ${\displaystyle r_{}}$ ${\$isr}/{}$T_{isr}}}$ will change from ${\displaystyle {0.5ms}/{4ms}{=}0.125}$ to ${\displaystyle {0.5ms}/{1ms}{=}0.5}$. This utilization factor would be used when adding up the total utilization factor for the task set and comparing to the upper bound to prove schedulability.ISR의 기간을 조정하는 것은 분석만을 위한 것이며, ISR의 실제 기간은 변하지 않는다는 점을 강조해야 한다.

잘못 처리된 ISR을 완화하는 또 다른 방법은 ISR을 사용하여 새로운 세마포어/뮤텍스만 설정하는 동시에 RMS를 사용하여 적절하게 우선순위를 정했고 새로운 세마포어/뮤텍스를 차단하는 새로운 프로세스로 시간집약적 처리를 이동하는 것이다.스케줄링 가능 여부를 결정할 때 ISR 활동으로 인한 CPU 활용도의 여유를 최소 상한에서 빼야 한다.활용률이 미미한 ISR은 무시할 수 있다.

예

예 1

과정	실행시간	기간
P1	1	8
P2	2	5
P3	2	10

RMS에서는 P2가 가장 높은 비율(즉, 최단 기간)을 가지므로 우선순위가 가장 높으며, 그 다음이 P1과 최종 P3이다.

최소 상한

활용도: $1{\displaystyle \frac{\mathrm{}}{}}$ ${\displaystyle 8\frac{\mathrm{}}{}}$+ 2 +${\displaystyle \frac{5}{}}$ + ${\displaystyle 2\frac{10}{}}$ =${\displaystyle 0.725}$ ${\displaystyle {\frac${1$}{8}+{\frac {2}{5}+{\frac${2}{$10}}=0.725$

시스템이 스케줄링 가능하다고 결론을 내릴 수 있는 3개의$$ $[\$에 대한 충분한 조건은 다음과 같다.

$${\displaystyle {U_{lub}}=3(2^{\frac {1}{1}-1)=0.77976>0.693\ldots(0.693{\text{}는 }}}}의 RMS에 대한 활용률 바인딩됨$$

$0{\displaystyle .77976}$ ${\displaystyle \ge }$ ${\displaystyle 0.725}$ ${\displaystyle$ 0$.77976\geq 0.725$ 그리고 최소 상한보다 낮은 것이 충분한 조건이기 때문에 시스템을 스케줄링할 수 있다고 보장된다.

예 2

과정	실행시간	기간
P1	3	16
P2	2	5
P3	2	10

RMS에서는 P2가 가장 높은 비율(즉, 최단 기간)을 가지므로 우선순위가 가장 높고, 그 다음이 P3와 최종 P1이다.

최소 상한

예 1과 같이 류와 레이랜드 바인딩을 사용하면 작업 세트가 스케줄링 가능하다고 결론을 내릴 수 있는 3개의 $([\$ 3$\,},}$개 프로세스에$$ 대한 충분한 조건이 유지된다.

$${\displaystyle {U_{lub}=3(2^{\frac {1}{3}-1)=0.77976}$$

총 활용도: 3 ${\displaystyle \frac{16}{}}$+ ${\displaystyle \frac{2}{}}$ + 2${\displaystyle }$+ ${\displaystyle \frac{10}{}}$= 0${\displaystyle .7875}$ ${\displaystyle {\frac {3}{16}}+{\frac {2}{5}+{\frac {2}{10}}=0$.7875$\}$ .

< ${\displaystyle$ 0$.77976{{}0.7875}$ 이후, 시스템은 류와 레이랜드의 바인딩에 의해 스케줄링할 수 없다고 보장되지 않는 것으로 결정된다.

쌍곡선 경계

다음과 같이 더 엄격한 쌍곡선 바인딩 사용:

${\displaystyle \prod_{i=1}^{n}(U_{i}+1)=({\frac {3}{16}}+1)*({\frac {2}{5}+1)*({\frac {2}{10}+1)=1.995\leq 2}$

태스크 세트를 스케줄링할 수 있는 것으로 확인됨.

예 3

과정	실행시간	기간
P1	7	32
P2	2	5
P3	2	10

RMS에서는 P2가 가장 높은 비율(즉, 최단 기간)을 가지므로 우선순위가 가장 높고, 그 다음이 P3와 최종 P1이다.

최소 상한

예 1과 같이 류와 레이랜드 바인딩을 사용하면 작업 세트가 스케줄링 가능하다고 결론을 내릴 수 있는 3개의 $([\$ 3$\,},}$개 프로세스에$$ 대한 충분한 조건이 유지된다.

$${\displaystyle {U_{lub}=3(2^{\frac {1}{3}-1)=0.77976}$$

총 이용률은 다음과 $같다{\displaystyle \frac{\mathrm{}}{}}$:${\displaystyle \frac{7}{}}$ ${\displaystyle \frac{32}{}}$+ 2 + ${\displaystyle 2\frac{10}{}}$ =${\displaystyle 0.81875}$ ${\displaystyle${\$frac{7$}{$7}}}}+{\frac {2}{5}+{10}}=0.81875$

< ${\displaystyle$ 0$.77976{{}0.81875}$ 이후, 시스템은 류와 레이랜드 바인딩에 의해 스케줄링할 수 없다고 보장되지 않는 것으로 결정된다.

쌍곡선 경계

다음과 같이 더 엄격한 쌍곡선 바인딩 사용:

${\displaystyle \prod_{i=1}^{n}(U_{i}+1)=({\frac {7}{32}}+1)*({\frac {2}{5}+1)*({\frac {2}{10}+1)=2.0475}$

0<. ${\displaystyle$2$.0{{}2.0475}$ 이후, 시스템은 쌍곡선 바인딩에 의해 스케줄링할 수 없다고 보장되지 않는 것으로 결정된다.

고조파 작업 집합 분석

${\displaystyle {왜냐하면\mathrm{}}_{}}$ T${\displaystyle {}_{}}$3 = ${\displaystyle 2\mathrm{}}$ ${\displaystyle {T\mathrm{}}_{}}$ 2 ${\$$T_{2$ 작업 2와 3은 조화 작업 서브셋으로 간주할 수 있다.과제 1은 자체의 조화 과제 하위 집합을 형성한다.따라서 고조파 작업 하위 집합의 수 K는 2이다.

$${\displaystyle {U_{lub,harmonic}}=K(2^{\frac {1}{{K}-1)=2^{\frac{1}{1}{1}-1)=0.828}$$

위에서 계산한 총 이용률 계수(0.81875)를 사용하여 0< $<\displaystyle$ 0$.81875<0.828}$ 이후 시스템을 스케줄링할 수 있는 것으로 결정된다.

참고 항목

• 마감일 단조 스케줄링
• Deos, 작동 속도 단조 스케줄러를 포함하는 시간 및 공간 분할 실시간 운영 체제.
• 동적 우선 순위 스케줄링
• 가장 빠른 마감 첫 번째 예약
• RTMS, 작동 속도 단조 스케줄러를 포함하는 오픈 소스 실시간 운영 체제.
• 스케줄링(컴퓨팅)

참조

추가 읽기

• Buttazzo, Giorgio (2011), Hard Real-Time Computing Systems: Predictable Scheduling Algorithms and Applications, New York, NY: Springer.
• Alan Burns and Andy Wellings (2009), Real-Time Systems and Programming Languages (4th ed.), Addison-Wesley, ISBN 978-0-321-41745-9
• Liu, Jane W.S. (2000), Real-time systems, Upper Saddle River, NJ: Prentice Hall, 6장.
• Joseph, M.; Pandya, P. (1986), "Finding response times in real-time systems", BCS Computer Journal, 29 (5): 390–395, doi:10.1093/comjnl/29.5.390.
• Sha, Lui; Goodenough, John B. (April 1990), "Real-Time Scheduling Theory and Ada", IEEE Computer, 23 (4): 53–62, doi:10.1109/2.55469, S2CID 12647942

외부 링크

• 마이크로소프트사의 Mars Pathfinder 버그
• Mike Jones가 The Risks Digest, Vol.19, Case 49의 Mars Rover Pathfinder에서 실제로 일어난 일
• [1] Mars Pathfinder Bug의 실제적인 이유, 그러나 실제로 그것을 다루는 사람들, 즉 회사나 따라서 주식가치가 문제의 설명에 의존하는 사람들, 혹은 누군가가 그 문제에 대해 이야기하는 것을 들은 사람들보다.