[Study] Time Demand Analysis

지난 포스트에서 Task의 worst Case를 통해서 Schedulability를 판단하는 Critical Instant Theorem에 대해서 언급을 했었고, 이번 포스트에서는 그때 구한 방법을 통해서 Rate Monotonic 방식이 Optimal인지를 확인해보는 과정을 정리해보고자 한다.

 우선 전에도 쓴 내용이겠지만 Optimality를 증명하는 것은 즉, 어떤 task Schedule이라도 특수한 Algorithm을 거치면 RM-based Schedule로 바꿀 수 있다는 것을 보여주기만 되는 것이다. 하지만 Static-priority에서는 그 task의 주기마다 deadline과 만나는지를 검증하는 단계가 있어야 하고 그 걸 확인하기 위해서는 매 주기마다 task를 검증하는 불필요한 과정이 있었다. 이를 위해서 가장 긴 한 주기동안의 task schedule의 worst case 즉, 같은 시간동안 respone time이 가장 긴 경우만 고려하자는 Critical Instant Theorem을 적용하면 나머지 주기에 대해서는 고려할 필요가 없어진다고 했었다. 이 말을 그대로 한 예제에서 확인해보겠다.

다음과 같이 두가지 task가 있고, 여기에는 RM에 따른 Priority가 고려되어 있지 않다. 지금 보면 J2들은 task들이 deadline이 시작하는 시점에서 일정 시간동안 Execution이 발생하는데 J1은 어떤 규칙을 지니는지 감을 잡을 수 없다. 아무튼 정해진 schedule내에서 deadline miss가 나지 않으므로 feasible 하기는 하다. 이걸 RM으로 바꿀 수 있으면 우리는 RM이 Optimal하다는 것을 보일 수 있을 것이다. 그럼 Critical Instant Theorem에 따라서 정해진 task의 주기내의 worst case를 찾아보면 J22와 J12,J13가 만나는 주기가 될 것이다. 이걸 sample로 보고 변경해본다.

지금 표현은 J21,J11,J12로 되어 있지만 원래 위의 J22,J12,J13가 변해서 위와 같이 표현된 것이다. 아무튼 여기서 중요한 것은 두 Schedule의 Start Time을 일치시켜야 한다는 것이다. 그럼 지난 포스트에서도 Static Priority의 Schedulability를 측정하는 방식 중 하나였던 Swapping Trick을 적용해본다.

이렇게 J11과 J21를 Swapping해보고 Deadline miss 여부를 확인해보면 된다. 보다시피 

J21 + J11 = J11 + J21 = t < D1 <D2

이기 때문에 J11과 J21은 항상 Deadline안에서 실행된다는 것을 알 수 있고 이 때문에 Scheduable 하다고 할 수 있다. 그리고 CIT에서 설명되었던 것처럼 이런 패턴이 가장 worst case이기 때문에 나머지 Task에 대해서는 당연히 scheduability가 보장된다고 말할 수 있다. 

 그러면 의문을 가질 수 있다. 과연 위에서 언급한 J22, J12,J13가 이 task 중에서 worst Case라고 할 수 있는지 말이다. 적어도 위에서 제시한 task 내에서는 맞다고 할 수 있다. 하지만 그런 의문점에서도 나올 수 있다시피 worst case를 구하기 위해서는 최소한 worst case가 나올 때까지 검증하는 과정이 필요하다. 우리가 worst case라고 평가할 수 있는 요소가 바로 기존에 얻어진 data를 통해서 나오기 때문이다. 그래서 Scheduable 하다는 말은 적어도 worst case가 나타난 시점을 전후해서 언급할 수 있을 듯 하다. 아무튼 지금과 같이 정해진 시간에 대해서 critical instant를 통해 schedulability를 측정하는 방식을 Time Demand Analysis 라고 한다. 즉 Critical Instant 시점에서의 job을 통해서 task가 처리되는 process time의 demand를 계산하는 걸로 요약할 수 있다. 조금 말이 어렵긴 한데, 이 time Demand Analysis function은 다음과 같이 제시된다.

