[Study] Real Time Scheduling의 몇가지 접근 방식

System이 원활하게 돌아가기 위해서는 무언가의 제어를 받아야 한다. 보통 그 무언가를 processor로 정의하고 있으며, 이 processor가 발생시키는 clock의 timing을 활용해서 Task scheduling을 한다. 이번 포스트에서는 Liu 교수가 쓴 Real Time Systems 의 chapter 4에 나오는 Realtime Scheduling에 대해서 조금 정리해보고자 한다.

 앞에서 언급한대로 clock의 timing이라는 건 시스템내에서 주기적으로 정확하게 발생하는 이벤트이다. 즉, 가장 쉽게 생각해볼 수 있는 scheduling은 이 clock을 기준으로 Task를 할당하는 Clock Driven Scheduling Approach가 될 것이다. 다른 말로는 Time-Driven이라고도 표현할 수 있는데 말그대로 Scheduling의 변인을 Time으로 한정지은 것이다. 간단하게 생각해보면 프로세스는 다음과 같다. Task들이 여러개 나열되어 있는 상태에서 clock이 주기적으로 발생할 것이다. 그러면 이때 어떤 일을 할 것인지 선택하고, 실행하게 되는 간단한 과정이다. 물론 clock과 execution Time간의 상관성에 따라서 Rising Edge인지 Falling Edge에 할 것인지가 달라지겠지만 전체적인 맥락은 주기적이라는데 있다.

 그런데 당연한 이야기이겠지만, 지속적으로 많은 기능을 제공하는 현대 RTOS에서는 순수한 Clock-Driven Scheduling이란 존재할 수 없다. 구현하기가 매우 단순하지만, 너무 직관적이고 다른 task가 개입하는 것에 대해서 별도로 처리하기가 매우 힘들다. 다만 이 clock이 기반이 되서 권한을 부여하는 식으로 발전한 것들이 주를 이루고 있다.

다음으로 나오는 개념이 Round-Robin 방식이다. 비단 컴퓨터 알고리즘에서 뿐만 아니라 round robin 방식은 순위를 정하거나 scheduling을 설계할 때 많이 쓰는 방식이다. 역시 주기적인 개념이 들어가되 나열되어 있는 Task들이 순차적으로 실행되는 것을 말한다. Task들이 순차적으로 이뤄지는 것을 볼 때 내부적으로는 FIFO 형식을 띄는 Queue가 존재할 것이며, queue에서 빠져오면서 task가 실행되는 구조가 된다. 물론 정해진 execution time이 지난후에 task가 남아있으면 다시 queue로 들어가는 형식을 취한다. 이 Round Robin의 핵심은 모든 task들이 골고루 나눠져서 정해진 주기내에는 적어도 한번씩 실행되는 것이다. 가령 n개의 task가 queue안에 들어 있으면 주기 T는 n으로 나눠져서 실행될 것이며 이 때 T를 round 라고 부를 수 있겠다.

 그런데 생각을 해보면 이 Simple한 Round Robin 방식도 말이 안된다고 생각하는 사람이 많을 것이다. 임베디드 시스템을 초기에 부팅시키면 시스템 관련 Task들이 실행될텐데 이런 것들이나 문서작업을 하는 것이나 같은 방식으로 실행되는 것을 상상하면, 분명 각 Task에도 각각의 Weight가 존재해야 한다고 생각할 수 있다. 즉 비중에 따라서 execution time을 효율적으로 분배하는 방식이 Weighted Round-Robin Scheduling이다. 강의자료에는 다음과 같이 언급되어 있다.

당연히 앞에서 언급한 Regular Round Robin 방식은 weight w가 1이 될 것이고, 생각해보면 이 Weight가 사전에 정의되어 있기 때문에 queue에 들어가 있는 task의 priority에 대해서 고려할 필요가 없다. 그렇기 때문에 구현에 있어서도 Simple하다고 언급되어 있다. 그런데 Round Robin의 고질적인 문제 자체가 전체적으로 task들이 늦게 끝난다는 것이다. 물론 Weighted RR 방식에서는 주기적으로 한번씩 수행하는 것이 아니기 때문에 어느정도 융통성이 있긴 하지만 기본적으로 RR 방식을 기반으로 삼기 때문에 한가지 일이 끝나기 위해서는 단순한 방식보다 기다려야 한다. 또한 weight에 기반을 두고 미리 설계된 방식 탓에 일이 끝났다는 것을 알지 못한 체 계속 기다려야 한다는 단점도 가지고 있다. 그래서 보통 이런 방식은 중요한 task가 아닌 message를 주고 받는 식의 networking 쪽에서 많이 적용되는 편이다.

 그러면 위에서 정한 것과 달리 아예 task가 생성될 때부터 순위를 정하고 그 순위에 따라 실행되게 하는 접근하면 어떨까? 이런 접근 방식이 바로 Priority-Driven Scheduling이다. 그런데 사실 이 방법은 사전에 고민을 해볼게 있다. task간의 priority를 정하기 위해서는 그 정하는 규칙에 대한 Algorithm이 필요할 것이고, 또는 Queue 구조 내에서도 priority order에 따라서 어떤 건 ready queue에 보내거나 wait queue에 보내는 구조가 사전에 정의되어야 한다. 그리고 무엇보다 중요한 건 이런식의 구조와 Algorithm이 Optimal 하냐는 것이다.

 그런데 바로 앞에서 말한 내용중에서 뭔가 이상한 점을 느끼는 사람도 있을 것이다. Queue 라는 자료구조는 말그대로 First-In-First-Out 의 성향을 띈다. 이 논리에 따르면 Queue는 순위에 상관없이 내보내는 전형적인 "anti-priority"라고 느낄 사람도 있을 것이다. 사실 FIFO의 기준 자체를 Order에 주목해보면 여기에 대한 답을 풀 수 있다. 들어온 Order 자체를 구별하는 것이 하나의 algorithm이자 Priority이기 때문이다. 여기에 맞춰 들어온 task가 그냥 수행된다는게 anti-priority처럼 보이게 하는 것이지, 엄연히 priority Scheduling을 따르고 있으며 다른말로 work-Conserving Scheme라고 말하기도 한다. 

 자 그러면 이런식으로 Task를 관리하는 Scheduling이 많이 있으며, 이걸 어떤 시스템에 대해서 분류할 필요가 있어보인다. 여기서 다루는 Realtime System이 아닌데에는 쉽게 적용할 수 있는 것이 다들 알고 있는 자료구조들을 들 수 있다. 거기서도 지난 포스트에서도 설명했던 release time에 따라 나누면 흔히 FIFO와 LIFO로 나눠볼 수 있고. 또는 Execution의 길이에 따라서 Short-Execution-Time First나 Longest-Execution-Time First가 대표적일 것이다. 하지만 이 section에 다루는 것은 Realtime에 사용할 수 있는 System이기 때문에 조금 다른 접근이 필요하다. 

