Scheduling of Reactive Systems - Priority-Driven Scheduling

Priority-Driven Scheduling

 

내용에 들어가기 앞서, 스케줄링 조건에 대해 정의부터 하고 들어가자.

개념에 대한 이해가 쉬울 수 있도록, 최대한 단순하게 조건을 설정하자.

 

- 싱글 프로세서를 사용한다.

- 서로에 대해 독립적인 잡들로 구성된, 고정된 수 n개의 period task들에 대해 스케줄링 한다.

   - 이 잡들은 preemptive하며, 자기 스스로 중지되지 않는다.

   - aperiodic job과 sporadic job은 없다.

   - resource에 대한 고려는 하지 않는다.

 

- 스케줄링 decision들은 release of a job 혹은 completion of job 시간에 결정된다.

- 문맥 전환(context switch)에 따르는 오버헤드는 무시할만큼 작다고 가정한다.

- priority level에 대한 제한은 없다.

 

이러한 조건들(가장 간단하게 설정된)의 가정하에, prioriy driven scheduling을 알아보자.

prioriy driven scheduling은 크게 Fixed-Priority알고리즘과 Dynamic-Priority 알고리즘으로 나눌 수 있다.

 

Fixed-Priority vs Dynamic-Priority Algorithms

전에 언급하였듯이, priority driven스케줄러는 온라인 스케줄러이다.

즉 task에 대한 스케줄을 미리 짜놓지 않는다.

잡이 release되면 그 잡에대한 priority를 할당하고, 그 priority에 기반하여 우선순위 큐에 집어넣는다. (높은 priority를 갖는 잡들이 큐의 앞에 위치한다)

각 스케줄링 결정 시간마다(scheduling decision time) 스케줄러는 실행준비중인 잡들이 들어있는 큐를 업데이트 하고, 큐 가장 앞에 있는 잡을 실행시킨다.

 

Fixed-priority와 Dynamic-priority의 차이점은 아래와 같다.

Fixed-priority : 같은 테스크에 속하는 모든 잡들은 같은 우선순위를 갖는다.

Dynamic-priority = 같은 테스크에 속해있는 잡이더라도, 각각의 우선순위가 다를 수 있다.

 

---

Fixed-Priority 알고리즘의 종류

RM(Rate Monotonic)

 

가장 잘 알려진 우선순위-고정 알고리즘은 RM스케줄링이다.

RM알고리즘은 task의 period에 기반하여 우선순위를 부여한다.

 

- 짧은 주기를 가진 테스크일 수록 더 높은 우선순위가 부여된다

-> rate는 period와 반비례 관계에 있기 때문에, rate가 높을 수록 더 높은 우선순위를 갖게 된다.

 

위의 예시를 통해 RM스케줄링을 직관적으로 이해할 수 있을 것이다.

 

DM(Deadline Monotonic)

 

DM스케줄링은 RM에서 우선순위 부여 조건을 relative deadline으로 변형한 스케줄링이다.

즉 데드라인이 짧은 잡들을 가진 테스크일 수록, 더 높은 우선순위를 부여한다.

 

만약 relative deadline이 period와 같은 task들만 존재하는 상황에서 스케줄링을 한다면,

당연하게도 RM과 DM은 같은 스케줄링이 될 것이다.

하지만 데드라인과 주기가 같지 않은 경우라면, RM이 feasible한 스케줄링을 하지 못하는 경우에 DM이 feasible 스케줄을 할 수 있는 경우가 존재한다.

 

예를 들면,

T1 = (3, 1, 1) / T2 = (2, 1)에 대한 스케줄링을 생각해보자. (T2의 경우, (2, 1, 2)와 같은 의미이다.)

 

RM의 경우 T1의 주기는 3, T2의 주기는 2이기 때문에 T2에 더 높은 우선순위를 부여하게 된다.

따라서 T2의 잡을 먼저 스케줄 할 것이다.

