[Real Time] Liu & Layland Bound

계속 이어서 Utilization Bound Check을 다뤄보려고 한다. 일단 간단히 요약하자면 우리는 task들을 보면서 해당 task의 execution time과 period를 구할 수 있다. 이를 바탕으로 Utilization이라는 것을 구할 수 있었는데 System내에서도 task가 여러 개이기 때문에 Utilization들을 모두 합친 Total Utilization을 얻을 수 있을 것이다. 이 값과 Scheduling algorithm을 적용한 후의 Utilization의 최소값, 즉 Utilization Bound와 비교를 통해서 Schedulability를 측정하는 방식이 지난 포스트에 언급한 Utilization Bound Check의 내용이었다. 그래서 이번에는 실례를 통해서 다시 정리해보려고 한다.

 자 그럼 이제 생각해볼 수 있는게 일단 schedulable하다는 것을 알았으니까. 어느 정도까지 그 schedulability를 유지할 수 있을지 minimal utilization factor를 구하는게 다음 과정이 될 것이다.

 

이렇게 task가 두개 있다. 이 system의 Total Utilization은 당연히 2/3 + 2/7 이 될 것이다. 여기서 어느정도 job에 대한 execution time을 변화시켰을 때 간신히(barely) schedulable할 수 있을까? 이 때의  Minimal Utilization은 어떻게 될까? 그럼 다음과 같이 그 변화량을 Δ 라고 가정했을 때의 Total Utilization을 구해보면 된다.

 

이 때의 Total Utilization U는 

U = 2/3 + 2/7 - Δ /3 + 2 Δ /7  = (2 -  Δ )/3 + (2 + 2 Δ )/7   

이 될 것이다. 여기서 각 Task의 첫번째 주기만을 고려했을때는 Task 1은 3/Δ 만큼 감소한 꼴이고 Task 2는  2 Δ /7 만큼 증가한 형식이 된다. Δ 값에 따라 달라지겠지만 전체적으로 봤을 때는 Utilization 이  Δ /21 만큼 감소한 것으로 보인다. 그러면 여기서 Δ 를 1이라고 가정을 하고 Task 1의 Period를 증가시키면 어떻게 될까? 가령 이런 것이다.

  

이 때의 Utilization은 

U = 1 / 6 + (4 + 1)/7

이 되겠고, 이때도 증가한 양과 감소한 양을 비교해보면 증가량이 1/7 만큼이고, 감소량은 1/6이다. 전체적으로는 1/42 만큼 감소한 것이다. 그런데 여기서 뭔가 규칙이 있는 것을 볼 수 있다. 위의 예제에서는 볼 수 없었지만 이번 예제에서는 우연하게도 증가량과 감소량이 Period와 연관되어 있다. 그러면 Execution Time을 배제하더라도 Period만 가지고(단 Rate Monotonic 이라는 가정하에...) Minimal Utilization을 구할 수 있지 않을까 하는 것이 지금 접근하는 방향이다.

위와 같이 Task 1과 Task 2가 있다.(Period, Execution time)으로 표현했을 때 Task 1은 (4,2), Task 2는 (10,4) 가 된다. 이때 p2는 e2에 대한 time demand function으로 다음과 같이 구할 수 있다. 

여기서 위에서 한대로 Minimal Utilization을 구하기 위해서 p1의 주기를 두배로 늘려보면 식은 다음과 같이 변할 수 있다.

그럼 이 값이 같기 때문에 어떤 것이 더 큰지를 비교할 필요가 있다. 그래서 첫번째 식에서 두번째 식을 빼보면 다음과 같은 결과를 얻게 된다.

현재 p1은 4, p2는 10이기 때문에 당연히 나온 결과는 위 시스템 상에서는 0보다 크게 될 것이다. 즉, 위 시스템에서는 p2가 2p1보다 크다는 것을 증명하면 schedulable을 증명할 수 있는 것이다. 그럼 이걸 조금더 일반화를 해보면 된다. 만약 k라는 factor가 있고 p1과 p2의 비율이 k라고 가정해보자.

