[Real Time] Schedulability of Earliest Deadline First Using Time Demand Analysis

지난 포스트에서 이야기 했던 것처럼 N개의 Task에 대해서 Utilization를 측정하는 것이 어렵기 때문에 이에 대안적인 방안으로 Time Demand Analysis를 쓸 수 있다고 했다. 간단히 요약하자면 각 Task의 Response Time을 측정해서 그때의 Time Supply보다 큰가 작은가를 비교하면 Schedulability 를 얻을 수 있다는 것이다. 그런데 아마 Time Demand Analysis에 대해서 기억하는 사람이 있다면 이 접근 방식의 문제를 알고 있을 것이다. 바로 모든 Case에 대해서 다 구해야 한다는 것, 매 period마다 Schedulability를 측정하기 위해서는 response time을 재야 하고 이를 위해서는 무한적으로 측정해야 한다는 답이 나온다. 물론 그때는 Critical Instant Theorem이라는 방법을 적용해서 딱 한번 측정하면 Schedulability를 잴 수 있다고 했었다. 그러면 지금과 같이 EDF의 Schedulability를 잴 때는 이 방법을 활용할 수 있지 않을까? 

 사실 지금은 Utilization을 재는 것이기 때문에 Critical Instant Theorem의 방법은 전혀 상관이 없다. 이 때 적용할 수 있는 방법은 바로 Execution이 일어날 때를 취합해서 그 중에서 Worst Case를 뽑아보자는 것이다. 즉 EDF Scheduling이 적용되는 system 내에서 Worst Case pattern을 찾아보자는 것이다. 다시 말하자면 Critical Instant Theorem은 처음의 response time이 supply time을 넘어서는 시점만 구하면 되는 접근 방식이고 위에서 소개한 Worst Case Pattern은 모든 task를 수행하되 그 중에서 가장 worst한 case를 찾자는 것이다. 여기서 차이가 있다. Critical Instant Theorem을 통하면 어떤 시점에서 어떤 task가 miss가 발생했는지를 알 수 있지만 Worst Case Pattern은 그냥 단순히 miss가 발생했다, 아니다의 정도로만 구할 수 있다. 

자 위와 같은 task들이 나열되어 있다. 여기서 Worst Case Pattern을 뽑아낼 수 있느냐가 관건인데. 방법은 Start Time을 동일하게 맞춘 상태에서 EDF에 맞춰서 task를 재분배하는 것이다. 결국 EDF니까 Deadline이 가장 빠른 것 순서대로 Priority를 매기면 된다. 그러다보면 deadline이 발생하는 케이스가 나타난다. 

이때가 worst case pattern이며 Time Demand Analysis에 따라서 response time과 period를 비교하면 되겠다. 

그러면 이를 활용해서 예제를 풀어본다. 다음과 같은 3개의 task가 존재하는데 이에 대한 schedulability를 측정해본다. 

당연히 Total Utilization을 구해보면 1.18로 나오고 EDF식으로 따지면 Schedulable하지 않다. 그러면 언제 miss가 나는지는 확인을 해보면 된다. 

우선 Time Supply가 4인 상태라면 D[0,4]를 구하면 되고 이 값은 실제로 구해보면 3이 나오기 때문에 이 시점에서는 Schedulable하다. 다른 Periodic time에서도 각각의 Response time을 구해보면 다음과 같다.

결국 Time Supply가 14일 때 Response Time이 Supply를 넘어서게 되므로 miss가 발생하게 된다. 

그럼 이런식으로 Schedulability를 보여줘도 되는지는 간단한 증명을 통해서 가능하다. 우리가 Utilization을 구할 때는 다음과 같은 수식을 사용했다.

이걸로

위의 수식과 동등하다는 것만 보여주면 되는 것이다. 그런데 의외로 간단하다. 모든 Time supply 내에서는 U가 1보다 작거나 같다. 그러면 두번째 결과식에 U를 곱해도 부등호는 변하지 않을 것이다. 그러면 최종적으로

이렇게 얻을 수 있을 것이고, 어차피 bracket의 의미가 low bound를 나타내기 때문에 우변의 부등호 또한 변하지 않게 된다. 그러면 이에 대한 반대 case인 U<1인 상황이라면 당연히 부등호도 바뀔 것이고 이 때는 다음과 같이 정의될 것이다.

참고로 이때의 L은 p1,p2,p3 ... p(n) 의 최소공배수를 의미하며 수식으로는 lcm(p(1),p(2),p(3) ... p(n)) 라고 표현한다. 그리고 다른 말로는 hyper-period라고도 한다. 결국 period의 최소 공배수를 구하고 이 때의 response time을 구해서 비교함으로써 Schedulability를 측정할 수 있는 것이다. 

 사실 Time demand Analysis를 통해서 schedulability를 측정하는 방법이 조금 까다롭긴 했지만 확실히 Utilization Bound Check에 비해서 가지는 강점이 있다. 바로 모든 상황에서 검증할 수 있다는 것이다. 다른 포스트에서 봤겠지만 Utilization Bound Check을 하기 위해서는 반드시 Period가 Deadline보다 작거나 같아야 한다. 그런데 Time Demand Analysis를 적용하면 deadline이 period보다 작은 케이스에서도 검증할 수 있다는 장점이 있다. 

즉 위와 같이 Deadline이 period보다 짧은 case에서도 Schedulability를 측정할 수 있다. 다만 이때는 이전에 사용했던 Time Response function을 그대로 쓸 수 없다. Deadline이 Function에 미치는 영향도 고려해야 되기 때문에 처음부터 발생한 Deadline을 빼주고 시작하게 된다. 그래서 

시작점을 달리 해준 상태에서 analysis를 수행하게 된다. 물론 Function도 다음과 같이

바뀌게 될 것이다. 그런데 이렇게 하면 전체 Task Execution Time을 측정하는데 하나가 빠진 형태가 되므로 이를 보정해주기 위해서 1을 더해주게 된다. 최종적으로는 

요약하자면 period보다 짧은 deadline을 가진 task 들이 있을 때 response time이 Time Supply보다 작으면 Task들이 Schedulable하다는 것을 알 수 있었다.