[linux kernel] CFS Scheduler에서 VR(T) 조정(wake_up)

1. 도입

Linux kernel이 사용하는 scheduler는 점점 발전해왔다. 초기에는 매우 단순한 scheduler를 사용하다가 Linux 2.4부터는 O(n) scheduler를 사용했고, linux 2.6~linux 2.6.22에는 O(n) scheduler를 조금 더 보완한 O(1) scheduler를 사용하였다. 이후 linux 2.6.23에 현재까지도 사용하고 있는 cfs scheduler가 처음 도입되었다. linux kernel은 여러 계층의 scheduler를 제공하지만 대부분의 경우 CFS(SCHED_NORMAL, SCHED_BATCH)를 사용한다. 오늘은 CFS scheduler의 특정 현상에 대해 공부하기 위해 글을 쓰게 되었다. 들어가기 앞서서 O(n)과 O(1) scheduler에 대한 간단한 설명을 하고 지나간다. 

 

2. O(n) Scheduler

O(n) scheduler에 대한 간단한 설명을 해보자. 당시에 각 task의 priority를 나타내는 값 'nice'를 사용하였다. nice는 말하자면 정적인 priority로 이를 토대로 'counter'라는 동적인 priority를 설정하여 각 task에게 할당해주게 된다. counter는 다른 의미로 time slice로 이해할 수 있다. scheduler는 이러한 counter값과 task의 mm, nice값 등을 고려하여 'goodness'라는 척도를 정하고 이를 토대로 다음 수행할 task를 결정한다. 모든 task가 자신의 time slice를 다 쓰면, 즉 counter 값이 0이 되면 다시 scheduler는 각 task에 counter값을 부여하고 scheduling 한다. 새로운 task가 들어오거나 잠들어있던 task가 run queue에 들어오는 경우에는 현재 돌고 있는 task의 goodness와 비교하여 preemption을 결정한다. 또한 block 되어 있는 task에게 새로운 epoch이 시작할 때 해당 task의 nice값에 해당하는 counter만큼 추가하는 동시에 기존의 counter의 값을 반으로 줄인다. 이렇게 함으로써 block 되어 있던 task의 우선순위를 높이면서 동시에 counter값이 최대 2배 이상 올라가지 않아 너무 오래 cpu를 독차지하고 있는 현상을 방지한다. block 되어 있는 task의 우선순위를 높이는 이유는 throughput을 증가시키기 위함이다.

 

O(n) scheduler는 다양한 문제를 가지고 있다. 우선 이름에서 알 수 있듯이 모든 goodness를 비교하여 다음 task를 결정하기 때문에 O(n)만큼의 시간 복잡도가 걸린다는 것과 새로운 epoch시작 시 모든 task의 counter값을 재 할당해야 된다. 이것을 해결하기 위해 O(1) scheduler를 개발하였는데, 각 priority마다 queue와 bitmap을 두어 scheduling시와 counter값 할당시의 시간을 줄였다. 

 

3. CFS에서 VR(T)

CFS scheduler는 Complete Fair Scheduler의 약자로, 이름 그대로 최대한 공평하게 task에게 CPU를 할당하는 것을 목적으로 한다. O(n) Scheduler의 경우 timeslice를 오직 nice값을 기준으로 할당하였다. 이렇게 정적인 전환의 경우 througput이 떨어질 수 밖에 없다. CFS는 상대적인 기준으로 timeslice를 할당하였기 때문에 이러한 문제를 피할 수 있었다. 기본적인 개념을 살펴보면, nice값은 동일하게 존재한다. 해당하는 nice값을 토대로 weight값을 대응하게 된다. 하지만 이러한 weight값을 바로 사용하는 것이 아닌 전체 weight값들의 합에 대한 비율을 계산하여 time slice를 할당받는다. 또한 CFS의 scheduling 기준은 Virtual Runtime(VR(T))로 이 값이 가장 작은 task를 먼저 scheduling 하게 되는데, 이 값은 nice=0인 task의 weight를 기준으로 하여 얼마나 많은 CPU time을 사용했는지로 계산한다. 예를 들어서 nice 값이 -20인 task와 -19인 task가 있다면 -20인 task의 weight값은 더 클 것이다. priority(weight)의 값이 더 큼으로 작은놈보다 전체 timeslice를 더 얻을 것이며, VR(T) 또한 priority가 작은놈보다 더 천천히 증가할 것이다. 여기서 CFS scheduler에 대한 자세한 설명은 하지 않을 것이다. (모르는 것도 있지만...) 여기서 짚고 넘어가고 싶은 것은 block 된 task의 VR(T)를 어떻게 해줄 것이냐는 것이다.

