[Real Time] Effective Release Time / Deadline

지금까지 계속 EDF와 RM의 Optimality 혹은 Schedulability를 확인하는 내용을 다뤘었다. 그런데 사실 이렇게 구한 값들이 실제 케이스상에서도 적용할 수 있는 값일까 하는 의문을 가질 수 있다. 만약 그게 가능하다면 앞으로 Task Scheduler를 설계할 때는 이미 구해놓은 utilization이나 Release Time만을 활용하면 쉽게 설계할 수 있다. 하지만 공학을 설계한 사람이라면 누구나 알다시피 이론과 실제 케이스는 너무나 큰 차이를 나타낸다. 이론에 나온 것은 단순히 실제 케이스들 중에서 제한 사항을 엄격히 설정한, 아주 특이한 케이스 인 것이다. 

 실제로 이전의 EDF나 RM의 Optimality를 측정할 때도 언급하지는 않았지만 우리는 무언의 제한을 두고 있던 것과 같았다. 우리는 Task들이 항상 Preemptive 하고 생각했으며, Task간의 Resource가 전환되는 현상인 Context Switch 간에 발생할 수 있는 Overhead에 관해서는 신경쓰지 않았다. 또한 지난 포스트 마지막에서만 나온 내용이지만 전반적으로 Deadline이 Period보다 같거나 클 때만을 고려해서 Scheduability를 측정했다. 

 따라서 실제로 적용하기 위해서는 다음의 사항들을 추가적으로 더 고민해봐야 한다.

- 만약 Deadline이 Period보다 짧으면 어떻게 Schedulability를 측정할까?

- 만약 지금과 같은 Preemptive task만 있는 것이 아니라 Kernel 상에서 동작하는 System Call 같은게 호출(e.g Non-Preemptive Code Section)되면 어떻게 측정할까?

- 만약 Task Switching간에 Overhead가 발생하면 어떻게 처리할 건지...

이런 것들에 대해서 조금 더 생각해볼 필요가 있어 이 포스트를 통해서 조금 전개해보고자 한다. 

그전에 잠깐 나온 Non-Preemptable code Section (NPS)에 관해서 언급하자면, 말그대로 Preemptive를 허용하지 않는 영역을 나타나는 것이다. 다르게 표현하면 Task가 수행되고 있다고 하더라도 이 Non-Preemptive Code Section이 호출되면 이걸 우선적으로 처리하겠다는 것이다. 그래서 앞에서 잠깐 나온 System Call이 대표적인 예이다. System Call은 자체적으로 Kernel Mode에서 수행되기 때문에 그 어떤 Task보다도 High Priority를 가진다. 그래서 이 NPS가 적용된 Task는 수행되고 있는 timing동안은 task가 보장된다. 

 물론 다른 때는 상관없겠지만 우리가 신경써야 할 부분은 low priority task가 이 NPS로 구성되어 있을 때이다. 앞에서 언급한 것처럼 task에 대한 우선을 가지고 가기 때문에 어떤 high priority task가 개입한다 하더라도 low task는 계속 수행된다. 즉, block을 시킨다는 의미이다. 

 그러면 이제 관심을 가지는 건 만약 이 NPS가 포함된 Task Scheduling에서는 어떤 방법으로 Utilization Bound를 측정하냐는 것이다. 이걸 측정할 수 있어야 해당 Task도 Optimal한지를 알 수 있는 것이다. 이 때 Utilization Bound는 다음과 같이 계산할 수 있다.

결국 Preemption 에 따른 Deadline의 변화가 발생하기 때문에 그 값에 따라서 execution time이 바뀔 것이다. 당연히 그런 변화에 대해서 deadline도 상대적인 값으로 측정해야 될 것이다. 그러면 이를 활용해서 Utilization Bound Check을 통한 Schedulability를 구해볼 수 있다. 그 결과는 다음과 같다. 

어차피 Utilization을 측정하기 위해서는 매 period 마다의 Utilization을 측정해야 되는데 해당 task 내에는 앞에서 언급한 NPS가 포함되어 있다고 가정했을 때 NPS가 포함된 영역의 Utilization값과 기존의 Utilization 의 값의 합이 적어도 EDF의 Utilization Bound인 1보다 작아야 Schedulable 하다고 할 수 있을 것이다. 물론 이걸 확장시켰을 때는 측정된 NPS의 Utilization b(j) 값이 가장 큰 때가 Utilization Bound Check을 이용한 Schedulability 계산에 이용된다.

 그런데 지금까지 전개한 것은 Deadline과 Period가 같다고 가정했을 때의 전재방식이고 당연히 Deadline이 Period보다 작은 경우에는 다음과 같이 수식이 변할 것이다.  

그런데 한번 생각을 해보자. 만약 Deadline이 Period보다 짧은 경우를 가정한다면, 어느 순간인가 Execution Time이 deadline을 miss하는 경우가 발생할 것이다. 우리가 원하는 것은 그런 miss가 나는 케이스가 아니므로 사전에 이에 대한 제한을 정해두게 되는데 이를 보통 Precedence Constraint 라고 한다. 말 그대로 Task의 execution order를 정해두고 그 순서에 따라서만 수행되게끔 하는 것이다. 다시 말하자면 Task의 Predecessor와 Successors 를 정해두고 그에 대한 execution order를 미리 정해보자는 건데, 당연히 Preemption에 대한 문제도 이 규칙을 따르게 된다. 

