各スケジューリングクラス

前回、下記クラスの概要について述べました。徐々に核心部分に近づいていきます。今回は各クラスをもう少し掘り下げてみていきたいと思います。
1.STOPクラス
2.DEADLINEクラス
3.RTクラス
4.FAIRクラス
5.IDLEクラス

本内容は量が多いため、1を「その3-1」、2～3を「その3-2」、4～5を「その3-3」と分割して述べていきます。

sched_class構造体

各クラスのスケジューリングアルゴリズムの前に非常に重要な構造体を説明します。sched_class構造体です。本構造体は各クラスごとに定義し、スケジューラコアからは本構造体のメンバ経由で呼び出されます。
本構造体は基本的には関数ポインタのメンバで構成されていて、スケジューラコアからは関数ポインタで呼び出されます。
下記に構造体の定義と各メンバで何をするのかコメントで記載していきます。
なお、コードを読解しやすくするためにUPシステムを想定して述べます。（CONFIG_SMPで囲まれている箇所は割愛）

kernel/sched/sched.h

struct sched_class {
        const struct sched_class *next; 
        //次の優先度のスケジューリング クラスを指す。優先度は本ページの先頭に記載した1～5の順

        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);
        //currentプロセスがCPU実行権を一時的に明渡す時の処理を定義
        bool (*yield_to_task)(struct rq *rq, struct task_struct *p, bool preempt);
        //指定したプロセスにCPU実行権を渡す処理。fairクラスでのみ使用する
        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,
                                               struct rq_flags *rf);
       //次に実行するプロセスを決定して、そのプロセスを示す構造体（task_struct）を返す処理を定義
        void (*put_prev_task)(struct rq *rq, struct task_struct *p);
       //CPUの実行権を明渡したプロセスを引数で指定して呼び出す処理を定義

        void (*set_curr_task)(struct rq *rq);
       //スケジューリングクラスを変更する時に実施する処理を定義
        void (*task_tick)(struct rq *rq, struct task_struct *p, int queued);
       //タイマー割込みから呼び出される処理を定義
        void (*task_fork)(struct task_struct *p);
       //プロセス生成時の処理を定義
        void (*task_dead)(struct task_struct *p);
       //プロセス終了時の処理を定義
        /*
         * The switched_from() call is allowed to drop rq->lock, therefore we
         * cannot assume the switched_from/switched_to pair is serliazed by
         * rq->lock. They are however serialized by p->pi_lock.
         */
        void (*switched_from)(struct rq *this_rq, struct task_struct *task);
       //スケジューリングクラスを変更する時の処理を定義
        void (*switched_to)  (struct rq *this_rq, struct task_struct *task);
       //スケジューリングクラスを変更する時の処理を定義
        void (*prio_changed) (struct rq *this_rq, struct task_struct *task,
                              int oldprio);
      //プロセスの優先度が変更された時に実施する処理を定義
        unsigned int (*get_rr_interval)(struct rq *rq,
                                        struct task_struct *task);
      //ラウンドロビン型プロセスのラウンドロビンするタイムスライスを返す処理を定義。
        void (*update_curr)(struct rq *rq);
      //現在のプロセスの統計情報を取得する処理を定義
# define TASK_SET_GROUP          0
# define TASK_MOVE_GROUP         1

# ifdef CONFIG_FAIR_GROUP_SCHED
        void (*task_change_group)(struct task_struct *p, int type);
     //グループを変更した時に行う処理を実施
# endif
};

これらのメンバーの中で2点ほど補足します。
（1）スケジューリングクラスの変更
本記事を読まれている方は「各プロセスのスケジューリングクラスは一度設定すれば、その後は変更することはほとんどないんじゃないの？」と思われると思います。
実はユーザーの見えないカーネル内部ではスケジューリングクラスの変更が頻繁に行われています。最たる例は、優先度継承です。優先度継承の詳細はZephyr入門（排他制御：mutex編）を参照してください。
例えば、高優先度プロセスAがRTクラス、低優先度プロセスBが一般クラスの時、低優先度プロセスBが保持しているmutexを高優先度プロセスAが取得しようとすると優先度継承が行われます。
この時、低優先度プロセスBが高優先度Aの優先度までブーストされる為、一般クラスからRTクラスにクラス変更されます。そして、優先度継承の終了時はRTクラスから元の一般クラスに戻ります。