앞에서 O(n) scheduler의 경우 새로운 epoch이 시작될 때마다 모든 task의 counter 값을 1/2배한 다음 새로운 tick을 더해주었다. 이를 통하여 'sleeper fairness'라고 불리는 block 된 task에게 CPU에 대한 우선권을 주는 policy를 구현하였다. 그렇다면 CFS에서는 어떻게 될까? 만약 VR의 값이 3인 task가 block 된 상태에서 다른 task들이 계속 돌면서 그들의 VR(T)는 계속 증가할 텐데 이후에 block 되었던 task가 unblock 되는 순간 아주 오랫동안 CPU를 잡고 있을 수 있다. 이를 방지하기 위해 

1. wake-up이 발생한 task

2. 새로운 task

에 대한 VR(T)의 값이 어떻게 설정되는지에 대해 코드 단위로 조사해보았다. 

 

4. Wake-up 된 Task의 VR(T)

wake-up시의 code flow

우선 들어가기 앞서 각 CPU마다 'cfs_rq'라는 구조체가 있다는 것을 알아야 된다. cfs_rq는 cfs scheduler의 runqueue에 대한 정보가 들어가 있다. 이 안에 'u64 min_vruntime'이라는 변수가 있는데 이는 현재 cfs의 runqueue안의 가장 작은 vruntime값을 가진 task의 vruntime을 저장하고 있다. 자 이제 위의 흐름도에 따라서 하나씩 살펴보자.

---

(1) wake_up_process

kernel/sched/core.c

특정 process를 깨우기 위한 함수이다. 성공하면 1을 이미 돌고있다면 0을 반환한다.

---

(2) try_to_wake_up

kernel/sched/core.c

Thread를 깨운다. SMP환경에 대한 코드가 있고 lock에 대한 코드들이 있지만 중요한 것은 ttwu_queue라는 함수를 호출한다는 것이다. 

---

(3) ttwu_queue

kernel/sched/core.c

ttwu는 (try to wake up)의 줄임말로 추정이 된다. cpu의 run queue를 rq에 저장하고 update_rq_clock과 ttwu_do_activate라는 함수를 호출하는데, 우리가 따라갈 것은 ttwu_do_activate 함수이다. (update_rq_clock은 이름 그대로 rq 구조체의 clock변수의 값을 증가시켜주는 것 같다)

---

(4) ttwu_do_activate

kernel/sched/core.c

여기서 집중해서 볼 것은 en_flags안에 'ENQUEUE_WAKEUP'이 포함된다는 것이다. 또한  이를 activate_task의 인자로 넘겨준다. 

---

(5) activate_task

kernel/sched/core.c

똑같은 인자를 가지고 enqueue_task함수를 호출한다. task_struct 구조체의 on_rq값을 바꾼다. (이럴 거면 이 함수는 왜 만들지... enqueue_task만 따로 사용하는 경우가 있나 보다)

---

(6) enqueue_task

kernel/sched/core.c

앞에서 flag로 받아온 것들에 해당하는 작업을 한 뒤 task_struct구조체의 sched_class안의 enqueue_task라는 method를 호출한다. 이는 <kernel/sched/fair.c>의 DEFINE_SCHED_CLASS(fair)에서 찾아보면 다음과 같이 나와있다.

kernel/sched/fair.c

즉, enqueue_task_fair라는 함수가 호출된다.

---

(7) enqueue_task_fair

kernel/sched/fair.c

이 함수는 위에 나온 것이 끝이 아니다. 내가 아직 해석하지 못하는 부분이 너무나도 많다. 우선 task_struct내의 모든 sched_entity에 대하여 이를 run queue에 올리는 작업을 하는 것 같다. 이를 enqueue_entity라는 함수를 통해서 수행한다.

