프로세스 스케줄링_4 (Real-time System)

앞서 살펴보았던 기본적인 스케줄링 방법 이외에 한단계 더 심화된 스케줄링 방법에 대하여 알아보자.

 

오늘 알아볼 스케줄링 방법은 크게 두가지인데, 1)Proportional Share scheduling과 2) Real-time System의 스케줄링이다.

 

 

 

1. Proportional Share Scheduling

 

각 프로세스가 전체 Time share 중에 몇 퍼센트정도 가질지 결정하는 스케줄링 기법.

 

전체 CPU실행시간을 Time share라는 단위로 쪼갠 뒤, 각 프로세스에게 일정 퍼센트만큼 할당해주는 방법이라고 생각하면 된다.

 

전체 Time share을 T라고 했을 때, 각 프로세스는 N만큼의 시간을 할당받는다. (N < T)

 

두가지 예시를 살펴보자.

 

예1) MQ에서 큐 끼리의 스케줄링 비율 설정시 자주 사용되는 방법으로, 각 프로세스마다 일정 비율에 맞는 숫자를 정해준뒤, 한번 실행시마다 숫자에서 하나씩 까주는 방법이다.

예를들어 A프로세스와 B프로세스를 3:2의 비율로 Time share를 할당해준다고 하자. 만약B프로세스가 한타임 실행되면, 3:1이 되고, A프로세스가 한타임 실행되면 2:1이 되는 식이다.

만약 모든 숫자가 0이 되면 다시 초기화 시켜준다.

 

예2) Lottery Scheduling방식이 있다. N개의 Time share가 있다고 할 면, [1, ... , N]을 P개의 파티션으로 나누어준다.

P1 = [1, ..., 5]  P2 = [6, ..., 8]  P3 = [9, 10] 이런 식으로 말이다.

그다음 1부터 N 사이의 하나의 난수를 뽑은뒤, 그 숫자가 포함된 파티션의 프로세스를 실행시켜주는 방식이다.

 

 

 

2. Real-time System

 

Real-time System이란, Deadline 이 있는 task들이 있는 System이다.

 

가장 대표적인 예로 과제를 들 수 있다. 과제는 과제마다 제출기한, 즉 Deadline이 있다.

 

Real-time system은 크게 두가지로 나눌 수 있는데, 1) Soft real-time system과 2) Hard real-time system이다.

 

• Soft real-time system

이 시스템에서는 real-time task 와 Non-real-time task들이 혼재되어 있는 상황에서, 시스템이 real-time task를 조금 더 신경써서 처리해 주기는 하지만, 무조건 deadline에 맞춰서 끝내줄거라는 보장이 없는 시스템을 말한다.

 

물론, deadline이 있는 것을 더 빨리 처리해주기는 하지만, 무조건적으로 deadline을 맞춰주는것은 아닌 시스템이다.

 

• Hard real-time system

Hard real-time system은 각 task들을 무조건 deadline에 맞춰서 끝내주는 시스템이다.

 

이 시스템에서 deadline을 못맞추는것은 너무 치명적이어서, 못맞출바에야 차라리 그냥 스케줄을 안해주는게 더 나을 정도인 시스템이다. 대표적인 예로는 자율주행 자동차나, 무기체계에 사용되는 시스템들이 있다.

 

 

Real-time system에서 특정 프로세스가 주기를 가지고 반복적으로 들어온다고 생각해보자. 이때 주기를 p, deadline을 d, 프로세싱되는 시간을 T라고 하면, 아래의 그림이 성립된다. (0 <= T <= d <= p)

 

Real-time scheduling

 

이 때, rate of the periodic process = 1/P 임을 잘 알아두자!

 

 

 

3. Real-time 의 deadline을 맞추기 위한 스케줄링 방법들

 

앞서 살펴보았던 Hard real-time system과 같은 경우에는 deadline을 꼭 맞춰야 한다. 이렇게 deadline을 맞추기 위한 스케줄링 기법들에 대하여 살펴보자.

 

1) RMS (Rate Monotonic Scheduling)

 

각 프로세스 중 rate가 가장 높은 프로세스부터 스케줄링을 하는 기법 (필요시 preemptive 한다.)

 

다시한번 강조하면,  rate of the periodic process = 1/P 이다. 즉, RMS는 (rate가 가장높은 프로세스) = (주기(P)가 가장 짧은 프로세스)를 먼저 스케줄링하는 기법이다.

 

이 방법은 프로세스가 들어온 순간마다 priority를 판단하는 것이 아니라, 처음부터 rate를 사용하여 priority를 정해주고, 그 priority그대로 쭉 스케줄링 해주는 것이다. 

 

말로 설명하는 것보다, 두가지 예시를 들어보겠다.

 