（2）グループの変更
cgroupという言葉を聞いた事はありますか？
各プロセス群をグルーピングしてそれぞれのグループに対して使用できる資源を割り当てる機能のことです。
以前カーネルドキュメントにあった例だと、教師グループ、生徒グループを定義して全員をいずれかのグループに設定します。
コアが4つある場合、1つを教師グループ、3つを生徒グループに割当てることで生徒グループのコア群が高負荷になっても教師グループの先生は割り当てられている1コアを使用でき、コマンドレスポンス/GUIが遅いという事を防げます。
グループの変更と言うのは生徒グループから教師グループに変更、といったことを指しています。

rq構造体

sched_class構造体以外にもう一つ重要な構造体があります。
本構造体はCPUごとに存在します。
sched_class構造体は各スケジューリングクラスの処理を定義しているのに対してrq構造体（以後、ランキューと述べます）はスケジューラを正常に動作させる為の構造体と思っていただいて構いません。本構造体のメンバはここでは説明せずに後述する説明で出てきたときに述べたいと思います。

kernel/sched/sched.h

/*
 * This is the main, per-CPU runqueue data structure.
 *
 * Locking rule: those places that want to lock multiple runqueues
 * (such as the load balancing or the thread migration code), lock
 * acquire operations must be ordered by ascending &runqueue.
 */
struct rq {
        /* runqueue lock: */
        raw_spinlock_t          lock;

        /*
         * nr_running and cpu_load should be in the same cacheline because
         * remote CPUs use both these fields when doing load calculation.
         */
        unsigned int            nr_running;

        #define CPU_LOAD_IDX_MAX 5
        unsigned long           cpu_load[CPU_LOAD_IDX_MAX];
# ifdef CONFIG_NO_HZ_COMMON
        unsigned int            nohz_tick_stopped;
        atomic_t nohz_flags;
# endif /* CONFIG_NO_HZ_COMMON */

        /* capture load from *all* tasks on this CPU: */
        struct load_weight      load;
        unsigned long           nr_load_updates;
        u64                     nr_switches;

        struct cfs_rq           cfs;
        struct rt_rq            rt;
        struct dl_rq            dl;

# ifdef CONFIG_FAIR_GROUP_SCHED
        /* list of leaf cfs_rq on this CPU: */
        struct list_head        leaf_cfs_rq_list;
        struct list_head        *tmp_alone_branch;
# endif /* CONFIG_FAIR_GROUP_SCHED */

        /*
         * This is part of a global counter where only the total sum
         * over all CPUs matters. A task can increase this counter on
         * one CPU and if it got migrated afterwards it may decrease
         * it on another CPU. Always updated under the runqueue lock:
         */
        unsigned long           nr_uninterruptible;

        struct task_struct      *curr;
        struct task_struct      *idle;
        struct task_struct      *stop;
        unsigned long           next_balance;
        struct mm_struct        *prev_mm;

        unsigned int            clock_update_flags;
        u64                     clock;
        u64                     clock_task;

        atomic_t                nr_iowait;

# ifdef CONFIG_IRQ_TIME_ACCOUNTING
        u64                     prev_irq_time;
# endif
# ifdef CONFIG_PARAVIRT
        u64                     prev_steal_time;
# endif
# ifdef CONFIG_PARAVIRT_TIME_ACCOUNTING
        u64                     prev_steal_time_rq;
# endif