당연히 무작정 execution order만 지정하는 것이 아니라, 그 변화한 후에도 execution 의 효율성을 위해서 Timing Parameter들을 수정해줘야 한다. 이 때 이런 수정값들을 Effective Release Time / Effective Deadline이라고 한다. 그럼 이 값들을 어떻게 구하냐가 다음에 알아볼 내용이다.

위와 같이 J(a)와 J(b)가 있다. 각각의 execution time(C(a), C(b))과  deadline(d(a), d(b))이 정해져 있는 상태에서 앞에서 언급한 precedence constraint가 d(a) -> d(b)로 정해져 있다고 가정하자. 

그러면 J(b)의 Release time인 r(b)는 어떻게 구할 수 있느냐가 이 예제의 목적이다. 그런데 앞에서 언급한 것처럼 precedence constraint가 결정된 상태에서는 당연히 J(a)가 수행되고 난 후에야 J(b)를 수행할 수 있다, 그렇기 때문에 r(b)의 time은 다음과 같은 수식으로 정의할 수 있게 된다.

 Effective Release Time r(b) = max ( r(b) , r(a) + C(a))

 Deadline도 똑같다.

똑같은 Precedence Constraint가 존재하는 상태에서 J(a)의 Effective Deadline은 다음과 같이 정의할 수 있다.

Effective Deadline d(a) = min ( d(a) , d(b) - C(b))

위의 경우는 단순히 Task 2개가 있는 상태에서 구한 Effective Value이지만 여러개의 Task가 있는 경우에도 Precedence Constraint를 파악한 후 각각의 effective Value를 구한 후 다른 Job의 경우를 iterative 하게 구하면 된다. 

 그런데 지금 이런 과정을 수행하면서도 우리는 암묵적으로 EDF에 따르고 있다는 것을 알 수 있다. EDF의 정의 대로 Deadline에 가까운 Job이 먼저 수행되고 timing Value가 변하는 것이다. 이 말은 다르게 표현하면 이렇게 Effective Value를 적용해서 Release Time과 Deadline을 변화시켜도 Schedulability가 유지된다는 것이다. 물론 Schedulable을 증명하기 위한 Swapping Trick도 적용할 수 있다. 그래서 다음과 같은 Theorem이 나오게 된다.

 If there exists a feasible schedule ( meet all release times, deadlines, precedence constraints), effective EDF schedule( EDF schedule with effective release time and deadlines) is also feasible

 그럼 이제 effective EDF의 optimality를 증명하면 위의 Theorem이 맞다는 것을 확인할 수 있겠다. 

위와 같이 J(1)과 J(2)에 대한 Precedence Constraint가 존재하고 Feasible Schedule이 형성되어 있다. 일단 J(1)의 effective deadline과 J(2)의 effective release time을 구해볼 수 있다. 

d(1) = min ( d(1) , d(2) - C(2))

r(2) = max ( r(2) , r(1) + C(1))

이제 Schedulable을 측정하기 위한 Job Swapping을 수행하면 다음과 같이 된다. 

이렇게 하면 r(1)과 r(3)간에 deadline miss가 발생하지 않기 때문에 schedulable이 유지된다. 이제 관건은 J(2)와 J(3)간의 연관성인데 여기서도 똑같이 Job Swapping을 수행하면 알 수 있다. 그러면

역시 이렇게 바꾼 후에도 Deadline miss가 발생하지 않기 때문에 역시 J(2)와 J(3) 사이에도 schedulable이 유지된다. 

자.. 결국 NPS가 포함된 Schedule을 처리하기 위한 Precedence Constraint도 이렇게 Effective Value를 구해서 Deadline과 Release Time을 변경시키면 Schedulability가 유지 되는 것을 볼 수 있었다. 그러면 여기까지만 고려해보면 Dynamic Priority Based Scheduling, 더 나아가보면 EDF가 이런식으로 유연하게 대응할 수 있으므로 좋은 Solution이라고 생각할 수 있다. 하지만, 정말 scheduling 알고리즘을 접하다보면 EDF 방식을 쓴 형태가 생각보다 드문 것을 알 수 있다. 사실 EDF의 단점이라고 하는 것은 태생적으로 Priority가 가변적이기 때문에 Deadline miss가 발생했을 때에 대한 합리적인 해결책이 없다는 것이다. 그렇다고 task가 수행되는 동안 그걸 계속 추적해서 일일히 miss가 발생하지 않도록 scheduling 하는 것 자체도 resource가 발생하는 요인이기에 오히려 Static Priority Based Scheduling이 많이 사용되고 있다. 

 물론 최근에는 이런 연구도 많이 진행이 되서 가령 Feedback Controller를 달고 deadline을 조금더 soft하게 만드는 방법까지 나온 거 같다. 이 부분이야 조금더 공부를 하다보면 더 자세히 알 수 있지 않을까 싶다...