---

(8) enqueue_entity

kernel/sched/fair.c

  이 함수가 실질적으로 wake up 한 task의 vruntime을 결정해주는 시작점(?)이다. 'renorm'라는 bool형 변수가 있다. 이 값이 true이면 renormalization이 필요하다는 뜻이다.

  normalization이 무엇일까? 여러 개의 CPU가 있는 환경에서는 run queue도 여러 개일 것이다. 특정 run queue는 task가 적어서 VR(T)의 값이 빠르게 커질 수 있지만 특정 run queue는 그렇지 않을 수 있다. 만약 같은 nice값의 task가 이러한 2개의 run queue에서 돌다가 같은 run queue로 들어오게 되면 서로 nice값은 같음에도 불구하고 한 task만 계속 독점하게 될 것이다. normalize에 대한 설명은 찾기 매우 힘들지만 추정한 바로는 각 cpu_rq에 저장되어 있는 min_vruntime을 +,-해주면서 renormalize, normalize를 해주는 것 같다. 

  다시 돌아가서 앞에서 ENQUEUE_WAKEUP이라는 flag가 설정되었기 때문에 renorm은 false가 된다. 따라서 se->vruntime은 변함없이 내려와 place_entity라는 함수를 호출하게 된다.

---

(9) place_entity

kernel/sched/fair.c

  앞에서 initial값을 0으로 enqueue_entry에서 넘겨주었기 때문에 두 번째 if문이 실행된다. thresh값에 넣는 sched_latency는 상수 값으로 nanosecond단위로 6ms를 나타내는 6000000 ULL로 설정되어 있다. (Unsigned Long Long) 최소한의 preemption latency라고 생각할 수 있다. (위에서 말한 epoch의 개념이다!) GENTLE_FAIR_SLEEPERS라는 것이 있다면 threash의 값을 반으로 줄인다. fair sleeper는 자고 있던 task에게도 공평하게 CPU를 할당하기 위한 개념인데 이를 gentle하게 하니 thresh값을 줄이는 것 같다. 이제 min_vruntime에서 이 thresh를 뺀 것과 자고 있던 task의 vruntime을 비교하여 더 큰 것으로 vruntime을 수정한다. 

  생각해보면 block 되어 있던 task는 normalized 된 vruntime을 가지고 있었을 것이다. 즉, 그리 크지는 않았을 것이다. 이를 min_vruntime과 비교한다는 의미가 무엇일까? 혹시라도 normalized 된 vruntime이더라도 더 클 수 있기 때문에? 그리고 vruntime을 수정하는 대부분의 코드에서 

/* ensure we never gain time by being placed backwards */

라는 문구를 찾아볼 수 있다. 이는 cfs_rq의 min_vruntime을 update 하는 함수에서도 찾아볼 수 있다. 이는 어떠한 경우라도 vruntime이 더 작아지는 방향으로는 갈 수 없다는 뜻이다. 따라서 대부분의 경우에는 

 

se->vruntime = min_vruntime - thresh

 

가 되지 않을까 예상된다. 이렇게 되면 바로 preemption이 발생하여 먼저 돌게 될 것으로 예상된다. 하지만 '충분히 오래 block 되지 않은' task들의 경우 다른 task들의 vruntime이 아직 더 작을 수 있다(min_vruntime-thresh < se->vruntime) 이럴 경우에는 preemption이 발생하지 않고 계속 runqueue에서 대기하는 것으로 예상된다.

 

5. 마치며

CFS의 중요한 역할을 하는 vruntime의 작동 원리를 나름 해석해보았다. 아마 틀린 부분도 많고, 쉽게 지나친 중요한 부분도 많을 것 같다... 궁금한 것은 왜 이렇게 찾아볼 자료가 적은 걸까? 전 세계에 linux distro가 얼마나 많은데 다들 CFS를 사용하지 않는 건가? CFS에 대한 더 자세한 것들은 어차피 바뀌지 않아서 배우지 않는 것일까? 다음에는 block 되면서 vruntime의 변화 과정도 한번 살펴보고 싶다.