        /* calc_load related fields */
        unsigned long           calc_load_update;
        long                    calc_load_active;
# ifdef CONFIG_SCHED_HRTICK
        struct hrtimer          hrtick_timer;
# endif

# ifdef CONFIG_SCHEDSTATS
        /* latency stats */
        struct sched_info       rq_sched_info;
        unsigned long long      rq_cpu_time;
        /* could above be rq->cfs_rq.exec_clock + rq->rt_rq.rt_runtime ? */

        /* sys_sched_yield() stats */
        unsigned int            yld_count;

        /* schedule() stats */
        unsigned int            sched_count;
        unsigned int            sched_goidle;

        /* try_to_wake_up() stats */
        unsigned int            ttwu_count;
        unsigned int            ttwu_local;
# endif

# ifdef CONFIG_SMP
        struct llist_head       wake_list;
# endif

# ifdef CONFIG_CPU_IDLE
        /* Must be inspected within a rcu lock section */
        struct cpuidle_state    *idle_state;
# endif
};

各クラスのsched_class構造体メンバの処理内容

1.STOPクラス

本クラスのsched_class構造体を以下に示します。

kernel/sched/stop_task.c

const struct sched_class stop_sched_class = {
        .next                   = &dl_sched_class,

        .enqueue_task           = enqueue_task_stop,
        .dequeue_task           = dequeue_task_stop,
        .yield_task             = yield_task_stop,

        .check_preempt_curr     = check_preempt_curr_stop,

        .pick_next_task         = pick_next_task_stop,
        .put_prev_task          = put_prev_task_stop,

        .set_curr_task          = set_curr_task_stop,
        .task_tick              = task_tick_stop,

        .get_rr_interval        = get_rr_interval_stop,

        .prio_changed           = prio_changed_stop,
        .switched_to            = switched_to_stop,
        .update_curr            = update_curr_stop,
};

・ nextメンバ
これは次の優先度のsched_class構造体を示します。
STOPクラスの次に優先度が高いDEADLINEクラスの構造体dl_sched_classを指しています。

・enqueue_taskメンバ

kernel/sched/stop_task.c

static void
enqueue_task_stop(struct rq *rq, struct task_struct *p, int flags)
{
        add_nr_running(rq, 1);
}

本関数はCPU毎に保持しているランキューのnr_runningメンバをインクリメントしています。
nr_runningメンバは実行可能状態のプロセス数を保持します。

・dequeue_taskメンバ

kernel/sched/stop_task.c

static void
dequeue_task_stop(struct rq *rq, struct task_struct *p, int flags)
{
        sub_nr_running(rq, 1);
}

本関数はenqueue_taskメンバの逆です。ランキューの実行可能プロセス数nr_runningメンバをデクリメントします。

・yield_taskメンバ

kernel/sched/stop_task.c

static void yield_task_stop(struct rq *rq)
{
        BUG(); /* the stop task should never yield, its pointless. */
}

STOPクラスのプロセスはCPU実行権を自ら手放すことを許しません。
処理を最後まで完遂させる必要があります。
従って、本関数が呼ばれるとBUG( ) （警告：カーネルバグ）でコンソールに警告を出力します。

・check_preempt_currメンバ

kernel/sched/stop_task.c

static void
check_preempt_curr_stop(struct rq *rq, struct task_struct *p, int flags)
{
        /* we're never preempted */
}

stopクラスは最高優先度のためプリエンプションされません。この為、空関数になっています。
なお、プリエンプションというのは「高優先度プロセスが実行可能となった時に低優先度プロセスからCPUの実行権を奪って処理を行うこと」です。下図を参考ください。

・pick_next_taskメンバ

kernel/sched/stop_task.c

static struct task_struct *
pick_next_task_stop(struct rq *rq, struct task_struct *prev, struct rq_flags *rf)
{
1        struct task_struct *stop = rq->stop;

2        if (!stop || !task_on_rq_queued(stop))
3                return NULL;

4        put_prev_task(rq, prev);

5        stop->se.exec_start = rq_clock_task(rq);

6        return stop;
}

