[Real Time] Schedulability of Earliest Deadline First Using Utilization Bound Check

지난 포스트를 통해서 Rate Monotonic Algorithm을 사용한 Schedule의 Minimum Utilization이 0.69 이고 이걸 LL Bound라고 했다. 이번 포스트에서는 Earliest Deadline First의 Schedulability를 보고자 한다. 

 아무튼 우리가 알고 있는 것은 해당 Task 들의 Schedulability를 측정하기 위해서는 각각의 Task에 대한 Utilization을 구해야 되고 그 중에서 가장 작은 Utilization Bound를 찾아야 한다. 이게 결국은 Utilization Bound Check의 간략한 진행 방법이다.

그러면 Utilization 자체는 Execution Time / Period 의 합이므로 EDF의 Utilization은 다음과 같이 나타낼 것이고, 각각의 Task가 Deadline miss가 나지 않기 위해서는 그 Utilization의 합이 1을 넘지 않아야 할 것이다. 

그러면 결국 위의 식이 맞는지를 증명하면 이번 포스트에서 언급하고자 하는 것을 설명할 수 있을 것이다.

 일단 우리가 이걸 증명하는 방법은 두가지가 있다. 첫번째 방법은 목적이 Schedulable의 여부이므로 Schedulable하면 Total Utilization이 1보다 작거나 같다는 것만 보이면 된다. 이걸 직접적으로 증명하기 힘들면 위 가정의 대우인 Total Utilization이 1 보다 크면 Schedulable하지 않다는 것을 보이면 되는데 이 증명은 위에다가 직접 식을 대입해보면 쉽게 구할 수 있다. 당연히 Period보다 Execution Time이 긴 상황이므로 Deadline Miss가 발생하며, 즉 Schedulable하지 않다는 것을 보일 수 있다. 

 그러면 이제 고민해야 되는 것이 과연 Total Utilization이 1보다 작거나 같으면 Schedulable 하냐는 것이다. 만약 위의 가정을 성립하면서 지금의 가정이 성립한다면 결국은 필요 충분 조건에 의해서 Total Utilization간의 관계가 정립될 것이다. 그러면 위 가정의 대우인 task가 deadline을 벗어나면 Total Utilization이 1보다 크다는 것을 보이면 되겠다.

 그러면 일단 쉬운 케이스로 두가지 task에 대한 상황을 보겠다.

지금 보면 두번째 task는 t에서 deadline miss가 발생했다. 이 말을 다르게 하면 시점까지의 Execution이 일어났어야 할 시간, 즉 Execution Time의 합은 당연히 t보다 커야 한다는 것이다. 그러면 이때 Execution Time의 합을 측정하면 어떨까? 

 일단 두 task의 비교 기준이 다르므로 Task 1의 execution time은 theta 1 만큼 shift 된 시점으로 측정되어야 할 것이다. 그리고 Task 2의 Execution Time까지 구해보면 다음과 같이 구할 수 있다.

그러면 이 두개의 합이 t보다 크다는 것을 보이면 되는데 theta1의 크기는 p1에 비해서 무척 작은 값이므로 배제할 수 있다. 그러면 수식은 다음과 같이 전개된다.

이렇게 구하고 나면 좌변은 결국 Task들의 Utilization의 합이 나왔고, 이 값이 1보다는 크다는 것을 증명할 수 있다. 즉 deadline miss가 발생하면( 다르게 말해서 Not Schedulable하면..) Total Utilization은 1보다 크다는 것이다. 

 지금 이렇게 보인 것은 Schedule 상에 딱 두개만 있는 아주 간단한 케이스이고, 우리가 고려해야 될 것은 당연히 훨씬더 복잡한 케이스여야 할 것이다. 당장에 Task를 한 개 더 추가해도 수식이 복잡해진다. 

이렇게 하면 각각의 execution time을 측정해서 이 값이 t보다 크다는 것을 보일 수 있을까? 앞에서 두개의 task로 했을 때처럼 t로 수식이 정리되면 최종적으로 p와 e로 정리된 수식을 구할 수 있겠지만 위와 같은 경우는 Task 2가 중간에 끼면서 Task 1에 *라는 time이 발생한다. 이 식이 그대로 적용되면 위처럼 치환할 수 없을 것이다. 

 결국 *를 없애는 것이 관건이 된다. 그렇게 해야 위에서 쉬운 case처럼 치환할 수 있을 것이다. Liu 책에서는 Idle Interval과 Busy Interval을 활용해서 특정영역만 고려하는 방법을 소개하고 있다. 

idle interval 자체는 단어에서 나오는 것처럼 task의 idle status의 interval을 말한다. 

여기서 idle interval은 I라고 표시된 부분이다. 그런데 사실 task내에서는 task간에 연관성이 없고, 독립적이다. 그러면 t라는 시간이 있을 때 t 이전에 발생한 task는 t 이후에 발생한 task와 전혀 연관이 없다고 할 수 있다. 결국 다시 말하면 t 이전의 schedulability는 t 이후의 schedulability와는 상관이 없다는 말까지 할 수 있다. 결국은 Idle Interval이 지난 t 시점을 기준으로 Schedulability를 측정해도 우리가 특정한 수치를 구하는 것이 아니기 때문에 상관이 없다는 것이다. 

 Busy Interval은 schedule이 진행되는 시점간에 task가 점유하고 있는 interval을 나타낸다. 

위와 같은 케이스도 아무리 task가 0부터 시작했더라도 전체적으로 Schedulability를 측정한 것이나, idle Interval이 지난 시점에서 측정한 Schedulability나 똑같다는 것이 기본 전제이다. 거기서 miss가 발생한 가장 최근의 busy interval만 가지고 Utilization을 측정한다면 앞의 케이스에서 언급했던 중간에 짜투리로 남아있던 * 같은 것도 없을 것이다. 즉 쉬운 케이스로 바꿀 수 있다는 것이다. 

지금까지 설명한 것을 적용해보면 위와 같이 START_TIME을 새롭게 정의할 수 있을 것이다. *가 있는 부분, t(a)는 idle Interval에 의해서 생략할 수 있을 것이고, t(a)부터 miss가 발생하는 t까지는 Latest Busy Interval에 의해서 고려하면 되는 것이다. 그러면 처음에 소개했던 케이스처럼 바뀐 것을 볼 수 있다. 그러면 새롭게 정의된 execution time은 다음과 같이 될 것이고,

쉬운 케이스로 설명한 것처럼 이 합이 1보다 크기 때문에 schedulable 하지 않다는 것을 증명할 수 있을 것이다. 

 이로써 Total Utilization이 1보다 크면 Schedulable 하지 않다는 것을 확인했고, 이에 따라서 EDF는 Utilization Bound Check에 의해서 Schedulable 하다는 것을 알 수 있다. 그런데 우리가 다른 포스트에서 언급했던 것처럼 Schedulability를 측정하기 위한 다른 한가지 방법이 있었는데 그게 Time Demand Analysis 였다. 사실 Utilization Bound Check으로 Schedulability를 측정하기에는 제한 사항이 몇가지 있고, 그중에는 이런 Task가 N개 있을 경우 각각의 Idle Interval을 구해서 Utilization을 얻는 것자체가 복잡하다. 그래서 대안적인 방안으로 Time Demand Analysis를 사용하는데 이에 대해서는 다음 포스트에서 계속 이어보고자 한다.