예1) P1은 주기가 50초이고, 20초동안 processing한다. P2는 주기가 100초이고, 35초동안 processing한다.

이 경우, RMS 스케줄링을 이요하면 아래와 같은 결과가 나온다.

 

RMS Scheduling1

 

처음 P1과 P2가 들어왔을 때, P1이 주기가 짧으므로(=rate가 높으므로) P1을 먼저 스케줄링해준다. 20초간의 스케줄링이 끝나면 P2가 스케줄링된다. P2가 스케줄링 되는 도중 50초에 P1이 들어오게 되고, P1이 더 rate가 높으므로 P1이 preemption해서 스케줄링된다. P1이 끝난 70초에 P2가 마저 스케줄링 된다.

 

예2) P1은 50초 주기, 25초동안 processing. P2는 80초 주기, 35초 동안 processing.

이 경우, RMS를 적용하면 결과는 아래와 같다.

 

RMS Scheduling2

 

위의 경우를 보면, P1이 P2보다 rate가 높으므로 priority가 높은 것을 확인할수 있다. 그래서 P1 먼저 실행되고, P2가 실행되다가 50초에 다시 P1이 스케줄링된다. 75초에 다시 P2가 스케줄링 되고있는데, 80초에 첫번째 P2 스케줄링이 끝나기 전에 다시 P2가 스케줄링된다. 이 경우, deadline을 맞추는데 실패한 것이다. (펑)

 

• RMS의 특징

RMS는 앞서 강조했듯이, 처음부터 static한 priority를 줘서 실행되는 스케줄링 기법이다.

 

만약 RMS를 사용했는데, 예2) 처럼 deadline을 맞추는데 실패한 경우, static priority를 주는 다른 어떤 방법으로 해도 deadline을 못맞춘다.

 

RMS에 대한 한가지 수학적으로 증명된 것이 있는데, N개의 Process로 N(2^(1/N) - 1) 이상의 CPU utilization이면, RMS로는 스케줄링이 불가능하다는 것이다.

 

참고로 CPU Utilization = ∑ (Process time / period)이다.

 

예1) 의 CPU utilization은 (20/50) + (35/100) = 0.75 이다.

 

 

2) EDF (Earliest Deadline First)

 

deadline이 가까워져 올 때, 가장 급한놈 먼저 스케줄링 해주는 기법

 

EDF는 우리가 과제할 때, 본능적으로 사용하는 스케줄링 기법이다. 과제 제출기한이 가장 적게 남은 과제 먼저 하는 방식이다.

 

이 방법은 RMS처럼 static하게 priority를 주는 것이 아니라, task들이 들어올때마다 deadline을 비교해보고, priority를 정하는 방식이다.

 

예) P1은 주기가 50이고, processing이 25이다. P2는 주기가 80이고, processing이 35이다.

주기가 데드라인이라고 생각할 때, EDF를 적용한 결과는 아래 그림과 같다.

 

EDF

 

먼저 처음에는 deadline이 더 급한 P1이 먼저 스케줄링된다. 이후 P2가 스케줄링 중인 50초 때, P1이 들어오는데, 이 때 각 프로세스의 deadline을 따져보면, P2(30) 이 P1(50)보다 급하다. 그래서 P2를 계속 스케줄링 해준다.

 

80초 때 P2가 들어오는데, 이 때 deadline을 따져보면, P1(20)이 P2(80)보다 급하다. 그래서 P1을 계속 스케줄링 해준다.

 

100초때 P1이 들어오는데, 이 때 deadline을 따져보면, P1(50)이 P2(60)보다 급하다. 그래서 P1이 preemption을 해서 스케줄링 하게 된다.

 

• EDF의 특징

EDF는 RMS와 다르게 task들이 들어오는 순간마다 priority를 판단해준다.

 

또한, priority를 판단할 때 오직 deadline만을 이용하므로, CPU burst time을 모르는 경우에 유용하게 쓸 수 있다.

 

EDF방식은 이론적으로 CPU Utilization을 100% 까지 끌어올릴 수 있는 효율적인 스케줄링 방식이다. 그래서 만약 EDF를 썼는데도 deadline을 못맞췄다는 것은 CPU Utilization을 풀로 썼는데도 못맞췄다는 뜻이다. (즉 답이없다는 뜻이다.)

 

 

오늘 배운 내용을 정리해보면,

 

1. 심화적인 스케줄링 기법에는 Proportional Share Scheduling과 Real-time system Scheduling이 있다.

 

2. Real-time 스케줄링을 맞추기위한 기법에는 RMS와 EDF가 있다.

 

3. RMS는 rate를 가지고 static priority를 적용하는 것이고, EDF는 남은 deadline을 가지고 dynamic priority를 적용해준다.

 

본 내용은 공부하며 정리한 것으로, 오류가 있을 수 있습니다.