Real-Time System (3) : Fixed Priority Scheduling

서론

이번 포스트에서는 optimality의 개념에 대해 간단히 소개한다. 이후 fixed priority scheduling의 대표적인 예시인 RM(Rate Monotonic)에 대해 소개하고, RM의 optimality 증명을 소개하고자 한다.

Schedulability

schedulability는 주어진 task set을 deadline miss 없이 스케줄 가능한 알고리즘이 있는지를 의미한다. 주어진 task set의 schedulability를 확인하는 일은 Real-Time System에서 중요한 과정이며, 관련 연구도 많다. task set이 schedulable하지 않다면 무슨 짓을 해도 deadline miss가 발생하니 해당 task set을 고려할 필요가 없기 때문이다. 따라서 offline phase (task set을 design하는 단계)에서는 period와 알고리즘을 결정하는 데에 중요하며, online admission phase에서는 새로운 task가 dynamic하게 생기더라도 schedulable한지 확인하는데에 중요하다.

Schedulability 관련 이론에서 중요한 두 가지 point는 아래와 같다.

• 어떻게 priority를 할당할 것인가?
  priority를 할당하는 방법은 정말 많다. 따라서 중요한 것은 제시하는 방법이 optimal한지, 혹은 주요 성능 지표들을 향상시킬 수 있는지 (예를 들어 offline schedule의 경우에는 schedule의 길이, makespan을 줄이는 것이 있을 것이다.)이다. 따라서 많은 연구들이 priority를 할당하는 알고리즘을 소개한 뒤 자신의 알고리즘이 optimal한지, 혹은 conditionally optimal한지를 소개한다.
• schedulability를 어떻게 검사할 것인가?
  schedulability를 검사하는 방법을 새로 제시하는 것 역시 하나의 주제가 될 수 있다. 이전 글들에서 소개한 방법들이기도 하지만, RTA(Response Time Analysis), TDA(Time Demand Analysis) 역시 schedulability를 검사하는 한 방법이다.
  

Optimality

Optimal Algorithm의 정의
스케줄링 알고리즘 A가 optimal하다는 것은 task set이 특정 알고리즘으로 스케줄 가능하다면, A로도 스케줄 가능하다는 의미이다.

정의만 놓고 보면 자명해보이나, optimality를 증명할 때에 정의를 이용하여 증명하는 것이 가장 쉽다. feasible한 임의의 스케줄에 대하여, 해당 스케줄을 우리의 알고리즘에 의한 스케줄로 변환할 수 있으면 알고리즘이 optimal하다고 할 수 있다.

직관적으로는 모든 schedulable task set을 feasible하게 만들 수 있는 알고리즘을 의미하는 것으로 보인다. 그렇다면 optimal algorithm은 하나밖에 없고 새로운 optimal scheduling algorithm은 나올 수 없는 것처럼 보인다. 그렇다면 왜 이렇게 optimal scheduling algorithm과 관련한 많은 논문이 나올 수 있을까? 그 이유는 각자의 scope가 다르기 때문이다. conditional optimality라고도 하는데, 자신의 알고리즘이 특정 constraint 하에서만 optimal이라고 주장하는 것이다. 완벽히 general한 상황에서 optimal한 알고리즘을 만드는 것은 어렵기 때문에, 대부분 constraint를 가지고 optimality를 증명한다. 예를 들어 EDF는 preemption이 가능하고, single processor이고, work-conserving한 경우에만 optimal하다.

Optimal Fixed Priority Algorithm

• RM (Rate Monotonic) : period가 짧을 수록 높은 priority를 주는 알고리즘을 말한다. 간단하게는 period의 역수로 priority를 주는 방법이 있다.
• DM (Deadline Monotonic) : relative deadline이 짧을 수록 높은 priority를 주는 알고리즘을 말한다.

소제목에 적어논 대로 두 알고리즘은 모두 optimal하다. 하지만 두 알고리즘은 분명히 다르다. period와 deadline은 엄연히 다른 값이기 때문이다. 즉, 각 알고리즘은 각자의 constraint에 대해 conditionally optimal하다고 할 수 있다. DM 알고리즘은 periodic task들에 대해 fixed priority이기만 하면 optimal하다. 하지만 RM의 경우에는 deadline과 period가 같다는 조건인 implicit deadline을 만족하는 task set에 대해서 optimal하다. 그럼 결국 period로 priority를 주는 것이 deadline으로 주는 것과 마찬가지이기 때문에 DM과 같다고도 할 수 있다.

Optimality of RM

실제로 RM이 optimal하다는 것을 증명해보자. 앞서 말했던 대로 feasible한 스케줄을 RM에 의한 스케줄로 바꿀 수 있다는 것을 보임으로써 증명할 것이다. 이를 위해 먼저 아래의 critical instant theorem을 정의한다.

Critical Instant Theorem

[Critical Instant Theorem]
fixed priority scheduling에서 task는 모든 higher priority task와 동시에 release되었을 때 첫 job이 deadline을 만족한다면 schedulable하다.

