Post date: Nov 30, 2016 5:41:48 AM
얼마전 슈퍼맨과 새로워진 kernel 2.6 의 schedule 소스를 보며 분명 책에서 봤던 프로세서 실행 순위를 가늠케 하는 active 배열과 expired 배열을 찾지 못해 살짝 당황하며 "책이라고 무조건 믿으면 안되겠구나..." 라는 의심을 가지게 한 부분이 있었는데.. 이제서야 그 이유를 알겠됐다...
내가 참조한 책은 kernel 2.6.10을 기준으로 설명하였고 우리가 본 kernel 소스는 2.6.28 버전이었던것이다....
다시말하자면 책은 2.6버전의 O(1) 스케줄러를 설명한 것이었고 슈퍼맨과 나는 2.6.28 버전의 CFS 스케줄러를 열심히 보고 있었던 것이었다....
아래는 정리 잘 해 놓은 블로그의 내용을 그대로 가져와 복사 해 놓은것이니 참조하기 바란다.
아래 내용을 보고 조금 아쉬운 점이 있다면 kernel 2.6에서 어떻게 kernel이 preemptive하게 돌아가는지를 새로이 추가된 tread_info와 함께 설명하지 않은 부분이다... 시간이 허락된다면 짧은 지식이지만 나라두 설명을 해 볼까 하는데.... 언제 할수 있을지 모르지만..
-.-;;
========================================================================================================
커널 2.6.23의 CFS 스케줄러.
http://monac.egloos.com/1411868 에서 간략하게 소개한 적이 있다.
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 스케줄러이다.
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는 실시간 스케줄링만 하게 고정한다면 목적을 달성할 수 있겠다. 하하...
ps. 기존의 스케줄러에서 CFS 스케줄러를 구현하는 과정을 실습으로 다루고, 스케줄러를 철저하게 분석한 책을 하나쯤
내고 싶지만 출판사는 책을 안 낼 것이고, 커널 책도 안 팔리는 마당에 이런 책은 더더욱 안 팔릴듯 싶다.
차라리 대기업이나 연구소에서 프로젝트 의뢰받아서 책(보고서)을 만들고 4천만원쯤 받는 게 더 낫겠구나... 헐헐...
(실제로 S사 같은 경우 4천만원에 커널 분석 의뢰를 합니다. 보고서가 전화번호부 정도 된다죠. 책은 한 번 받아서
1-2일 정도 훑어보고 싶으나 그래도 거기는 기밀일테니 안 봅니다. ㅋㅋ)
ps2. 그래도 책이 나오고, 책 값이 대따 비싸도(500p에 4만원 정도) 사겠다는 분이 있나요??(예상 판매 부수가 적으면 출판사는 책 가격을 높게 책정할 수 밖에 없습니다. 이런 책이 나오면 한 800부나 팔리려나요. 즉, 관심있는 분들 외에는 안 산다는 것이겠죠.)
왠지 저런 책이 나온다면 실시간 운영체제 관련 연구하는 곳이나 스케줄러와 관련 있는 곳에서 책을 살 것 같은데, 기껏해야 10권이내려나요.(연구실도 한 권 정도 사죠. 인원수만큼 사는 곳은 없잖아요. 돈도 많으면서 제본도 하더만요.)
ps3. 열차안에서 심심해서 메모장에 작성한 문서입니다. 독일 철도엔 좌석마다 콘센트가 있어요. 인터넷은 느려터졌지만,
이건 좋아요.(IC, ICE 이상은 좌석마다 있어요)
레겐스부르크에 다녀왔습니다. 내일은 가르미슈 파르텐키르헨에 다녀올 생각입니다. 추크슈피체(2964m)에 다녀올겁니다.
해발 3000m 고도에서 펼쳐지는 알프스 산맥의 장엄함을 구경해야죠.(알프스 자락이라는데 이거 알프스 산맥 맞죠??)
반팔이라 얼어죽을지도... ^^;;