[Study] Critical Instant Theorem

이전 포스트 중에 Reference model의 분류에 관한 내용을 다뤘던 적이 있고, 그중에 우선 순위에 따라 Scheduling model을 결정하는 Priority Driven Approach에 대해서 언급했었다.

그 때 Scheduling에 고려되는 Priority가 Task에 따라서 변경되는지의 여부에 따라서 Static (Fixed) / Dynamic 으로 나눠졌었다. 그런데 과연 이 Priority가 높다고 해서 그 task가 Critical하다고 할 수 있을까? 사실 그 개념이 애매하긴 하지만 지금까지 배운 내용을 되짚어보면 그렇지 않은 예를 찾아볼 수 있다. System Task의 경우 그 task의 동작이 멈춘다면 시스템의 동작에 영향을 준다. 반면 워드 프로세싱이나 인터넷 같은 task는 그냥 비주기적으로 실행하는 task일뿐 system 동작에 영향을 미치지 않는다. 원래 알고 있는대로라면 System Task의 Priority가 높아야 정상이겠지만, 가령 워드 프로세싱의 Deadline이 System Task의 Deadline보다 짧다고 가정하면 어떻게 될까? 이전 포스트에서 다뤘던 Earliest Deadline First 방식을 적용하면 워드 프로세싱의 priority가 더 높게 나온다. 그러니 무조건 Priority = Critical 이라고 할 수 없는 예들이 존재하게 되는 것이다. 

 그래서 realtime system의 요구하는 최종 결과는 importance과 schedulability를 그때그때 알아서 조절할 수 있는 효율적인 Algorithm을 구축하는 것이다. 물론 priority가 높은 걸 먼저 실행시키는 것이 가장 이상적인 실행이지만 어느정도 인정하는 내에서 예외적인 상황도 고려를 해주는 것이다. 

가령 위와 같은 상황에선 정상적이라면 Important Job을 먼저 수행하는 것이 가장 적절하겠지만 상황에 따라서 Less Important한 Job을 먼저 끝내고 다음 중요한 일들을 수행하는 것도 scheduling의 효율성 측면에서 흠을 잡을 수 없을 것이다. 이전과 똑같이 Period 안에 Execution이 발생했기 때문이다.

 사실 가장 좋은 것은 무엇보다도 Flexible 하게 Scheduling되는 것이다. 물론 이를 위해서는 미래에 어떤 task들이 나타날지를 알고 있어야 할 것이다. 가령 위와 같은 importance를 알고 있어야 할 것이고, 상황에 따라서는 deadline도 알고 있으면 좋을 것이다. 물론 execution을 scheduling시 고려하는 factor로 삼는다면, 그 부분도 미리 알고 있어야 할 것이다. 

 그러면 지난 번에 다뤘던 Dynamic Priority Driven Approach 중 하나인 EDF의 Optimality는 증명했었는데 과연 Static Priority Driven은 어떤식으로 Optimality를 고려할 수 있을까? 우선 초점을 맞출 부분은 앞에서 다뤘던 importance이다. 가령 인터넷 서핑 같은 task나 심박동 제어기 같은 task의 순서는 importance에 따라서 구분지을 수 있을 것이다. 그 와중에 예외도 고려할 수 있을 것이다. 만약 기존에 정상적으로 task들이 처리되는 상태라면 굳이 Priority를 Dynamic scheduling의 기준으로 삼지 않아도 될 것이다. 이럴 때는 static Priority Algorithm이 적용되어 있다면 이에 맞춰서 scheduling되는 것을 고려할 수 있다. 

 Reference Model 분류시에도 설명했고 위에도 나왔있다시피 Static Priority Driven Approach에는 크게 두가지 방식이 있다. 첫번째는 바로 Cycle Duration( = Rate)에 따라서 Priority를 정하는 Rate Monotonic (RM)방식이고, 다른 방식은 Deadline의 근접성에 따라 결정되는 Deadline Monotonic (DM) 방식이다. RM에서는 당연히 Cycle이 빨리 도는, 즉 rate가 높은 task가 Priority에 대한 우선권을 가져갈 것이고 DM에서는 상대적으로 Deadline이 짧은 task가 높은 Priority를 가져갈 것이다. 강의에서는 RM의 Optimality에 대해서 비교를 증명하는 게 설명되어 있기에 이를 정리해본다.

 자 그럼 다시 원점으로 돌아가서 Static Priority 방식의 Optimality는 어떻게 구할 것인가? 조금더 범위를 줄여 RM의 Optimality는 어떻게 증명할 것인가. 이전 포스트에서는 EDF의 Optimality는 해당 주기내에서 Deadline에 따라 Swapping을 해보고 그 결과가 schedulable하면 optimal하다고 했다. 그 방법을 RM에 적용해보면 왠지 가능할 거 같지만 그렇지 않다. 우선 RM의 특성상 Rate, Cycle이 빠른 것을 우선적으로 실행시켜주는 방법을 고려해야 되는데 우리가 schedulable이라고 말하기 위해서는 이 task들이 정해진 deadline안에 종료되어야 한다는 것이다. 그러면 결국 RM이 Schedulable한 것을 알아보기 위해서는 매 주기마다 task들이 종료된다는 것을 증명하면 되는데 생각해보면 매우 비효율적인 검증이다. 일이 언제 끝날지 모르는 상황에서 이런 Checking을 위한 모듈이 반복적으로 쓰이는 건 일종의 Resource 낭비이기 때문이다.  

 그러면 생각해볼 수 있는 방법이 그냥 worst case를 고려해보자는 것이다. worst case에 맞춰서 Scheduling을 조절한 후 task들이 정해진 deadline안에 포함되어서 schedulable 하다는 것을 증명하기만 하면 다른 주기에 대해서도 schedulable 하다는 가정에서 시작하는데 이렇게 worst case로 만들어주는 Schedule 조절인자를 Critical Instant 라고 하고 이런 접근 방식을 Critical Instant Theorem (CIT)이라고 한다. 보통 정의는 다음과 같이 이뤄진다.

