[Study] Optimality of Earliest Deadline First

Optimal이란 단어 자체는 모호하다.사실 판단하는 기준이 어떻냐에 따라서 Optimal의 정도가 바뀔 수 있기 때문이다. 그래서 시스템의 최적성 판단시 Optimality 를 측정하기란 쉽지 않다. 그런 가운데에서도 가장 쉽게 취할 수 있는 approach는 바로 자기 자신을 기준으로 삼는다는 것이다. 자신을 기준으로 어떤 변형이 가해진 시스템에 적합하다고 증명하면, 다른 시스템에 대해서도 적용하기 쉽다는 방식이다. 지금 다루는 실시간 시스템의 경우에도 만약 자기가 만든 알고리즘이 어떤 환경에서든 schedulable 하다면 완벽하지는 않겠지만 그래도 어느정도 Optimality가 있다고 판단할 수 있을 것이다. 

 Realtime System 책에서 다루는 다음 주제는 지난 포스트에서 다뤘던 Priority Based Approach 중 Dynamic 방식에 속했던 Earliest Deadline First (EDF) 방식과 Least Slack Time First(LST) 방식이 과연 Optimal한지 증명하는 것이다. 그 중에서도 수업시간에 다뤘던 EDF 방식의 optimal 여부를 정리해보고자 한다. 

 그런데 사실 말로 자기 자신을 기준으로 Optimal 여부를 따져본다고 말을 했었지만 막상 적용하기가 쉽지 않다. 우선 따져봤을때 가장 먼저 체크해야 될 점은 과연 이 Algorithm이 Schedulable 한지 일거 같다. schedulable 한지를 알기 위해서는 어떤 algorithm이든 EDF에 맞춰서 변형을 가한다면 앞에서 말했던 어느정도의 Optimality가 보장될 것이라는 게 기본적인 전제이다.

 우선 다음의 예제를 살펴보자.

지금 t시점에서 바라본 위의 Schedule은 적절한 Period 내에서 Execution이 발생하기 때문에 Schedulable 하다. 그럼 이걸 이전 포스트에서 언급했던 EDF 방식에 맞게 변경하면 어떤식으로 바뀔까? 

당연히 이름안에 내포되어 있는대로 Deadline이 빠른게 먼저 실행되어야 하므로 J2가 J(1,)2보다는 빨리 실행되어야 할 것이다. 여기서 J(1,1)보다도 일찍 시작해야 된다고 생각할 수 있으나 J2의 Release Time이 R2이기 때문에 우리가 초점을 맞추고 있는 t와 R2간의 시간내에서 EDF를 적용해야 된다. 그래서 적용한 것이 두번째 그림이다. 이렇게 변경을 가했음에도 두 Time line은 Schedulable을 유지하고 있다. 수식으로 표현하면 다음과 같이 나올 것이다. 

R2 + (J(1,2) + J2) = R2 + (J2 + J(1,2)) = t < D2 < D1

EDF가 적용되어 있는지를 확인하는 예제였다. 그런데 과연 이것만 가지고 EDF가 Optimal하다고 할 수 있을까? 사실 이건 환경이 정해진 상태에서만 적용가능한 Algorithm이다. 더구나 J1을 J(1,1)과 J(1,2)로 쪼갤 수 있는 일종의 preemtive Job 이었기 때문에 위와 같이 증명할 수 있는 것이다. 만약 non-preemtive job에 EDF를 적용하면 어떻게 될 것인가? 즉, Job 자체가 Priority에 따라 중간에 멈추는 현상이 발생한다면 말이다.

아마 위와 같이 통째로 Job이 이동할 것이다. 당연히 J2는 적절한 Period(D2 - R2) 이내에 Execution이 발생하지 않았으므로 더이상 Schedulable이라고 할 수 없을 것이다. 정상적인 Preemtive EDF라면 바로 위 예제의 두번째 그림처럼 Scheduling이 되어야 정상이다. 일단 한가지 선행조건인 Preemptive Job Scheduling에서만 EDF가 적용할 수 있다는 것을 알았다. 그럼 다른 제약 사항은 없을까? 최근 추세에 적용해보자면 Multiprocessor 환경에서도 이 Scheduling Algorithm이 Optimal한지를 측정해볼 수 있다. 아래와 같은 환경이 있다.

지금 CPU1에서는 2개의 thread가 돌고 있고 CPU2에서는 1개의 Thread가 수행중이다. 이게 과연 Optimal 한가? 그걸 확인해보려면 위에 적용했던 Task Swapping을 해보면 된다. 

우선 CPU1의 첫번째 thread와 CPU2를 비교해보면 첫번째 thread의 Deadline이 먼저 있기 때문에 이미 EDF에 따라서 scheduling되어 있다. 그런데 문제는 CPU1의 두번째 thread인 것이다. CPU1의 두번째 thread와  CPU2를 비교해보면 CPU2의 Deadline이 더 먼저 있기 때문에 CPU2에 있는 Task가 먼저 실행이 되어야 한다. 그런데 막상 Swapping을 하고 보면 이미 점유하고 있는 CPU1의 첫번째 thread와 충돌하게 된다. 역시 Thread끼리도 Scheduling시 EDF를 만족해야 되므로 다음과 같이 될 것이다.

그러면 CPU2는 CPU2 대로 Period내에서 Job을 수행하지 못하므로 Schedulable하지 않고 CPU1은 Schedulable하되, CPU1의 CPU idle time이 길어지게 된다. 역시 이 점도 고민해볼 요소가 되겠다. 아무튼 MultiProcessor에서는 이런 Thread간의 간섭으로 인해서 EDF가 Optimal하다는 것을 증명하기 힘들다.

 다시 정리해보자면 EDF가 Optimal한지를 알기 위해서는 그 Schedule Table이 Preemptive한 상태에서 Single Processor로 처리되고 있을 때만 증명이 가능하다. 사실 요즘 trend인 Multi processor 에서 Optimal 여부를 증명하지 못한다면 요새에는 여기 나와있는 그대로 적용하기 어려운 Algorithm이 아닐까 생각해본다. 그래서 조금 찾아봤더니 Multiprocessor 내에서 EDF Schedulability 를 증명해놓은 논문들이 존재하는 것 같다. 관심있는 사람이라면 한번쯤 보면 도움이 될 듯 싶다.

-Reference 

Multiprocessor EDF and DM Schedulability Analysis by T.Baker - (http://websrv.cs.fsu.edu/~baker/papers/rtss03.pdf)