Completely Fair Scheduler について

この記事はLinux advent calendar 10日目の記事です。

以前までLinux kernel はO(1)スケジューラというものを使っていました。これは「詳解Linux カーネル第３版」に詳しく説明があると思います。 この記事ではその後、v2.6.23から導入されたCompletely Fair Scheduler(CFS)についてまとめます。多分に間違いがあるかもしれないのでまさかりを投げてください。

スケジューリングとは

あまりLinuxカーネルに馴染みのない人のためにざっくりスケジューリングについて説明します。積極的に飛ばして結構です。

OSは基本的に複数のプロセスを同時に動かすように見せます。 しかし、実は短時間でプロセスを切り替えることで人間からは同時に動いているように見えているだけです。 このとき順番にプロセスを切り替えるというのが最も単純なスケジューラですが、もちろんすべてのプロセスは対等ではありませんし、 それぞれのプロセスに状態があり、デバイスの読み書きのような時間のかかることをしていて実行可能ではないプロセスも存在します。 そのため、Linuxカーネルはそこそこ複雑なスケジューリングの機構を用意することで無駄の少なく、応答性の高いシステムを実現しています。

スケジューリングクラス

Linuxはスケジューリングクラスという概念を導入しています。 これはそれぞれのプロセスが異なるスケジューリングポリシーを持つことができるというもので、v4.xでは

• stop_sched_class
• dl_sched_class
• rt_sched_class
• fair_sched_class
• idle_sched_class

の5つがあります。 これらのスケジューリングクラスは上記の順で連結リストになっていて、 上の方が優先度が高くなっています。

この中のfair_sched_class がCFSスケジューラに相当するものです。

CFS

kernel/sched/fair.cに実装があります。

CFSではプロセスを赤黒木で管理します。赤黒木は平衡２分木のひとつで値の挿入、削除、探索が でできるというデータ構造です。また、木の一番左（値が最小）の要素はキャッシュされているので で取得できます。

この赤黒木は sched_entityを要素、その中のvruntimeをキーとしています。 sched_entityはかならずしもプロセスに対応するものではありませんが、 とりあえず、プロセスに対して１つ存在すると思ってもらって大丈夫です。（Group Scheduling が絡んでいます）

赤黒木のキーとなるvruntimeですが、これはプロセスの仮想実行時間を表しています。 仮想実行時間とはその名の通りプロセスが実行された合計時間（のようなもの）です。 この仮想実行時間が短いプロセスから選んでスケジューリングすることで すべてのプロセスに平等なスケジューリングを実現しようとしています。

データ構造

スケジューリングに関する構造体は次のようなものがあります。

• task_struct
• sched_class
• sched_entity
• rq
• cfs_rq
• load_weight

順に説明していきます。

task_struct

とにかく長いです。400行以上あります。 プロセスに関する情報はすべてこの構造体に収められているのでしょうがないです。 特に大事そうなフィールドだけ紹介します。

state

プロセスの状態を簡潔に表します。次のような値をとるようです。include/linux/sched.h

#define TASK_RUNNING     0
#define TASK_INTERRUPTIBLE  1
#define TASK_UNINTERRUPTIBLE    2
#define __TASK_STOPPED      4
#define __TASK_TRACED       8
/* in tsk->exit_state */
#define EXIT_DEAD       16
#define EXIT_ZOMBIE     32
#define EXIT_TRACE      (EXIT_ZOMBIE | EXIT_DEAD)
/* in tsk->state again */
#define TASK_DEAD       64
#define TASK_WAKEKILL       128
#define TASK_WAKING     256
#define TASK_PARKED     512
#define TASK_STATE_MAX      1024

on_rq

rqにそのプロセスが入っているかどうかを表します。 rqは後述します。

prio, static_prio, normal_prio

プロセスの優先度を表します。 優先度は0から140までの値をとり、値が小さい方が優先度が高くなります。 0から99まではリアルタイム優先度、100から139までがCFSで扱うプロセスの優先度となります。 このプロセスの優先度はnice値によって決められ、nice値の -20 ~ 19が優先度の100 ~ 139にマップされてます。 また、何もしないidleプロセスは140と決められています。

sched_class

プロセスの属するスケジューリングクラスを表します。

sched_entity

プロセスに対応するsched_entityを表します。

sched_class

スケジューリングクラスを表す構造体です。

struct sched_class {
    const struct sched_class *next;

    void (*enqueue_task) (struct rq *rq, struct task_struct *p, int flags);
    void (*dequeue_task) (struct rq *rq, struct task_struct *p, int flags);
    void (*yield_task) (struct rq *rq);
    bool (*yield_to_task) (struct rq *rq, struct task_struct *p, bool preempt);

    void (*check_preempt_curr) (struct rq *rq, struct task_struct *p, int flags);

    /*
     * It is the responsibility of the pick_next_task() method that will
     * return the next task to call put_prev_task() on the @prev task or
     * something equivalent.
     *
     * May return RETRY_TASK when it finds a higher prio class has runnable
     * tasks.
     */
    struct task_struct * (*pick_next_task) (struct rq *rq,
                        struct task_struct *prev);
    void (*put_prev_task) (struct rq *rq, struct task_struct *p);

/* 中略 */

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

/* 中略 */
};

