리눅스 스케쥴러의 변천사 O(1), CFS

출처: http://tory45.egloos.com/5167290

CFS 스케줄러는 Con Kolivas의 스케줄러 개선에 기인한다.

Ingo Monlar는 커널 2.4의 스케줄러를 대체할 새로운 스케줄러를 작성했었고, 그것이 현재 커널 2.6에 적용된 O(1) 스케줄러였었다.

O(1) 스케줄러는 커널 2.4에 가장 많이 백포팅된 알고리즘이었다. 대부분의 커널 2.4 기반 상용 배포판들은 O(1) 스케줄러를 백포팅하였다. 실제로 프로세스의 개수가 많을 때 스케줄러에 의한 성능차이는 현격하게 벌어진다.
(책에서는 백포팅하는 법을 소개하고, 성능 비교를 하였다. 불행히도 완전한 백포팅이 아니었기 때문에 책에서 소개한 방법은
완전한 O(1) 스케줄러 백포팅은 아니었다)

커널 2.6에 도입된 O(1) 스케줄러는 대부분의 경우에 잘 동작했으나 사용자에 따라 동작이 제대로 되는 경우와 안되는 경우가 공존했다.

때문에 Con Kolivas는 O(1) 스케줄러를 개선하는 방향으로 성능 개선된 버전을 만들어내었고, 인터랙티비 평가를 이용하려는 시도를 한다. Interactivity Estimator는 사용도 평가라 할 수 있다. 이 프로세스가 CPU를 집중적으로 사용하는지(CPU Bound Process), I/O만 집중적으로 하는 프로세스(I/O Bound Process), 백그라운드 작업만 하는 프로세스(Batch process)인지를 구분하기 위한 것이었다. 운영체제 시간에 이런 프로세스에 대해 학습하지만 실제로는 이들 프로세스를 구분하는 방법은 존재하지 않는다.

통계에 기반하여 프로세스를 구분하려는 시도를 했고, 사용자 반응성을 더 좋게하려고 시도했지만 더 많은 문제를 만들어냈고, 의도했던 대로 동작하지 않았다. 하나를 고친 것이 다른 문제를 열어버리기도 했다.

Con Kolivas는 완전히 역발상을 하게 된다. 프로세스를 구분하기 위해 커널에서 사용하는 모든 평가(estimation)를 제거한다.
마찬가지로, Interativity Estimator도 제거하고, 이 프로세스가 CPU Bound인가, I/O Bound인가도 구분하지 않는다.
O(1) 스케줄러의 O(1)은 그대로 유지하면서 CPU 할당 시간의 공평한 분배(fairness)에 따른 스케줄러를 구현한다.

- RSDL(Rotating Staircase Deadline Scheduler)    
http://lwn.net/Articles/224654/

Con Kolivas가 제안했던 RSDL은 커널 2.6의 메인 스케줄러와 동일한 큐를 이용한다. 커널 2.6의 O(1) 스케줄러는 active 배열과 expired 배열을 갖고 있고, 할당 시간(time quantum)을 소비한 프로세스는 expired 배열로 이동하는 방식이었지만, RSDL에서는 상위 우선 순위의 모든 프로세스가 라운드 로빈으로 실행되고, 할당 시간을 모두 소비하면 한 단계 낮은 우선순위로 프로세스를 이동시키고 새로운 할당 시간을 부여한다. 모든 프로세스는 다시 라운드 로빈으로 실행되고, 모든 시간을 소비하면 다음 단계로 프로세스를 모두 이동시킨다. 즉, 계단(Staircase)처럼 한 계단씩 내려가면서 실행한다.
또한, 각 우선순위에 해당하는 큐는 각 큐 별로 CPU 사용량(CPU Time Quotas)가 제한되어 있다. 같은 우선순위에 있는 프로세스들이 라운드 로빈으로 실행중이고, 프로세스에 CPU 할당 시간이 남아있어도 해당 우선순위 큐의 사용량을 모두 사용하면 모든 프로세스는 강제로 다음 우선순위 큐로 이동하게 된다. 따라서, 가장 낮은 우선 순위에 있는 프로세스도 정해진 시간(deadline)만큼만 대기하면 실행되는 것을 보장할 수 있다.(해당 우선순위 큐의 실행시간은 정확하게 정해지므로 hard dealine이지만, 해당 우선순위 큐에서는 라운드 로빈으로 실행되고, 실행순서가 보장되지 않기 때문에 약간의 지연 시간이 생길 수 있다. 즉, soft deadline이 된다)

그 이후의 연속된 패치에서 수행성능 개선이 크다는 것을 보여줬고, Ingo Monlar는 Con Kolivas의 아이디어에 기초해서 
완전히 새로운 스케줄러를 개발하였다. 이 스케줄러의 이름이 CFS 스케줄러이다.

- CFS (Completely Fair Scheduler)

