[Study] Utilization Bound Check

이전 포스트를 통해서 Schedulability를 측정하는 방법 중 하나인 Time Demand Analysis를 소개했고, 그걸 Xenomai 상에서 검증하는 과정을 보였다. 우리가 이렇게 Schedulability에 신경쓰는 이유가 무엇일까? 바로 지금 우리가 다루는 것이 Real Time OS이기 때문이다. formal한 OS와 RTOS와의 차이는 Deadline이 Task 처리시 어떻게 작용하냐는 것이고, 특히 RTOS에서는 보통 Deadline이 task scheduling에서 중요한 요소로 고려된다. 즉, task가 적절하게 scheduling이 되지 않아서 발생하는 miss는 시스템의 동작에 치명적으로 작용할 수 있다는 것이다. 그래서 task에 대한 execution time과 period를 측정하는 것이 중요하다.

 그럼 왜 지난번에 사용했던 Time Demand Analysis말고 다른 방법인 Utilization Bound Checking을 하려는 것일까? 내가 생각하기엔 식이 너무 복잡하다. 다시 Time Demand Function을 살펴본다.

 여기서 Response time을 구하려고 하면 항상 전자에 해당 job의 execution time이 들어간다. 그런데 우리가 정확한 Response time을 구하지 않는 한 이렇게 더하고 빼는 것 자체가 의미가 없지 않을까? 단순히 이렇게 구한 값 자체가 Period보다 작다는 것만 보여주면 해당 task가 schedulable 하다는 것을 보일 수 있기 때문이다. 실질적으로 초점을 맞춰야 하는 것은 해당 task의 execution time과 period 일 것이다. 보통 해당 period 내에서 execution time의 비중이 얼마나 되느냐에 따라서 system의 효율성이 얼마나 되느냐를 판단하곤 한다. 그래서 이 값을 schedulability의 factor로 넣는게 바로 Utilization(효율성) Bound Check의 기본적인 접근이다. 

 앞에서 언급한 것처럼 Utilization 자체는 다음과 같이 period 내에서 execution time의 비중을 가지고 구한다. 그런데 우리가 따져야 할 것은 전체 task에 대한 Total Utilization 값이므로 이 값은 다음과 같이 구할 수 있을 것이다.

여기서 C는 execution time이고 p가 period가 되는데 즉 total utilization이라는 것은 전체 job의 Utilization에 대한 sum이라고 보면 될거 같다. 

 일단 period 내에 execution이 일어나는 것을 schedulable 라고 할 수 있기 때문에 total Utilization U는 항상 1보다 작아야 할 것이다. 그리고 이 값이 작으면 작을 수록 그만큼 Schedulability를 보장할 수 있을 것이다. 그러면 어떻게 이 값을 가지고 Schedulability를 판단할 수 있을까?  정답은 이렇게 구한 Utilization 중에서 가장 minimum(Minimum Utilization)한 값을 찾자는 것이다. 

 이전 포스트에서 다뤘던 것처럼 feasible을 증명하는 기본적인 원칙은 아무 규칙이 없는 task들을 scheduling algorithm을 통해서 변환했을 때도 schedulable 하다면 우리는 해당 해당 algorithm을 optimal하다고 했다. 여기에 Utilization 개념을 집어넣어서 algorithm을 적용한 task의 Utilization의 minimum 값이 원래 task의 Utilization 보다 크다는 것만 보이면 해당 algorithm은 optimal하다고 표현할 수 있을 것이다. 결국 수식으로 표현하면 다음과 같이 되는 것이다. 

그러니까 우리는 minimum Utilization을 구하는 것이 목적이 될 것이고, 이걸 다른 말로 Utilization Bound라고 한다. 그래서 앞에서 말한 방법들을 통칭해서 이 값이 넘는지 안 넘는지를 검사하는 과정을 Utilization Bound Check이라고 한다. 결국 반복해서 말하자면 Utilization Bound를 구하는 게 최종 목적이 될 것이다. 그림으로 표현하면 다음과 같다.

