[운영체제] CPU 스케줄링: 실시간 CPU 스케줄링 - (2)

 

우선순위 기반 스케줄링(Priority-Based Scheduling)

---

 

실시간 OS의 가장 중요한 기능은 실시간 프로세스에 CPU가 필요할 때 즉시 응답을 해주는 것이다.

 

따라서, 실시간 OS의 스케줄러는 선점형 우선순위 기반 알고리즘을 지원한다.

 

이는 프로세스의 중요도에 따라 우선순위를 부여하고, 현재 CPU를 사용하고 있는 프로세스가 더 높은 우선순위를 가지는 프로세스에 의해 선점될 수 있다.

 

 

 

선점형 우선순위 기반의 스케줄러를 제공하는 것은 연성 실시간 시스템(soft real-time system) 임을 보장해준다.

 

하지만, 경성 실시간 시스템(hard real-time system)은 마감시간(deadline) 내에 수행되는 것을 보장해야 하므로, 부가적인 스케줄링 기법이 필요하다.

 

 

 

스케줄링될 프로세스들의 특성은 다음과 같다.

 

프로세스들은 주기적이다. 즉, 프로세스들은 일정한 간격으로 CPU가 필요하다.

 

각각의 주기 프로세스들은 CPU를 얻을 때마다 고정된 수행 시간 t, CPU로부터 반드시 서비스를 받아야 하는 마감시간 d와 주기 p가 정해져 있다.

 

이때, 수행 시간 t, 마감시간 d, 주기 p 사이의 관계는 0 ≤ t ≤ d ≤ p이다.

 

주기 태스크의 실행 빈도(rate)는 1/p이다.

 

 

periodic task - operating system concepts by Silberschatz A. & Galvin P. B. & Gagne G.

 

 

프로세스는 스케줄러에게 자신의 마감시간 요구사항을 알려야 할 수도 있다.

 

이때, 스케줄러는 승인-제어 알고리즘(admission-control algorithm)을 사용해서,

 

프로세스가 마감시간 내에 완료할 수 있다는 것을 보장할 수 있으면 실행을 허락하고, 보장할 수 없다면 요구를 거절한다.

 

 

 

 

 

 

Rate-Monotonic 스케줄링(RM Scheduling)

---

 

Rate-Monotonic(RM) 스케줄링 알고리즘은 선점 가능한 정적 우선순위 정책(static priority policy)을 이용하여 주기 태스크들을 스케줄링한다.

 

각 주기 태스크의 우선순위는 주기(period)의 역으로 할당된다.

 

즉, 주기가 짧으면 높은 우선순위가, 주기가 길면 낮은 우선순위가 할당된다.

 

이 정책은 CPU를 더 자주 필요로 하는 태스크에 더 높은 우선순위를 주려는 원리에 기반을 두고 있다.

 

 

RM 스케줄링은 주기 프로세스들의 처리 시간이 각 CPU burst time마다 같다고 가정한다.

 

 

RM 스케줄링은 어떤 프로세스 집합을 이 알고리즘으로 스케줄링할 수 없다면 정적 우선순위를 이용하는 어떤 다른 알고리즘으로도 스케줄링할 수 없다는 측면에서 최적(optimal)이라고 할 수 있다.

 

RM 스케줄링 기법은 최적이기는 하지만 많은 제약이 있다.

 

CPU 이용률은 한계가 있기 때문에 CPU 자원을 항상 최대화해서 사용할 수는 없다.

 

N개의 프로세스를 스케줄링할 때 최악의 경우 CPU 이용률은 $N(2^{1/N} - 1)$이다.

(N=1이면 100%, N=2이면 83%, N=∞이면 63%)

 

만약 두 프로세스가 존재한다면, 두 프로세스의 CPU 이용률의 합이 83% 미만이면, RM 스케줄링 알고리즘이 두 프로세스의 마감시간을 만족시키도록 스케줄링하는 것을 보장한다.

 

만약 두 프로세스의 CPU 이용률의 합이 83% 이상이면, RM 스케줄링 알고리즘이 두 프로세스의 마감시간을 만족시킬지 보장할 수 없다.