스케줄링 알고리즘 - RM

스케줄링이란

스케줄링 알고리즘은 준비 상태의 작업에 CPU를 배분하는 순서와 시점을 정하는 정책이다.

실시간 시스템의 마감 보장과 멀티프로세서의 부하 분산을 이 정책이 결정한다.

RM의 원리

RM은 주기적 실시간 태스크에 정적 우선순위를 주는 기법이다.

주기가 짧은 태스크는 마감이 가깝다. 그래서 주기가 짧을수록 우선순위가 높다.

우선순위는 실행 중에도 바뀌지 않는다. 그래서 RM은 정적 우선순위 방식이다.

더 높은 우선순위 태스크가 도착하면 현재 작업을 중단시키는 선점형이다.

이용률 판정식

RM의 충분 조건은 이용률 합이 n(2^(1/n)-1) 이하인지 보는 것이다.

n이 커질수록 상한은 약 0.693으로 수렴한다. 이는 CPU 이용률 약 69%까지 보장하는 것이다.

식을 만족하면 반드시 스케줄 가능하다. 만족하지 않아도 가능할 수 있다.

정답과 EDF 비교

정답은 0.828이다. 태스크가 2개이면 n=2를 식에 넣어 계산한다.

같은 실시간 분야의 EDF는 마감시각이 가까운 작업을 먼저 실행하는 동적 우선순위다.

이용률 상한은 EDF가 1.0, RM이 약 0.693이다. 그래서 EDF가 CPU를 더 많이 쓸 수 있다.

정리와 흔한 실수

정리하자. RM은 주기가 짧을수록 높은 정적 우선순위를 주는 선점형이다.

EDF는 마감시각이 가까운 작업을 먼저 실행하는 동적 우선순위 알고리즘이다.

RR, MLQ, SQMS, MQMS는 목적과 큐 구조가 달라 따로 구분해 두어야 한다.

RM 판정식은 충분 조건이므로 넘어도 스케줄 불가능이라고 단정하지 않는다.