1行目で、ランキューのstopメンバを取り出して、stopクラスのメンバーが存在しない場合はNULLを返します（2行目、3行目）

4行目は以下の通り、stopクラスのput_prev_taskメンバを呼び出します。

kernel/sched/sched.h

static inline void put_prev_task(struct rq *rq, struct task_struct *prev)
{
        prev->sched_class->put_prev_task(rq, prev);
}

kernel/sched/stop_task.c

static void put_prev_task_stop(struct rq *rq, struct task_struct *prev)
{
1        struct task_struct *curr = rq->curr;
2        u64 delta_exec;

3        delta_exec = rq_clock_task(rq) - curr->se.exec_start;
4        if (unlikely((s64)delta_exec < 0))
5                delta_exec = 0;

6        schedstat_set(curr->se.statistics.exec_max,
7                        max(curr->se.statistics.exec_max, delta_exec));

8        curr->se.sum_exec_runtime += delta_exec;
9        account_group_exec_runtime(curr, delta_exec);

10        curr->se.exec_start = rq_clock_task(rq);
11        cgroup_account_cputime(curr, delta_exec);
}

3行目で現在のプロセスの実行時間を求めます。（現在の時間 - 現在のプロセスの開始時間）
4、5行目は実行時間が負の場合、delta_execに0を入れます。
6、7行目は統計情報を設定しています。これは/proc/schedstatでユーザー空間に見せます。

8、9行目で現在のプロセスの実行時間を加算しています。
10行目で現在のプロセスの開始時間を現時点の時間に設定します。
11行目はcgroupの使用帯域の元になるCPU実行時間を加算しています。

端的に述べると、本関数の肝は1行目のランキューのstopで設定されているプロセスを返すということです。

・put_prev_taskメンバ
本メンバの説明はpick_next_taskメンバの中で説明したため、割愛します。

・set_curr_taskメンバ

kernel/sched/stop_task.c

static void set_curr_task_stop(struct rq *rq)
{
1        struct task_struct *stop = rq->stop;

2        stop->se.exec_start = rq_clock_task(rq);
}

1行目でランキューのstopメンバをstopに設定します。
2行目で現在の時間をstopのexec_startに設定します。

・task_tickメンバ

kernel/sched/stop_task.c

static void task_tick_stop(struct rq *rq, struct task_struct *curr, int queued)
{
}

stopクラスでは空関数です。

・get_rr_intervalメンバ

kernel/sched/stop_task.c

static unsigned int
get_rr_interval_stop(struct rq *rq, struct task_struct *task)
{
        return 0;
}

0を返します。

・prio_changedメンバ

kernel/sched/stop_task.c

static void
prio_changed_stop(struct rq *rq, struct task_struct *p, int oldprio)
{
        BUG(); /* how!?, what priority? */
}

stopクラスでは優先度という概念は存在しないため、本関数が呼ばれたらBUG( )で警告を出力します。

・switched_toメンバ

kernel/sched/stop_task.c

static void switched_to_stop(struct rq *rq, struct task_struct *p)
{
        BUG(); /* its impossible to change to this class */
}

stopクラスでプロセススイッチすることはできないため、本関数が呼ばれたらBUG( )で警告を出力します。

・update_currメンバ

kernel/sched/stop_task.c

static void update_curr_stop(struct rq *rq)
{
}

空関数です。

以上で、stopクラスの各関数を一通り見ました。（文字にすると長い…。）
次回はdeadlineクラスとrtクラスを見ます。
なお、スケジューラを理解するにあたって、rtクラスとfair（一般）クラスを理解することが肝だと考えています。

その後、コア部を読解することでコア部と各クラスの処理内容が結びつき、スケジューラをざっくり理解していただければ、と思います。

初回：【読解入門】Linuxカーネル（概要編）
前回：【読解入門】Linuxカーネル（スケジューラ編その2）
次回：【読解入門】Linuxカーネル（スケジューラ編その3-2）