O(1) 스케줄러의 등장이 스케줄링 알고리즘에 있어서 가장 큰 변화였다면, CFS 스케줄러의 등장은 그에 비견될만한 가장 큰 변화 중에 하나다. CFS 스케줄러는 실행큐(runqueue) 배열을 제거했고, 모든 프로세스의 실행 상태를 관리하기 위해 RB-tree 구조를 사용한다. 트리의 가장 왼쪽에 있는 프로세스는 언제나 원하는 시점에 CPU 제어권을 잡을 수 있다. 즉, 반응성이 높다. 이 스케줄러 구조에서 핵심은 트리 구조에 프로세스를 추가하기 위한 키 값을 어떻게 결정하는가 하는 것이다. RB-tree 구조 자체는 리눅스 커널의 공통 자료구조를 사용한다.

CFS 스케줄러의 특징은 1. 더 이상 지피값(jiffies)을 사용하지 않는다, 2. 더 이상 HZ 상수에도 의존하지 않는다. 3. 나노초 단위의 정밀도로 동작한다.(기존 스케줄러는 지피값에 의존했으며, 밀리초 단위의 정밀도였다), 4. 더 이상 통계적 기법이나 휴리스틱 기법에 의존하지 않는다.(데드라인 방식이므로)

include/linux/sched.h 헤더 파일의 변화부터 살펴보자.

+struct sched_class {

+       struct sched_class *next;

+

+       void (*enqueue_task) (struct rq *rq, struct task_struct *p,

+                             int wakeup, u64 now);

+       void (*dequeue_task) (struct rq *rq, struct task_struct *p,

+                             int sleep, u64 now);

+       void (*yield_task) (struct rq *rq, struct task_struct *p);

+

+       void (*check_preempt_curr) (struct rq *rq, struct task_struct *p);

+

+       struct task_struct * (*pick_next_task) (struct rq *rq, u64 now);

+       void (*put_prev_task) (struct rq *rq, struct task_struct *p, u64 now);

+

+       int (*load_balance) (struct rq *this_rq, int this_cpu,

+                       struct rq *busiest,

+                       unsigned long max_nr_move, unsigned long max_load_move,

+                       struct sched_domain *sd, enum cpu_idle_type idle,

+                       int *all_pinned, unsigned long *total_load_moved);

+

+       void (*set_curr_task) (struct rq *rq);

+       void (*task_tick) (struct rq *rq, struct task_struct *p);

+       void (*task_new) (struct rq *rq, struct task_struct *p);

+};

sched_class 구조체의 역할은 분명하다. 지금까지의 스케줄러는 한 가지 스케줄러만 있었다. 

커널의 다른 부분과 마찬가지로 프로세스 스케줄러도 교체할 수 있게 하기 위한 목적으로 새로운 레이어가 추가되었다.

문자 디바이스 드라이버에서 file_operations 구조체가 인터페이스 역할을 하는 것과 동일하다.

함수의 이름으로부터 대충 어떤 일을 하기 위한 것인지 예상할 수 있을 것이다.

+/*

+ * CFS stats for a schedulable entity (task, task-group etc)

+ *

+ * Current field usage histogram:

+ *

+ *     4 se->block_start

+ *     4 se->run_node

+ *     4 se->sleep_start

+ *     4 se->sleep_start_fair

+ *     6 se->load.weight

+ *     7 se->delta_fair

+ *    15 se->wait_runtime

+ */

+struct sched_entity {

+       long                    wait_runtime;

+       unsigned long           delta_fair_run;

+       unsigned long           delta_fair_sleep;

+       unsigned long           delta_exec;

+       s64                     fair_key;

+       struct load_weight      load;           /* for load-balancing */

+       struct rb_node          run_node;

+       unsigned int            on_rq;

+

+       u64                     wait_start_fair;

+       u64                     wait_start;

+       u64                     exec_start;

+       u64                     sleep_start;

+       u64                     sleep_start_fair;

+       u64                     block_start;

+       u64                     sleep_max;

+       u64                     block_max;

+       u64                     exec_max;

+       u64                     wait_max;

+       u64                     last_ran;

+

+       u64                     sum_exec_runtime;

+       s64                     sum_wait_runtime;

+       s64                     sum_sleep_runtime;

+       unsigned long           wait_runtime_overruns;

+       unsigned long           wait_runtime_underruns;

+#ifdef CONFIG_FAIR_GROUP_SCHED

+       struct sched_entity     *parent;

+       /* rq on which this entity is (to be) queued: */

+       struct cfs_rq           *cfs_rq;

+       /* rq "owned" by this entity/group: */

+       struct cfs_rq           *my_q;

+#endif

+};

스케줄링과 관련된 것의 대부분은 sched_entity 구조체에서 관리한다.

task_struct 구조체에는 다음 두 멤버가 추가되었다.(앞에서 정의한 구조체 두 개)

+       struct sched_class *sched_class;