関数ポインタがたくさんあり、スケジューリングクラスごとに異なる操作を統一して行えるようにしています。 上に書いたスケジューリングクラスがそれぞれどこかで宣言されています。

sched_entity

上で説明した赤黒木のノードに対応する構造体です。

struct sched_entity {
    struct load_weight  load;       /* for load-balancing */
    struct rb_node      run_node;
    struct list_head    group_node;
    unsigned int        on_rq;

    u64         exec_start;
    u64         sum_exec_runtime;
    u64         vruntime;
    u64         prev_sum_exec_runtime;

/* 略 */
};

この中にvruntimeや実際の赤黒木のノードか収められています。 loadは優先度に基づいた重みが格納されます。

rq

これも結構長いです。 rqはrunqueueの略で実行可能なプロセス(のsched_entity)を管理する構造体です。 よく使いそうなやつだけ紹介します。

nr_running

実行可能なプロセスの数です。

cfs

CFSに属するプロセスの管理をする構造体です。

dl, rt

それぞれデッドラインスケジューラ、リアルタイムスケジューラで使われる構造体です。

cfs_rq

CFSに関連するデータを格納しています。

struct cfs_rq {
    struct load_weight load;
    unsigned int nr_running, h_nr_running;

    u64 exec_clock;
    u64 min_vruntime;

    struct rb_root tasks_timeline;
    struct rb_node *rb_leftmost;

    /*
     * '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, *next, *last, *skip;
/* 略 */
};

赤黒木の根や、その最も左のノードへのポインタなどもこの中に含まれています。

load_weight

これだけです。sched_entityやcfs_rqの中に含まれています。

struct load_weight {
    unsigned long weight;
    u32 inv_weight;
};

重みとその逆数だけです。 何の重みかは後述します。

処理

ここからはプロセスの一生を通じてどのようにスケジューリングされるかおおまかに追っていきます。

まずプロセスが生成されると、スケジューリング関連の値はsched_fork()の中で初期化されます。 そのあとtask_fork_fair()の中でsched_entityのvruntimeの値は親のvruntimeの値になります。 しかしその後place_entity() が呼ばれ、vruntimeの値はそれまでのvruntimeの値に １回実行権が与えられたときの実行時間が足されます。 これにより、次々とforkが起こる事で新たに作られたプロセスばかりが実行されないようになります。 (task_fork_fair()の中でvruntimeからcfs_rq.min_vruntimeの値が引かれていますが、これはまたenqueue_entity()のなかで足されて戻ります。 おそらく眠りから覚めたプロセスと扱いを揃えるため？)

また、sched_entity中のload.weightがプロセスのstatic_prioに基づいてset_load_weight()で初期化されます。 実際の重みは優先度ごとにあらかじめ値が決められています。(prio_to_weight[]) 重みは優先度が高いほど大きく、優先度が低いほど小さく定められています。式で書くと weight = 1.25^(-nice) * 1024ぐらいみたいです。 最後にdo_fork()からwake_up_new_task()が呼ばれ、プロセスが赤黒木に入ります。

その後、schedule()の中でpick_next_task()が呼ばれることで次に実行するプロセスを選択します。 プロセスの選択はまず、すべての実行可能なプロセスがCFSクラスに属するとき、直接CFSクラスのpick_next_task()を、 そうでないときは、すべてのスケジューリングクラスのpick_next_task()を順に呼び出しています。 CFSでは次に赤黒木の最も左の要素(次に実行されるプロセスのsched_entity)を削除し、それまで走っていたプロセスのsched_entityを木に挿入するという操作をします。

また、pick_next_task_fair()の中のupdate_curr()で、 それまで走っていたプロセスのvruntimeに実行時間が重みで割られた値が足されます。これにより優先度が高いプロセスはほとんど実行されてないとみなされ、 優先的に実行されやすくなります。一方優先度の低いプロセスは長い間実行されたとみなされるため、次に実行されるのはしばらくあとになる可能性が高くなります。

これを繰り返すことで、常に仮想実行時間のもっとも小さいプロセスが選択されて、平等に（感じられるように）スケジューリングが進んでいきます。

プロセスが死ぬときは、do_exit()の中でtsk->state = TASK_DEADと設定することで、__schedule()の中で prev->on_rqが0になり、pick_next_task()の中でput_prev_entity()が呼ばれても、そのプロセスを赤黒木に挿入しなくなります。

以上で終わりです。

あまり時間がなくてこの程度のことしか調べられませんでしたが、実際のところはこれに加えて SMPにおけるロードバランシングや、グループスケジューリングによりもっと複雑なことをしています。

ほんとはもっとちゃんとまとめる形にしたかったのですが、 こんな乱文になってしまい無念..

参考文献

• 詳解Linux カーネル第３版

• Linux カーネル 2.6 Completely Fair Scheduler の内側

• （・・）！ • Linuxスケジューラ - 概要

• http://criticalblue.com/news/wp-content/uploads/2013/12/linux_scheduler_notes_final.pdf