CFS(Complete Fair Scheduling)은 linux 2.6.23에 들어간 이미 오래된 기능이다.
리눅스 커널 2.6의 가장 큰 변화 중 하나가 O(1) Scheduler라고 그렇게 외쳐됐던 것이 엇그제 일인데 벌써 다른 스케줄러로 교체되어 버렸다.
요즘 너무 메모리쪽으로만 집중을 하다보니 스케줄러 쪽으로 많이 소원해진 것이 사실이다.
아무리 그래도 기본적인 Design Concept정도는 알고 있어야 할 듯 해서 이 페이지를 정리해 본다.
이글은 아래의 페이지를 내 마음대로 해석하여 정리한 글임을 밝혀둔다.
2008/08/15 11:40:46 - barrios -
크게 봐서는 CFS는 이전의 스케줄러와 같은 원리로 동작한다.
CFS도 이전의 스케줄러와 마찬가지로 niceness가 각 쓰레드가 할당받는 CPU time을 제어하기 위한 주요 수단이다.
O(1) 스케줄러는 동적으로 priority를 조절하여 waking thread가 조만간 얼마나 빨리 수행될지를 조절하였지 runnable한 쓰레드들 사이에서의 CPU sharing을 조절하진 않았다.
CFS에서는 runtime을 측정하는 방법과 waking thread가 빨리 수행될 수 있기를 보장하기 위한 방법이 새롭게 사용되었다.
CFS로 들어가기에 앞서 이전 O(1) 스케줄러의 문제점을 몇가지 살펴보자.
- nice값으로 CPU sharing을 조절하게 되는 O(1)에 있어서 같은 nice값을 갖는 두개의 쓰레드가 있다고 가정하자. 두쓰레는 공평하게 CPU time을 반씩 나누어 가질 것이다. 하지만 스위칭은 얼마나 자주 일어나게 될까? nice 0이 가지는timeslice가 100ms이고 두 쓰레드가 nice0이라면 매 100ms마다 스위칭이 발생할 것이다. 반면에 nice19라면 그리고 timeslice가 5ms라면 5ms단위로 스위칭이 발생할 것이다. 이것은 이상적인 throughput과response time의 trace off는 아니다. 하지만 시스템에 여러 nice값을 가진 쓰레드들이 존재한다면 다소 완화될수는 있다. 어쨋든, nice의 변경으로 인하여 스위칭 rate가 변경되는 것은 바람직한 관계는 아니다. 굳이 관계를 지어본다면nice값이 높을 수록 CPU intensive한 프로그램이다. 즉 long-running 쓰레드들이라는 것이다. 이런쓰레드들은 throughput이 response time보다 더 중요하다. 그러므로 적은 timeslice로 인하여 빈번한스위칭은 바람직하지 않다. 그러므로 nice값과 스위칭 rate 관계는 기존과는 반대로 되야 할 것이다.
- niceness와 timeslice의 관계도 이상하다. 1 정도의 nice값의 차이가 나는 쓰레드가 2개 있다고 가정해보자. CPU를 어떻게나누어 가지게 될까? 대답은 nice의 값의 차이보다는 abosulte niceness level의 차이에 따라 다르다. 예를들어보자. niceness를 0과 1을 가지는 쓰레드들은 100과 95ms의 timeslice를 갖게 될 것이다. 다음niceness 18과 19를 가지는 경우를 살펴보자. 그때는 10과 5ms의 time slice를 갖게 될 것이다. -_-;;
- wakingthread들을 더 우선하는 시스템은 큰 문제를 가질 소지가 있다. 리눅스의 waking thread들은 thread의priroity와 관련된 위치의 active array에 들어가게 된다. 게다가 얼마동안 잠든 채로 시간을 보낸runnable한 쓰레드는 timeslice를 다 소진했을 지라도 다시 active array로 들어오는 bonus를 받게된다. 그래서 active array가 쓰레드들을 포함하고 있는 한, expired array에 어떤 쓰레드들도 CPUtime을 얻지 못하게 된다. waking 쓰레드들이 꾸준히 active array로 들어오게 되면 expired array에있는 runnable thread들은 예측할 수 없는 임의의 시간동안 지연되게 된다. 단 2개의 쓰레드들만으로도 sleep과wakeup을 조작하여 runabble한 쓰레드를 몇초 동안 지연시킬 수 있다. 왜냐하면 time slice를 주로 잠으로써 다소진한 쓰레드 는 expired array로 가지 않고 active array로 가기 때문이다.
CFS는 각 niceness level을 timeslice로 할당하기 보다는 weight로 할당하고 runnable한 쓰레드들의total weight에 기반하여 timeslice를 계산한다. 그로므로 각 쓰레드들은 total weight에 기반하여비례적으로 timslice를 받게 된다. CFS는 runabble한 쓰레드들이 한 바퀴 round-robin을 하는 시간을정하여 그 시간을 기준으로 CPU를 분배한다. 그 target time이 100ms라고 가정하면, 두개의 같은priority의 쓰레드들은 같은 weight을 가지게 됨으로 각 쓰레드는 50ms를 얻게 된다. 이는 두 쓰레드가 nice값0을 갖던, 19를 갖던 상관없이 50ms씩을 얻게 된다. 만일 4개의 쓰레드가 같은 nice값을 갖는다면 25ms씩 갖게된다. 스위칭 rate는 이전의 스케줄러와는 달리 nice 값의 level과는 무관하게 된 것이다.
재미있는 것은 스위칭 rate가 전체 시스템 부하와 관련있어 졌다는 것이다. 즉 시스템에 부하가 많아지면 응답성을 보장하기 위해서throughput을 약간 희생하게 될 것이다. 응답성의 level은 target time에 따라 조절되어 진다. 이 값은시스템 어드민에 의해 조절될 수 있다. 100ms의 값은 서버와 같이 throughput이 주요하고 응답성은 단지graphical한 interaction이 아니라 web page reload의 scalability를 중요시 여기는 시스템에서적절하다. CFS의 default target time은 20ms이다. 이것은 응답성이 중요한 desktopmachine에 적절하다.
하지만 시스템 부하가 정말 높아지게 되면 CFS는 응답성을 위하여 throughput을계속해서 희생하지 않는다. 왜냐하면 각 쓰레드가 얼마나 적은 timeslice를 받게 되느냐에 하한선이 있기 때문이다. 그지점에 도달하게 되었을 경우 새로운 쓰레드가 시스템에 들어가게 되면 per-thread time을 감소시키기보다는 쓰레드들을순환하기 위한 전체 시간을 증가시킬 것이다.
niceness0과 niceness5을 가지는 두개의쓰레드가 CPU를 공유하는 경우를 가정해보자. CFS는 이 쓰레듣르에게 1024와 335의 weight을 주게 된다. 그러므로쓰레드가 얻는 시간은 1024/(1024+355), 335/(1024+335)가 된다. 1024는 대략 335의 3배이기 때문에niceness0을 가진 쓰레드는 대략 100ms중에 75ms, niceness5를 가진 쓰레드는 100ms중에 15ms를 갖게될 것을 예측할 수 있다. niceness 5, 10 또는 niceness 0, 5를 갖던 상관 없이 같은 결과를 얻게 될것이다. 왜냐하면 어떻게 하여도 weight의 비율이 3:1이 될 것이기 때문이다. 즉, CPU proportion은niceness의 상대적 차이로 얻게 되는 것이지 이전과 같이 절대 차이로 인하여 얻게 되는 것이 아니다.
CFS의 big idea는 각 쓰레드들이 얼마나 많은 시간동안 실행을 했는지를 쓰레드의 weight으로 scale하여 유지하는것이다. 즉, niceness0 쓰레드는 수행시간을 1ns단위로 scale한다. 반면, niceness5 를 가진 쓰레드는실행시간을 대략 3ns단위로 scale하게 된다.
이렇게 weigh을 이용하여 scale하는 이유는 어떤 쓰레드가가장 뒤쳐져 있는지를 판별하기 위해서이다. 가장 뒤쳐져 있다는 것은 자신에게 주어진 timeslice를 가장 채우지 못한쓰레드라는 것이다. CFS가 timeslice를 채우지 못한 쓰레드들에게 계속해서 제어권을 넘겨 균형을 유지하려고 한다면끊임없이 가장 뒤쳐져 있는 쓰레드들로 스위칭을 해야하며 이는 매우 비효율적일 것이다. 얘기가 어려워진다. 쉽게 예를 들어설명하여 보자.
두 쓰레드가 같은 niceness를 가지고 있다면 스케줄러는 두 쓰레드가 항상같은 timeslice을 수행하고 있음을 보장하려고 애쓸 것이다. 즉, X ns 후에 살펴보니 정확하게 두 쓰레드가 X/2ns씩 수행을 해야 할 것이다. 이것을 만족시키기 위해서는 스케줄러는 끊임없이 쓰레드들 사이를 스위칭 해야 할 것이며 그것은너무 비효율적일 것이다. 그래서 스케줄러는 그렇게 자주 스위칭을 하는 것보다는 한 쓰레드를 그 쓰레드의 timeslice동안지켜보게 된다.(스케줄러는 쓰레드들을 20ms 주기로 스위칭을 한다고 가정하자) 그 결과, 60msec 후에 두 쓰레드가30ms씩 수행된 것이 아니라 40ms, 20ms 씩 수행된 것을 볼수도 있게 될 것이다. 하지만 스케줄러가 다음 실행할쓰레드를 결정할 때 20ms를 수행한 쓰레드 B를 선택하여 쓰레드 A를 빨리 따라잡게 만들 것이다. 이런 방법으로 쓰레드들이서로 제어권을 주고 받으며 수행하게 되면 어느 시점에서도 두 쓰레드들 사이의 차이가 그렇게 크게 되지 않게 만들 것이다.(이예제에서는 20ms 이내가 될 것이다.)
두 쓰레드가 다른 niceness를 가지고 있을 경우를고려해보자. 예를 들어 쓰레드 A는 niceness0을 가지고 있고 쓰레드 B는 niceness5를 가지고 있다고 가정하자.쉽게하기 위해 1024/335는 3이라고 하자. 즉 쓰레드 A는 쓰레드 B보다 3배 더 크다. 60ms이후에 이상적인 경우쓰레드 A는 45ms, 쓰레드 B는 15ms가 되야 한다. 하지만 스케줄러가 20ms마다 쓰레드들을 스위칭한다면 그 이상적인상황은 발생하지 않을 것이다. 쓰레드 A는 40ms, 쓰레드 B는 20ms가 수행된 것을 알 수 있다. 이 시점에서 다음 어떤쓰레드를 스케줄해야 할까?
B는 이미 자신의 할당받은 timeslice(15ms)를 넘어선 것을 알 수 있다.스케줄러가 이러한 상황을 판단하기 위해서는 각 쓰레드의 time을 scale fator를 가지고 곱하는 것이다. 예를 들어쓰레드 A는 scale factor가 1이다. 반면 쓰레드 B는 3이다. 그러므로 실제 run time이 40ms, 20ms인경우, virtual run time은 40ms, 60ms가 되는 것이다. 이제 명확해졌다. 쓰레드 A는 더 뒤쳐져 있다.그러므로 스케줄러는 쓰레드 A를 실행해야 할 것을 알게 된다.
위의 설명은 모든 쓰레드들이system이 처음 bootup됐을 때부터 시작되었고 계속해서 runnable하게 존재한다면 잘 동작할 것이다. 하지만 실제시스템은 그렇지않기 때문에 새로 만들어지는 쓰레드들과 잠에서 깨어나느 쓰레드들에 대한 고려가 반드시 필요하다. 이런 고려가 되지않을 경우, 새로 만들어지는 쓰레드나 잠들었다 깨어난 쓰레드들은 이미 존재하고 있던 쓰레드들을 따라잡을 때가지 수행되게 될것이다. 이는 바람직하지 못하다. 그러므로 하나의 쓰레드가 runqueue에 들어가게 될 경우 그 쓰레드의 virtualruntime은 존재하는 runnable한 쓰레드들의 가장 작은 virtual runtime으로 지정되고 약간 조절되게 된다.(새롭게 만들어지는 쓰레드 or 깨어나는 쓰레드냐에 따라). 이러한 방법으로 우선적으로 실행될 수 있는 구너한을 부여받고비정상적으로 오랫동안 수행되지 않을 것이다.
run queueu는 runnable thread들의virtual runtime으로 정렬한 red-black tree로 유지된다. CFS가 쓰레듣르을 스위칭하려고 할 때 가장왼쪽에 놓여 있는 쓰레드들 선택하게 된다. 즉 가장 작은 virtual runtime을 가진 쓰레드이다.
스케줄러는 2가지 상황에서 이러한 쓰레드들을 스위칭 한다. 첫째는 timeslice를 다 소진했을 경우이다. 다른 상황은 현재쓰레드가 수행된지 어느 정도 시간이 됐는데(이 값은 configurable하다.) 새로운 쓰레드가 runqueue에 들어오게되는 경우이다.
runnable 한 쓰레드들을 virtual runtime의 timeline에위치시키는 장점중 하나는 waking thread들이 다른 쓰레드들을 굶주리게 하는 경우를 막을 수 있다는 것이다.(이미 언급한바와 같이 이전 O(1) 스케줄러의 큰 문제점이기도 했다.) 시간이 가면서 깨어나는 쓰레드들은 virtual runtime의 timeline에 점점 더 뒤쪽으로 위치하게 된다. 즉, 현재 time을 기준으로 상대적으로 더 뒤쪽으로 위치하게 된다. 반면인내심을 가지고 CPU를 기다려온 쓰레드들은 고정된 virtual runtime을 갖게 된다. 즉, 이들은 이미 오래전 fix한 virtual runtime을 가지고 있다. 그러므로 마침내 가장 작은 virtual runtime을 갖게 될 것이며 실행되게될 것이다. sleeping과 wakeup을 가진 어떤 음모도 이제 통하지 않게 된다.
가장 이상적인 CFS slice는 다음과 같이 계산된다.
slice = (se->load.weight / cfs_rq->load.weight) * period
period는 스케줄러가 모든 task들을 수행하는데 걸리는 시간이다. default로 20ms로 되어 있으나 이 값은 고정은 아니다.
시스템에 runnable한 task들의 수가 sched_nr_latency보다 커질 수록 이 값은 증가하게 된다. 그렇지 않게 되면 각 task들에게 분배되는 slice가 너무 작아 context switching 오버헤드가 너무 커져 시스템이 비효율적일 수 있기 때문이다.
se는 sched_entity를 의미하는 것이다. 따로 설명은 안했지만 CFS에서의 sched_entity는 단지 task만 될 수 있는 것이 아니라, user, container등 보다 다양한 hierachy를 제공한다. 여기서는 se가 task로 봐도 무방하다.
즉, slice는 한 period 중 태스크의 weight이 cfs_rq의 전체 weight중에 차지하는 비율이다.
또한 실행중 특정 task의 vruntime은 다음과 같이 계산된다.
vruntime += (NICE_0_LOAD / se->load.weight) * delta_exec
여기서 delta_exec는 그 cpu를 할당받아 수행된 시간이다. NICE_0_LOAD는 상수값 1024이다.
즉 vruntime은 위에서 이미 설명한 것과 같이 task의 weight으로 수행시간을 scale한 결과이다.
위의 식 이전의 식과 결합하면 다음과 같이 될 수 있다.
vruntime += (period/cfs_rq->load.weight) * NICE_0_LOAD
위의 식이 증명하는 것과 같이 period와 cfs_rq->load.weight은 모든 task들에게서 같은 값을 가지기 때문에 모든 task들의 vruntime은 같은 값 갖게 된는 것이다. 아주 이상적인 경우에 말이다.
그러므로 vruntime 값이 적다는 것은 그 task가 자신의 slice를 충분히 사용하지 못했다는 것이고 그 task가 rbtree의 leftmost에 있게 되며 가장 긴급히 수행시켜줘야 할 task가 되는 것이다.
No comments:
Post a Comment