[Study] Reference Model in Resource / Scheduling

지난 포스트에서 Real Time System을 구현할 때 Reference model을 설정해놓으면 좋은 점에 대해서 언급했고, 그 중 하나로 Workload에 따른 분류를 해봤다. 이번 포스트에서 다룰 내용은 Resource 차원과 Scheduling 차원에서 정해진 Reference Model을 정리해보고자 한다. 

 System내에서 Resource라고 부를 수 있는게 뭐가 있을까? 생각해보면 PC의 성능을 나타내는 지표를 쭉 정리해보면 일차적으로 processor가 있을 것이고, 그 processor에 Data를 전달하기 위한 Bus, 그 Data를 담고 있던 storage,communication Channel등 task가 실행되고 전송되면서 거치는 모든 것들이 다 Resource라고 정리할 수 있을 것이다. 물론 이렇게 눈에 보이는 것들도 있겠지만 shared Memory나 virtual memory, semaphore, library routine과 같은 눈에 보이지 않으면서도 소프트웨어적으로 task를 수행하는데 도움을 주는 요소도 Resource라고 할 수 있다. 그럼 앞에서 설명한 Resource와 뒤에서 설명한 Resource의 차이는 무엇일까? 바로 Speed이다. 분명 task를 처리하는데 있어 다른 성향을 띄지만 전자쪽에서는 Speed라는 요소가 중요하게 작용할 것이고, 후자는 그렇게 speed와 연관있지는 않다. 이처럼 speed와 연관된 Resource를 Active Resource, speed와 무관한 Resource를 Passive Resource라고 말한다.

그러면 이런 Resource-based Reference Model을 평가하는 척도를 정리해보면 가장 대표적인 게 바로 같은 주기동안 얼마나 실행되느냐, 즉 Utilization이 될 것 같다. 보통 이전 포스트에서 잠깐 설명했던  Execution Time을 C라고 정의해보면

Utilization U(i) = C(i)/P(i)

라고 할 수 있을 것이다. 그런데 이건 i라는 시점에서의 Utilization이고, perodic task내에서는 전체 timing 내에서의 sum으로 평가할 수 있겠다.

 물론 위의 계산은 periodic Task일때를 가정한 것이고, Aperiodic Task일때는 p 값이 딱히 정해져있지 않다. 이때는 평균적인 값을 활용해서 전체 execution time의 평균값을 job inter-arrival time의 평균값으로 나눠준 값으로 Utilization을 계산할 수 있다. 

 사실 Resource 쪽에서 reference model을 설정한다는 것은 조금 무의미하다고 생각한다. 위에서처럼 Utilization으로 성능을 평가하면 Active Resource 의 발전으로 인해서 이는 얼마든지 향상될 수 있기 때문이다. 

 그럼 다음으로 정해볼 수 있는게 Scheduling 기법에 따른 Reference model의 분류이다. 

여기에 대해서는 이전 Resource와는 다르게 Reference model을 확연하게 분리할 수 있다. 우선 Schedule에 대해서 조금 정리해볼 필요가 있다.

Schedule이란 task를 어떤 규칙에 맞춰서 처리하는 방법을 포괄해서 말한다. 위의 그림에서는 정해진 timing t1,t2,t3에 맞춰서 J1,J2,J3를 실행되고 있으므로 좌측에 표현되어 있는 σ(t) 가 schedule이라고 할수 있다. 그래프를 잘 보면 알겠지만 schedule이 수행되고 있는 것에 따라 이 일을 처리하는 것의 상태도 idle냐 run이냐로 나눌 수 있는데 보통 schedule이 잘 되고 있느냐의 정도는 이 job이 제시간에 run state에 따라서 수행되는 것을 말한다. 보통 이런 상태를 feasible이라고 말하고, 이런 feasible한 schedule을 구현하는 algorithm이 있을 경우의 task process를 schedulable이라고 정의할 수 있다. 결국 이 Scheduling 방법에 따라서 Reference model을 정의할 때는 그 Scheduling 기법이 얼마나 schedulable 하냐를 따지면 될 듯 하다. 물론 이 schedulable을 정의할 때는 기준이 제각각이다. 임베디드 시스템에서 정의하는 schedulable이나, PC에서 정의하는 Schedulable이 다를 수 있을 것이다. 

 위에서 잠깐 언급했든 scheduler를 담고 있는 시스템에 따라서 scheduling 기법이 다를 수 있다. 먼저 나눌 수 있는게 task의 처리 순위이다. task가 처리되기 위해서 Resource를 사용하는데 그중 기본적인 가정이 CPU는 task를 한번에 하나 처리할 수 있다는 것이다. 그러면 CPU가 여러개의 task를 가지고 있을 때는 어떤 식으로 처리하는 것이 feasible하고 schedulable한지를 고민하는 것이 여기서 고민해볼 점이다. 보통 이런 것을 Preemption(선점)이라고 한다. 이 때의 기준은 Scheduler와 cpu와의 관계가 된다. 만약 cpu가 task를 처리하는데 있어서 Scheduler가 관여할 여지가 있으면 preemptive schedule이 될 것이고, 상황에 불구하고 Scheduler가 관여할 여지가 없으면 그건 Non-Preemptive schedule이 될 것이다. 

<http://www.embedded.com/design/operating-systems/4204740/Getting-real--time--about-embedded-GNU-Linux>

이와는 다른 방식으로도 분리를 해볼 수 있다.이렇게 task를 처리하는 schedule이 어딘가에 저장이 되어서 추후에 사용되는 off-line Scheduling 방식이라던가, Ready Queue를 따로 두어서 실시간으로 schedule로 처리되어야 할 task를 판단하는 online 방식도 존재한다. 아니면 궁극적으로 미래에 발생할 job을 예측해서 그에 따른 schedule 기법을 능동적으로 적용할 수 있는 clairvoyant  방식도 존재한다. 그런데 엄밀히 말하면 fully clairvoyant 라는 건 존재할 수 없고, 그에 대한 대안으로 Non-Clairvoyant scheduling이나 Partially Clairvoyant 방식에 관한 논문들이 나오고 있는 듯 하다. 개인적인 생각.. clairvoyant라는 말이 내포하는 뜻자체는 알겠는데 파생적으로 나온 방식에 대해서는 조금더 읽어봐야 할 듯 하다. 뭔가 최근에 이슈화되는 Data Mining 같은 걸 하면 예측에 따른 gap을 보완할 수 있지 않을까 하는데..

아무튼 두 포스트에 거쳐서 Reference Model을 정의해보았다. 말그대로 Reference를 정해놓으면 System을 만드는데 있어서 Reference가 생긴다는 것이고, 이렇게 하면 역량을 가해야 할 주요 point들이 명확해지기 때문에 중요하지 않나 생각한다. RTOS에서는 위에서 언급한 workload나 schedule등의 비교 요소들이 전체 동작에 미치는 영향이 크기 때문에 더더욱 그럴 듯 하다.