비율 단조 스케줄링 문서 원본 보기

{{위키데이터 속성 추적}}
[[전산학]]에서 '''비율 단조 스케줄링'''(rate-monotonic scheduling, 줄여서 RMS)은 [[1973년]] [[리우]](Liu)와 [[래일랜드]](Layland)가 제안한 [[실시간 시스템]]을 위한 스케줄링 정책이다. '''비율 단조 기법'''이라고도 한다.<ref>[http://www.dbpia.co.kr/view/ar_view.asp?arid=684978 경성 실시간 태스크를 위한 확장된 스케줄 가능성 검사를 갖는 비율단조 스케줄러]《DBPia》</ref>
'''비율 단조 분석'''(rate-monotonic analysis, 줄여서 RMA)은 RMS의 배경이 되는 이론으로서, 시간 당 CPU 사용률을 계산하여 [[프로세스]]들을 이상없이 수행할 수 있는지를 알아보는 일을 말한다.

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

n개의 프로세스가 있을 때, CPU 사용율의 상한은 다음 공식으로 계산할 수 있다.
:<math>U = \sum_{i=1}^{n} \frac{C_i}{T_i} \leq n(\sqrt[n]{2} - 1)</math>

프로세스의 수가 많아지면 약 69.3%로 수렴한다.
:<math>\lim_{n \rightarrow \infty} n(\sqrt[n]{2} - 1) = \ln 2 \approx 0.693147\ldots</math>

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

== 예제 ==
RMS가 적용된 시스템 내에서 다음과 같이 3개의 프로세스가 있을 때, 스케줄링이 가능한지를 알아보자.
{| class="wikitable"
|-
! 프로세스
! 수행시간
! 주기
|- align="center"
! P1
| 1
| 8
|- align="center"
! P2
| 2
| 5
|- align="center"
! P3
| 2
| 10
|-
|}

위 표로부터 구한 CPU 사용률(Utilization Factor)은 다음과 같다.
:<math>\frac{1}{8} + \frac{2}{5} + \frac{2}{10} = 0.725</math>

3개의 프로세스들에 대해 스케줄링이 가능하기 위한 [[충분조건]]은 다음과 같다.
:사용률 <math>U = 3(2^\frac{1}{3} - 1) = 0.77976\ldots</math>


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

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

== 각주 ==
<references/>

== 같이 보기 ==
* [[EDF 스케줄링]]

== 외부 링크 ==
* [http://research.microsoft.com/~mbj/Mars_Pathfinder/Authoritative_Account.html Mars Pathfinder Bug] from Research @ Microsoft
* [https://web.archive.org/web/20060526152305/http://www.cs.berkeley.edu/%7Ebrewer/cs262/PriorityInversion.html Priority Inversion explained via the Mars Pathfinder Bug]

{{전거 통제}}

[[분류:스케줄링 알고리즘]]
[[분류:운영체제 기술]]