Rate monotonic 스케줄링

Rate monotonic 스케줄링은 주기 태스크에 주기가 짧을수록, 곧 요청 빈도가 높을수록 높은 우선순위를 주고, 그 우선순위를 한 번 정하면 바꾸지 않는 우선순위 배정 규칙이다. Liu와 Layland가 1973년 논문에서 이 규칙과 그 이용률 상한을 제시했고, 요청 빈도(rate)에 따라 우선순위가 정해진다는 뜻에서 rate-monotonic priority assignment라 불렀다.[1] 이 규칙은 RM(Rate Monotonic)으로 줄여 부른다.[2]

배정 규칙

RM은 우선순위를 실행 시간과 상관없이 태스크의 주기만으로 정하므로, 고정 우선순위 스케줄링의 배정 규칙 가운데 하나다.[1]

최적성

단일 프로세서에서 태스크가 일정한 간격으로 요청되는 주기 태스크이고, 서로 독립이며, 각 요청의 마감 시한이 다음 요청 시각이고, 실행 시간이 일정하며, 선점할 수 있으면, RM은 고정 우선순위 배정 가운데 최적이다. 어떤 고정 우선순위 배정으로 모든 마감 시한을 지킬 수 있는 태스크 집합은 RM으로도 지킬 수 있다.[1]

마감 시한이 주기와 같다는 가정이 빠지면 RM의 최적성은 성립하지 않는다.[3] 마감 시한이 짧을수록 높은 우선순위를 주는 DM(Deadline Monotonic)은 고정 우선순위 스케줄링에서 다룬다.

이용률 상한

단일 프로세서에서 서로 독립인 주기 태스크의 마감 시한이 다음 요청 시각이고 실행 시간이 일정하며 선점할 수 있으면, 태스크 $n$개의 이용률 $U$가 $U\le n(2^{1/n}-1)$을 만족하면 RM으로 모든 마감 시한을 지킨다. 이 상한은 $n=2$일 때 약 0.828이고, $n$이 커지면 $\ln 2$(약 0.693)에 가까워진다.[1]

이 조건은 충분조건이다. 이용률이 상한을 넘어도 주기끼리 알맞은 관계에 있으면 RM으로 스케줄할 수 있다. 이런 태스크 집합은 태스크마다, 우선순위가 더 높은 모든 태스크와 함께 요청하는 critical instant에 낸 요청이 마감 시한 전에 끝나는지를 계산해 판정한다.[1]

단일 프로세서에서 서로 독립인 주기 태스크가 모두 시각 0에 함께 시작하고 상대 마감 시한이 주기와 같으면, 태스크 $i$의 이용률을 $U_i$라 할 때 ${\prod }_{i=1}^n(U_i+1)\le 2$를 만족하는 태스크 집합은 RM으로 스케줄 가능하다. Bini 외는 이 충분조건을 hyperbolic bound라 불렀다. 이 조건은 Liu와 Layland의 상한과 계산 복잡도가 같으면서 덜 비관적이라 Liu와 Layland의 상한이 받아들이지 않는 태스크 집합도 받아들인다.[4]

Liu와 Layland의 가정 아래 무작위로 고른 큰 태스크 집합에서, RM이 실제로 스케줄할 수 있는 이용률은 평균 약 88%다.[5]

EDF와의 차이

현재 요청의 마감 시한이 가까울수록 높은 우선순위를 주는 EDF는 요청마다 우선순위가 바뀌는 동적 배정이라, RM이 최적인 고정 우선순위 배정의 부류 밖에 있다. 단일 프로세서에서 서로 독립인 주기 태스크의 마감 시한이 다음 요청 시각이고 실행 시간이 일정하며 선점할 수 있으면, EDF는 $U\le 1$인 태스크 집합을 모두 스케줄한다.[1]

[1]

C. L. Liu and J. W. Layland, “Scheduling Algorithms for Multiprogramming in a Hard-Real-Time Environment,” Journal of the ACM, vol. 20, no. 1, pp. 46–61, 1973, doi: 10.1145/321738.321743.

[2]

R. I. Davis and A. Burns, “A Survey of Hard Real-Time Scheduling for Multiprocessor Systems,” ACM Computing Surveys, vol. 43, no. 4, p. 35:1-35:44, 2011, doi: 10.1145/1978802.1978814.

[3]

J. Leung and H. Zhao, “Real-Time Scheduling Analysis,” Federal Aviation Administration, Final Rep. DOT/FAA/AR-05/27, 2005. Accessed: Sep. 29, 2026. [Online]. Available: https://www.faa.gov/sites/faa.gov/files/aircraft/air_cert/design_approvals/air_software/05-27_RTSA.pdf

[4]

E. Bini, G. C. Buttazzo, and G. M. Buttazzo, “Rate Monotonic Analysis: The Hyperbolic Bound,” IEEE Transactions on Computers, vol. 52, no. 7, pp. 933–942, 2003, Accessed: Oct. 07, 2026. [Online]. Available: https://retis.sssup.it/~giorgio/paps/2003/ieeetc-hb.pdf

[5]

L. Sha et al., “Real Time Scheduling Theory: A Historical Perspective,” Real-Time Systems, vol. 28, no. 2–3, pp. 101–155, 2004, Accessed: Oct. 07, 2026. [Online]. Available: https://retis.sssup.it/~giorgio/paps/2004/rtsj04-edf.pdf