지나간 포스트에서 잠깐 언급했듯이 위의 bracket은 안의 값을 넘는 최소 정수를 나타낸다고 했다. 결국 저 식을 풀어서 나열하면 

와 같이 구할 수 있을 것이다. 역시 이 값을 고려해서 p2에 관한 식을 변형시켜보면 위의 예제에서 나온 것처럼

이었던 식이 k배만큼 주기를 늘리면 

이런식으로 일반화할 수 있을 것이다. 

자 역시 두 식 모두 p2를 가리키므로 두 값을 빼보고 어떤 값이 큰지 비교해보면 된다. 그러면 결과가.

와 같이 나오는데 앞에서 증명했다시피 p2와 (k-1)p1에 관한 식이 정립되었기 때문이 위의 결과는 항상 0보다 클 수 밖에 없다. 

이 결과가 시사하는 바는 결국 p1과 p2의 period ratio가 Utilization을 측정하는데 중요한 요소였다는 것이지, execution time은 minimsl Utilization을 측정하는데 period 들로 대체할 수 있다는 것이다. 그대신 조건이 있다. execution time은 항상 period에 대해서 넘지 않아야 하며, 적어도 low priority를 가진 task의 period가 high priority를 가진 task의 것보다는 2배이상 커야 한다는 것이다. 이에 대한 증명을 앞에서 쭉 한 것이다.

 그러면 극단적으로 이런 케이스를 들 수 있다. 

자 그럼 Task 1의 Execution Time은 위에서 보다시피 p2-p1으로 구할 수 있을 것이고 마찬가지로 e2 = p3 - p2 가 될 것이다. task 가 여러개 있다고 가정했을 때 e(n-1) = p(n) - p(n-1) 이라고 할 수 있을 것이고 e(n)은 다음과 같이 유도할 수 있다.

결국 e variable을 p variable로 표현할 수 있다는 것이다.

이제 전체 System의 Total Utilization을 구해보면 어떨까? 그때도 말했지만 Utilization은 Execution Time과 Period의 비율을 나타낸다. 그러면 위의 수식을 이용해서 execution time을 period로 대체해본다.

 

그리고 나서 통분해보면 다음과 같은 결과를 얻을 수 있다.

이 때부터 각 r값에 대한 Partial Differential Equation, 즉 각 요소에 대한 편미분을 구해보면 된다.

당연히 Utilization 을 편미분하면 0이 될 것이고 이 모든 경우를 다 구해보면 다음과 같은 결과를 얻을 수 있다. 

물론 n-1 의 경우까지 비슷한 케이스로 진행한다. 이때 (1)을 (2)로 나눠주면 결국 r(1) = r(2) = .... r(n-1) 이라는 결과가 나온다. 

다시 (1) 식에 집어넣으면  

이라는 결과가 나오는데 이걸 Utilization을 구하는 식에 대입해보면 된다.

결국 위의 결과물보다 Total Utilization이 작으면 해당 system의 schedulable하다. 이때 n을 무한대로 해서 극한을 취해보면 

U()  ln2  0.69  

라는 결과를 얻게 된다. 여기서 0.69가 나타내는 의미가 바로 앞에서 계속 소개했던 minimal Utilization의 값이고, 지금 수행되고 있는 모든 수식이 Rate Monotonic 상에서 수행되고 있으니까, 결국 69%가 Utilization Bound가 되는 것이다. 지나간 포스트에서 잠깐 소개를 했다시피 이 증명을 RealTime System의 저자인 Liu 교수와 Layland 씨가 했기 때문에 L&L Bound 라고도 불린다. 이 값이 시사하는 바가 크다. 사실 지금까지 쓴 포스트만 봐도 수학적인 식이 가득하다. 이걸 하드웨어적으로 구현하기는 것이 힘들었는데, 이렇게 간단한 수와의 비교를 통해서 schedulability를 비교할 수 있기 때문이다. 

뭐 아무튼 그렇다.