Critical Instant of T(i) : time of jobs  release of  Task i with maximum response time ( = worst case)

예를 들어보겠다.

위와 같이 Schedule case가 있다.여기서 C(n)이 나타내는 것은 τ(n) 의 release time이고, C(i)는 τ(i) 의 Release Time이다. 당연히 RM에 따르면 τ(i)  의 rate가 더 크므로 τ(n) 에 비해서 priority를 높게 가져갈 것이다. 그런데 위의 Case는 C(n)의 시간동안 모든 C(i)를 담고 있지 않다. 그렇기 때문에 정해진 주기동안 발생하는 C(i)의 정보를 알기 위해서는 그만큼 C(n)도 소비되므로 결론적으로 한 타이밍이 들어가게 된다. 이는 worst case가 아니다.   

 그런데 위와 같이 τ(i) 를 shift 해서 정해진 C(n) 안에 C(i)가 들어가게 한다면 별도로 한번 더 수행할 필요없이 짧은 시간내에 schedulability 를 측정할 수 있을 것이다. 결국 여기선 C(i)만큼 shift를 하는 것이 주어진 Schedule의 worst case가 될 것이다. 그러면 관건은 이 Critical Instant를 어떻게 구하냐는 것이다. 정답은 Task의 Response Time을 구해서 그 시간이 가장 긴 time이 앞에서 정의한 Critical Instance가 되는 것이다. 다음 예제를 보겠다. 

위와 같이 T1,T2,T3가 RM에 따라서 Scheduling되어 있다. 여기 T2의 Critical Instant를 구하려면 어떻게 될까? 바로 T2의 start Time과 T2의 release Time간의 차이가 response time이기 때문에 이 값들을 쭉 구하면 되겠다. 첫번째 r(2,1)은 당연히 처음 시작하는 task이므로 T1이 끝난 후에 바로 실행될 것이다. 그래서 r(2,1) = 0.8이 될 것이고, 다음 r(2,2)는 T1의 Release Time에서 바로 시작하기에 이 값을 고려하면 r(2,2) = ((2.0 +0.6) - 2.5) + 0.2 = 0.3 이 될 것이다. 이와 같은 방식으로 r2에 대한 Response time을 구해보면 위의 화살표같이 나오게 된다. 

r(2,3) = 0.2

r(2,4) = 0.2

r(2,5) = 0.8

....

그러면 여기서 가장 긴 response time이 0.8이 된다. 이 때가 바로 worst case이므로 이 0.8의 response time을 가지는 t =0 , t = 10 이 바로 Critical Instant가 된다. 

여기까지가 간단한 Critical Instant Theorem에 대한 정리였고, 이를 이용해서 RM의 Schedulability를 측정하는 것은 다음 포스트에서 다뤄보고자 한다. 

Reference : 

Wikipedia - Rate Monotonic : (http://en.wikipedia.org/wiki/Rate-monotonic_scheduling)

Wikipedia - Deadline Monotonic : (http://en.wikipedia.org/wiki/Deadline-monotonic_scheduling)

Critical Instatant : (http://www-users.cselabs.umn.edu/classes/Spring-2010/seng5831/lectures/L07_PrioritySched_post.pdf)

Scheduling Periodic Tasks : (http://www.lapis.ece.uvic.ca/RTS/Units/Ch2/framesC2.htm)