Worst Case가 발생하는 주기 p(i) 내에서의 Execution time과 higher-priority job의 total Execution time을 더한 값이 결국은 process time demand가 되는 것이다. 굳이 한국말로 번역하면 process되는 요구되는 최대 시간? 정도로 이해하면 좋을 듯 하다. 당연히 이렇게 구한 W(t)가 Deadline내의 t값보다 크다면, 즉 W(t)가 p(i) 보다 크게 된다면 이 방식은 Schedulable하지 않다고 말할 수 있을 것이다. 참고로 위의 수식에 나오는 bracket은 t/p(k)보다 큰 최소 정수값이다. 이 포스트에서는 편의상 [  ] 으로 표시하고자 한다. 그럼 위의 식을 토대로 예제를 다시 보겠다.

자 위와 같이 Task들이 나열되어 있고, 이 Task들의 Schedulability를 측정하려고 한다. 그러기 위해서는 지난 포스트에서 풀었던 예제처럼 각 task의 response time을 구해봐야 한다. 우선 지금 task 3의 schedulability를 측정하는 것이므로 task 3의 각 timing에 대한 resopnse time을 구해본다.

 그러면 첫번째 job 끼리만 비교해 보면 r(3,0)은 e1+e2+e3이므로 18이라는 값이 나오게 된다. 일단 이렇게 나열해도 p3보다 작기 때문에 schedulability가 유지된다. 

그러면 두번째 job은 어떻게 구할까? 이때 앞에서 소개한 time demand function을 활용하면 된다. 그러면 수식이 다음과 같이 제시된다.

역시 이 값도 작다. 다음 세번째 case도 구해보면 역시 p3보다 작다.

그런데 유심히 봐야 할 것은 Task 3의 Execution이 모두 종료 되었다는 것이다. 즉 여기서 i값을 증가시켜봤자 이 30이란 값에서 더 올라가지 않을 것이라는 말이다. 그러면 결국 한주기 동안 비교했을 때에도 D3를 넘지 않기 때문에 Task 3는 Schedulable 하다 라고 말할 수 있겠다. 바로 여기에 이전 포스트에서 잠깐 설명했던 Critical Instant Theorem이 포함되어 있는 것이다. 즉, higher priority의 task들이 동시에 시작한다고 가정했을 때 첫번째 Deadline안에 task가 종료된다는 것만 증명하면 이 Task가 항상 Schedulable 하다는 것이다. 이 내용이 RealTime System 교재의 저자인 Liu 교수가 1973년에 소개한 "Scheduling algorithms for multiprogramming in a hard real-time environment"  에서 게시되어 있다. 참고로 이 때 Rate-Monotonic이라는 개념이 등장했고 그 때문에 RM Scheduling을 Liu-Layland Scheduling이라고 하기도 한다. 

 그러면 다시 문제로 돌아가서 지금 구한 값이 Time Demand Function이므로 그걸 하나의 그래프로 묘사할 수 있을 것이다. 

대각선이 time function인데 Time demand function은 해당 주기마다 측정이 되기 때문에 위와 같이 step function으로 나타난다. time function과 time demand function이 만나는 교차점이 Critical Instant이고 이 값이 p3보다 작은 걸 확인할 수 있다. 

 지금까지 Time Demand Analysis에 대해서 정리해보았다. 지금 보면 알다시피 RM이 소개된 부분에서 이 time demand analysis가 나온 것이지, priority가 정해진 fixed priority scheduling에서는 이 방식을 이용해서 schedulability를 증명할 수 있다. 그런데 앞에서 언급했다시피 worst case를 파악하는 과정에서 구조가 복잡하다. 그래서 이를 대체할 수 있는 방법으로 제시된 것이 바로 Utilization Bound Checking 이라는 건데 이건 execution time과 period만 가지고 해당 task의 schedulability를 구하는 것이다. 이에 대해서는 다음 포스트에서 계속 정리해보려고 한다.