비율 단조 스케줄링

전산학에서 비율 단조 스케줄링(rate-monotonic scheduling, 줄여서 RMS)은 1973년 리우(Liu)와 래일랜드(Layland)가 제안한 실시간 시스템을 위한 스케줄링 정책이다. 비율 단조 기법이라고도 한다.비율 단조 분석(rate-monotonic analysis, 줄여서 RMA)은 RMS의 배경이 되는 이론으로서, 시간 당 CPU 사용률을 계산하여 프로세스들을 이상없이 수행할 수 있는지를 알아보는 일을 말한다.

개요

수행 주기가 가장 짧은 프로세스에 가장 높은 우선순위를 부여하는 방식이다. 따라서, 비율(rate, 단위시간당 프로세스 수행 횟수, 수행 주기의 역수)과 우선순위의 관계를 그래프로 나타내면 우상향 직선형이 된다. 이렇게 비율에 따라 우선순위가 단조롭게 증가하는 추세를 보인다고 하여 '비율 단조'라는 이름이 붙게 되었다. 프로세스에 부여하는 우선순위의 변동이 없기 때문에, 정적 스케줄링 정책이라고 할 수 있다. 그렇지만 상당히 효율적이라서 아직도 널리 사용되고 있다. RMS를 사용하는 운영체제는 일반적으로 선점형이고, 응답시간에 대해 결정적(deterministic)인 특징이 있다.

n개의 프로세스가 있을 때, CPU 사용율의 상한은 다음 공식으로 계산할 수 있다.

$U=\sum _{i=1}^{n}{\frac {C_{i}}{T_{i}}}\leq n({\sqrt[{n}]{2}}-1)$

프로세스의 수가 많아지면 약 69.3%로 수렴한다.

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

RMA 이론의 시스템 모델

RMA 이론에서는 시스템을 아래와 같이 비교적 단순한 모델로 가정한다.

• 모든 프로세스는 단일 CPU에서 주기적으로 구동된다.
• 문맥 교환 시간은 무시한다.
• 프로세스들 사이에 자료 종속성이 없다.
• 프로세스의 수행 시간은 일정하다. (즉, 변함이 없다.)
• 마감시각은 그 프로세스가 수행되는 마지막 주기가 끝나는 시점으로 한다.
• 준비 상태의 프로세스 중 가장 우선순위가 높은 것이 수행을 위해 선택된다.

예제

RMS가 적용된 시스템 내에서 다음과 같이 3개의 프로세스가 있을 때, 스케줄링이 가능한지를 알아보자.

프로세스	수행시간	주기
P1	1	8
P2	2	5
P3	2	10

위 표로부터 구한 CPU 사용률(Utilization Factor)은 다음과 같다.

${\frac {1}{8}}+{\frac {2}{5}}+{\frac {2}{10}}=0.725$

3개의 프로세스들에 대해 스케줄링이 가능하기 위한 충분조건은 다음과 같다.

사용률 $U=3(2^{\frac {1}{3}}-1)=0.77976\ldots$

그래서 $0.725<0.77976\ldots$이므로 스케줄링이 가능하다고 할 수 있다.

다만, 이 조건은 필요조건이 아니므로 이 스케줄링 알고리즘이 적용된 시스템이 더 높은 사용률을 가지더라도 스케줄링이 불가능하다고 할 수는 없다.

같이 보기

• EDF 스케줄링

외부 링크

• Mars Pathfinder Bug from Research @ Microsoft
• Priority Inversion explained via the Mars Pathfinder Bug