위와 같이 Task에 대한 각각의 Utilization을 구했다. 정상적인 Scheduling이 된 task라면 당연히 period보다 execution time이 짧기 때문에 Utilization이 1보다 작을 것이다. 자 그럼 새로 들어온 Task의 Schedulability를 유지하기 위해선 어떤 Utilization을 Bound로 삼아야 할까? 

 다시 돌아보자면 Utilization은 Period와 Execution Time의 비율이다. 그러면 같은 period라고 가정했을 때 execution time이 짧을 수록 해당 task의 execution time이 짧을 것이다. 반대로 이 값이 길면 그만큼 execution time도 클 것이다. 그러면 Scheduling Algorithm의 Optimal을 증명하기 위해서 각 Task에 대해서 Swapping을 해본다고 치자. 그러면 어떤게 유리할까? 당연히 이 Utilization Bound가 가장 작은 것이 Schedulability가 보장되는 가장 최적의 Task가 될 것이다. 이런 연유에서 가장 minimum한 Utilization을 Utilization Bound로 정한다. 그래서 내가 볼때는 위에 표현된 그래프의 길이보다는 1에서 그래프의 길이를 뺀 여백의 공간이 그만큼 Schedulability를 표현하는 척도가 아닐까 싶다. 결국 이 Utilization 보다 짧다는 것은 그만큼 period에 대한 execution time이 짧기에 나머지 Task에 대해서도 Optimal 하다는 것을 보장하기 때문이다. 

 자 그럼 이걸 지난 포스트 중에 다뤘던 Earliest Deadline First 에 적용해보자. 그때도 증명했었지만 EDF 방식은 Preemptive 하고 Uniprocessor인 환경 상에서 모든 Task에 대해서 Optimal하다. 여기에 Utilization을 적용해 보면 모든 task에 대해서 schedulable 하기 때문에 EDF 방식의 Utilization Bound는 1이라고 할 수 있다. 위에서 제공된 수식에 의해서도 task set들이 schedulable하다는 것을 보일 수 있다. 그런데 여기서 간과한 부분이 있을 수 있다. 지금 우리가 EDF의 Schedulability를 증명할 때 언급하지 않은 전제가 있는데 그게 바로 Period가 Deadline보다 짧다는 것이다. 우리는 보통 reasonable한 system을 고려하기 때문에 EDF를 증명할 때도 기본적인 전제가 Deadline이 period 뒤에 있거나 같다는 것이었다. 그런데 만약 period가 Deadline보다 길면 어떻게 될까?

 위의 예제에서 T1과 T2에 대한 Total Utilization을 구하면 0.8/2 +2.3/5 = 0.86 이라는 값이 나온다. 이건 앞에서 말한 EDF의 Utilization Bound인 1보다 작기 때문에 이 Task들은 EDF에 대해서 optimal 하다고 말할 수 있어야 한다. 그런데 보면 보다시피 T2의 Deadline이 3으로 잡혀있고, J(2,1)이 3보다 더 먼저 시작했다는 것을 확인할 수 있다. 즉, deadline에 대해서 miss가 났다는 것이다.결국 이럴때는 Utilization Bound를 통한 Schedulability를 측정할 수 없다. 다시 한번 말하지만 Utilization Bound Check을 하기 위한 가장 기본적인 조건은 Deadline이 Period보다 작을 때만 성립한다는 것이다. 그럼 여기서 Time Demand Analysis와의 차이를 볼 수 있다. 분명 Utilization Bound Check을 하면 단순히 execution time과 Period만 구하면 간단히 유추할 수 있기 때문에 simple하지만 위와 같은 제한 조건이 존재한다. 반면 Time Demand Analysis는 중간에 response time을 구하고 이 결과와 period와 비교해서 schedulability를 구하는 형식이므로 조금 복잡하긴 하지만 그걸 구하는 데 있어서 제한 조건이 없기 때문에 조금더 general하게 구할 수 있다. 

 아무튼 Dynamic Priority Based Scheduling인 EDF에서는 Utilization Bound가 1이라는 것을 알고 있기 때문에 모든 Task에 대해서 optimal 하다고 증명할 수 있었는데 그러면 Static Priority인 Rate Monotonic이나 Deadline Monotonic 방식의 Utilization Bound는 얼마일까? Static Priority 에서는 사전에 Priority가 정해지므로 분명 EDF에 비해서는 작을 것이다. 그럼 과연 어느 정도의 Utilization까지 감당할 수 있는지는 다음 포스트에서 조금더 정리해보고자 한다.