+       struct sched_entity se;

+struct rt_prio_array {

+       DECLARE_BITMAP(bitmap, MAX_RT_PRIO+1); /* include 1 bit for delimiter */

+       struct list_head queue[MAX_RT_PRIO];

+};

+

+struct load_stat {

+       struct load_weight load;

+       u64 load_update_start, load_update_last;

+       unsigned long delta_fair, delta_exec, delta_stat;

+};

실시간 스케줄링에서의 우선 순위 관리를 위한 구조체가 선언된다.

load_stat은 스케줄링과 관련된 시간들을 업데이트한다.

두 가지 구조체 모두 기존에는 하나의 스케줄러였기에 하나로 되어 있던 것이 별도의 구조체로 분리되었다.

예를 들어, 일반 스케줄링시에는 실시간 스케줄링과 관련된 멤버가 필요하지 않다.

+/* CFS-related fields in a runqueue */

+struct cfs_rq {

+       struct load_weight load;

+       unsigned long nr_running;

+

+       s64 fair_clock;

+       u64 exec_clock;

+       s64 wait_runtime;

+       u64 sleeper_bonus;

+       unsigned long wait_runtime_overruns, wait_runtime_underruns;

+

+       struct rb_root tasks_timeline;

+       struct rb_node *rb_leftmost;

+       struct rb_node *rb_load_balance_curr;

+#ifdef CONFIG_FAIR_GROUP_SCHED

+       /* 'curr' points to currently running entity on this cfs_rq.

+        * It is set to NULL otherwise (i.e when none are currently running).

+        */

+       struct sched_entity *curr;

+       struct rq *rq;  /* cpu runqueue to which this cfs_rq is attached */

+

+       /* leaf cfs_rqs are those that hold tasks (lowest schedulable entity in

+        * a hierarchy). Non-leaf lrqs hold other higher schedulable entities

+        * (like users, containers etc.)

+        *

+        * leaf_cfs_rq_list ties together list of leaf cfs_rq's in a cpu. This

+        * list is used during load balance.

+        */

+       struct list_head leaf_cfs_rq_list; /* Better name : task_cfs_rq_list? */

+#endif

+};

 

+/* Real-Time classes' related field in a runqueue: */

+struct rt_rq {

+       struct rt_prio_array active;

+       int rt_load_balance_idx;

+       struct list_head *rt_load_balance_head, *rt_load_balance_curr;

+};

CFS 스케줄링은 cfs_rq 구조체를 이용하고, 실시간 스케줄링은 rt_rq 구조체를 사용한다.

커널 2.6.22까지는 kernel/sched.c에 스케줄러의 모든 것이 구현되어 있었지만 커널 2.6.23부터는 sched_class 가상함수테이블(VFT, Virtual Function Table)을 사용한다. 하나의 레이어가 추가되었다.

따라서, 실시간 스케줄링과 관련된 내용은 sched_rt.c에 구현되어 있으며, CFS 스케줄링과 관련된 내용은 sched_fair.c에 구현되어 있다.

+struct sched_class fair_sched_class __read_mostly = {

+       .enqueue_task           = enqueue_task_fair,

+       .dequeue_task           = dequeue_task_fair,

+       .yield_task             = yield_task_fair,

+

+       .check_preempt_curr     = check_preempt_curr_fair,

+

+       .pick_next_task         = pick_next_task_fair,

+       .put_prev_task          = put_prev_task_fair,

+

+       .load_balance           = load_balance_fair,

+

+       .set_curr_task          = set_curr_task_fair,

+       .task_tick              = task_tick_fair,

+       .task_new               = task_new_fair,

+};

이들 함수를 토대로 찾으면 될 겁니다.

sched_rt.c에 구현된 실시간 스케줄러는 연결 리스트 기반으로 동작하며,
sched_fair.c에 구현된 CFS 스케줄러는 RB 트리 기반으로 동작합니다.


마지막으로 task_struct 구조체에 추가된 sched_class 멤버에 대해 생각해보자.

 struct sched_class *sched_class;

포인터로 되어 있는데 이는 해당 프로세스가 어떤 스케줄러에 속해있는지를 의미한다.

다시 말해, SMP 환경에서 0번 CPU는 CFS 스케줄링을 실행할 수 있고, 1번 CPU는 실시간 스케줄링을 실행할 수 있다는 것을 의미한다.

- 이기종 코어상의 다중 운영체제 구현
http://monac.egloos.com/1302743

에서 얘기했던 것이 커널 2.6.23부터는 현실이 된 것이다. ^^;

그나저나 이쪽 작업하던 분들은 하던거 마무리하고 끝내는 수준이 되겠구나. 커널 2.6.23부터 지원이 되니, 이를 조금 수정해서
0번 CPU는 CFS 스케줄링만하고, 1번 CPU는 실시간 스케줄링만 하게 고정한다면 목적을 달성할 수 있겠다. 하하...