이렇게 되면 T1의 첫 번째 잡의 deadline이 1이기 때문에, T2를 먼저 실행하는 순간 T1의 잡이 데드라인을 놓치게 된다.

 

DM의 경우, relative deadline을 기준으로 우선순위를 부여하기 때문에, T1이 더 높은 우선순위를 부여받게 된다.

이 경우에는 feasible한 스케줄링을 할 수 있다.

---

Dynamic-Priority 알고리즘의 종류

 

EDF(Earliest Deadline First)

 

EDF 스케줄링은 각 잡들의 absolute deadline을 기준으로 우선순위를부여한다.

매 스케줄링 결정 시간마다, job들의 큐는 earliest deadline을 기준으로 재정렬된다.

위 도식을 찬찬히 생각해보면, EDF의 스케줄링에 대한 이해를 할 수 있을것이다.

 

 

 

LST(Least Slack Time)

 

LST 스케줄링은 각 잡들의 slack time을 기준으로 우선순위를 부여한다.

job Ji에 대해서 현재 시간 t와 Ji의 남은 실행시간 x가 주어졌을 때,

슬랙타임은 di - t - x로 계산할 수 있다.

예를 들어 현재 시간이 3이고 J1과 J2가 실행 준비중인 잡 큐에 들어있다고 생각해보자.

J1의 데드라인은 7이고, execution time은 5이지만 이미 1만큼의 실행이 끝나있다.

J2의 데드라인은 8이고, execution time은 8이지만 이미 4만큼의 실행이 끝나있다.

J1의 슬랙타임을 계산해보면, 7 - 3 - (5-1) = 2이다.

J2의 슬랙타임을 계산해보면, 8 - 3 - (8-4) = 1이다.

 

위 경우 J2의 슬랙타임이 더 작으므로 J2에 더 높은 우선순위가 부여되는 것이다.

 

---

지금까지 여러 알고리즘에 대하여 살펴보았다.

이제 우리가 생각해야 할 의문은,

- 어떤 알고리즘이 더 좋은 알고리즘이며,

- 어떻게 하면 효과적으로 schedulablity를 테스트 할 수 있을까

이다.

 

위와 같은 판단을 위해 등장한 개념이 바로 Utilization이다.

 

---

Utilization

periodic task Ti에 대한 utilization ui는

ei(Ti의 execution time) / pi(Ti의 period)로 표현 할 수 있다.

 

즉 ui가 1이 넘어가면 스케줄링이 불가능 하게 되는 것이고,

작을수록 프로세서가 다른 일을 처리할 수 있는 시간이 많다는 의미를 갖는다.

 

테스크들의 집합 T = (T1, T2, ,,,, Tn)에 대하여 각각의 ui를 모두 더하면 Total utilization을 구할 수 있는데,

이 Total utiltization을 이용하여 해당 task set의 schedulability를 판단할 수 있다.

 

Ut(Total utiltization)는 아래와 같이 구할 수 있다. (각 task들의 ui를 모두 더한 값이다.)

이 Ut의 값과, 사용할 알고리즘이 스케줄할 수 있는 최대 U값을 비교하여 스케줄 가능성을 간편하게 체크할 수 있다.

 

즉 U_ALG는 특정 알고리즘이 스케줄 할 수 있는 U의 최대값이고,

스케줄 하고자 하는 테스크 셋 T의 UT가 사용할 알고리즘의 U_ALG보다 작다면,

해당 테스크셋을 해당 알고리즘을 통해 스케줄 할 수 있다는 의미이다.

 

 

아래는 Utilization을 계산하는 예제이다.

혹시 잘 감이 오지 않는 사람은 예제를 통해 이해를 도울 수 있을 것이다.

다음 포스팅부터는 이 Utilization을 적용하여 DM, RM, EDF 등의 알고리즘에 대하여 더 깊게 공부해볼것이다.