그럼 다시 돌아가서 RealtimeOS에서 가장 대표적인 특징을 정리해보자. 다른건 기억이 안나도 deadline이라는 것이 일반적인 OS와 RTOS를 구분하는 요소중의 하나라는 것을 기억할 수 있을 것이다. 바로 이 deadline을 priority를 정하는 기준을 만들면 조금더 algorithm을 구분하는데 쉬울 듯하다. 그 중에서도 deadline을 priority를 정하는 직접적인 기준으로 삼는 방식이 Earlist-Deadline-First(EDF) 이 될 것이다. 예를 살펴보자면 다음과 같다.

 

위와 같이 Period가 10이고 execution time이 2인 T1과 Period가 14이고 execution Time이 9인 T2가 있다. 지금 위의 예제는 Shortest execution-Time First에 따라서 scheduling된건데, 이걸 EDF에 맞춰서 scheduling하면 어떻게 될까? 우선 T1의 deadline이 작으므로 Priority는 T1이 높을 것이다. 그러면 T1이 끝난 후에야 T2가 실행될 것이고, 10초가 지난후에는 다시 T1의 Scheduling이 시작되므로 T2가 hold될 것이다. 물론 T1의 작업이 끝난 후에는 T2의 잔업을 수행하는 형식이 바로 EDF가 될 것이다.

그런데 잘보면 14초 이전에 약간의 idle 상태가 존재하는 것을 확인할 수 있다. 보통 scheduling이 잘 된다고 하는 것은 CPU의 Task process 중에 idle state가 없는 상태를 말하는데, 위처럼 약간 그런점을 약점으로 지적할 수 있다. 이점은 논외로 하고 Deadline을 이용해서 slack time을 구하고 이를 priority를 정하는 기준을 삼는 Least-Slack-Time (LST) 방식도 있다. 여기서 slack time이란 여유시간을 말하는데 수식으로는 다음과 같이 표현할 수 있다.

 간단히 설명하면 execution time이 많이 남은 것을 계산해 higher priority를 주는 것이다. 그런데 식에도 나와있다시피 t값에 따른 Remaining Execution Time을 실시간으로 측정해야 되기 때문에 앞에서 소개한 EDF 방식보다 복잡할 것이다. 무엇보다 나쁜 것은 scheduling으로 관리해줘야 할 job이 많을 경우 가장 worst한 case를 고려해야 하는데 이 worst case를 뽑는 것자체가 경험적이기 때문에 이를 구하기 위해서는 많은 iteration을 거쳐야 한다. 물론 이로 인해서 성능이 저하될 것이다. 

 뭐 아무튼 위에서 다룬 EDF나 LST 방식을 잘 살펴보면 모든 것이 t와 연관되어 있는 것을 알 수 있다. 즉, 시간에 따라서 priority가 변화하는 방식이 있고(Dynamic Priority) 한번 priority가 정해지면 job order가 바뀌지 않는 방식(Static(fixed) Priority)도 있다. Static Priority같은 경우는 어떤 기준을 정하고 그 기존에 맞춰서 priority를 정하는데, 그 기준이 Rate냐 Deadline이냐에 따라서 Rate Monotonic(RM)/ Deadline Monotonic(DM)으로 나눠볼 수 있을 것이다. 이전 포스트에서도 나왔던 online/offline분류에 맞춰서 앞에서 나온 접근방식을 나눠보면 다음과 같다. 

Scheduling에 대한 Algorithm은 참 많다. 정리해보면 offline은 실시간으로 감지할 필요없이 task를 실행시키는 것이므로 맨 앞에서 언급했던 clock driven scheduling이 될 것이고, online은 실시간으로 schedule 되는 것을 요구하기에 기존의 RR방식에 weight를 가한 WRR 방식이나 job 내에서 priority를 정하는 방식이 포함될 것이다. 이중 실시간으로 이 priority가 변하는지의 여부에 따라서도 또 나눌 수 있다. 참 많다... 

 이번 포스트는 단순한 접근 방식의 소개였던 것이지 각 algorithm에 대한 설명은 아마 뒷부분에서 자세하게 한다. 그건 조금더 정리를 해봐야 될 거 같다.