이 정리가 내포하는 바는 아래의 두 가지가 있다.

• schedulablity를 검사하기 위해 첫 job만 확인해도 된다는 것이다. 만약 아니라면 우리는 한 task의 모든 job에 대해 deadline을 만족하는지 검사해야 한다.
• fixed priority scheduling에서 한 job의 response time은 본인의 execution time과 preemption당한 시간의 합이다. 이렇게 구해진 response time이 relative deadline보다 작다면 feasible하다고 할 수 있다. 위 정리는 모든 task가 동시에 release되었을 때 response time이 가장 크다는 것을 내포한다. execution time은 동일하기 때문에 preemption을 가장 많이 당하는 조건이라고 봐도 무방하다.

pf)
task set 내의 task들을 priority 순으로 나열했다고 하자. 편의성을 위해 RM을 썼다고 가정하자면 $\Tau = \{ \tau_1, \dots, \tau_n \}$에서 $\tau_1$의 period가 가장 짧고, $\tau_n$의 period가 가장 길다. $\tau_n$은 priority가 가장 낮기 때문에 다른 $\tau_i$에 대해 preemption당한다. $\tau_n$의 release time이 0인데 $\tau_i$의 release time이 0이 아니라면 위 그림처럼$\tau_n$이 실행되다가 $\tau_i$에 의해 preemption당한다. 이 때 $\tau_i$의 release time이 더 앞당겨질수록 $\tau_n$의 주기 동안 $\tau_i$의 release가 더 많아질 가능성이 커진다. 그림에서 (b)의 경우 $\tau_i$의 release time이 앞당겨져서 (a)보다 1번 많이 preemption한 것을 확인할 수 있다. 따라서 $\tau_i$의 release time을 최대한 앞당겨서 t = 0에 release되게 하면 가장 많이 preemption될 것이라고 생각할 수 있다.
이를 $\tau_n$보다 priority가 높은 모든 task에 대해 반복하면 모든 task가 t = 0에 release될 때 가장 response time이 길어진다. 따라서 이 critical instance에 대해 response time이 deadline보다 작다면 어떤 release pattern에 대해서도 response time이 deadline보다 작을 것이기 때문에 task set이 feasible하다고 할 수 있다. 또한 뒤의 job 역시 다른 release pattern을 가지지만 첫 job보다 preemption이 같거나 적게 될 것이기 때문에 첫 job의 deadline miss 여부만 확인하면 된다는 것 역시 알 수 있다.

Optimaility Proof

모든 task가 t = 0에 release되는 조건을 critical instant라고 한다. 이제 우리는 위의 정리를 이용하여 critical instant 조건에서 feasible하지만 RM대로 스케줄되지 않은 스케줄을 RM에 의한 스케줄로 바꿀 수 있다는 것을 증명할 것이다. 증명은 swapping 기법을 이용할 것인데 생각보다 어렵지 않다.

RM으로 스케줄되지 않았다는 것은 위쪽 그림처럼 period가 더 긴 task의 job이 짧은 task의 job보다 먼저 실행되었다는 의미이다. 물론 이 경우에도 feasible한 스케줄 자체는 만들 수 있다. 어쨌든 두 task가 priority 순서대로 스케줄링되있지 않다고 했을 때 만약 두 task의 실행 순서를 아래 그림처럼 바꾸더라도 일반적으로 feasible함(deadline miss가 발생하지 않음)을 보이면 된다.
먼저 $J_{11}$의 경우에는 실행을 시작하는 시간이 더 앞당겨졌기 때문에 원래도 deadline을 만족했으니 자명하게 deadline을 만족한다.
$J_{21}$의 경우에는 미뤄진 completion time이 원래 $J_{11}$의 completion time인 $e_{11} + e_{21}$이다. 그런데 원래 $J_{11}$은 deadline을 만족했기 때문에 $e_{11} + e_{21} < D_1$이라 할 수 있고, 이는 $D_2$보다 작다. (RM에 의한 스케줄에서는 priority가 낮은 $\tau_2$가 period가 더 길기 때문) 따라서 $J_{21}$ 역시 deadline을 만족한다. priority 순서대로 되어있지 않은 모든 job에 대해 이 과정을 반복하면 결국 RM에 의한 스케줄로 바꿀 수 있다.
따라서 feasible한 임의의 스케줄을 RM에 의한 스케줄로 바꿀 수 있기 때문에 RM은 optimal하다.

Schedulability Check

이제 critical instant 조건에서 첫 job의 response time만 검사하면 된다는 것을 알았으니, response time을 쉽게 구하는 식만 있다면 주어진 task set의 schedulability를 알 수 있다. 이는 앞서 말했던 RTA로 수행할 수 있는데, 이 내용은 옛날 포스트에 올려놨기 때문에 생략하도록 하겠다.

다음 포스트에서는 RM의 utilization bound에 대해서 소개하도록 하겠다.