各スケジューリングクラス
前回、下記クラスの概要について述べました。徐々に核心部分に近づいていきます。今回は各クラスをもう少し掘り下げてみていきたいと思います。
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で囲まれている箇所は割愛）
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構造体（以後、ランキューと述べます）はスケジューラを正常に動作させる為の構造体と思っていただいて構いません。本構造体のメンバはここでは説明せずに後述する説明で出てきたときに述べたいと思います。
/*
* 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構造体を以下に示します。
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メンバ
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メンバ
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メンバ
static void yield_task_stop(struct rq *rq)
{
BUG(); /* the stop task should never yield, its pointless. */
}
STOPクラスのプロセスはCPU実行権を自ら手放すことを許しません。
処理を最後まで完遂させる必要があります。
従って、本関数が呼ばれるとBUG( ) （警告：カーネル バグ）でコンソールに警告を出力します。
・check_preempt_currメンバ
static void
check_preempt_curr_stop(struct rq *rq, struct task_struct *p, int flags)
{
/* we're never preempted */
}
stopクラスは最高優先度のためプリエンプションされません。この為、空関数になっています。
なお、プリエンプションというのは「高優先度プロセスが実行可能となった時に低優先度プロセスからCPUの実行権を奪って処理を行うこと」です。下図を参考ください。
・pick_next_taskメンバ
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メンバを呼び出します。
static inline void put_prev_task(struct rq *rq, struct task_struct *prev)
{
prev->sched_class->put_prev_task(rq, prev);
}
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メンバ
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メンバ
static void task_tick_stop(struct rq *rq, struct task_struct *curr, int queued)
{
}
stopクラスでは空関数です。
・get_rr_intervalメンバ
static unsigned int
get_rr_interval_stop(struct rq *rq, struct task_struct *task)
{
return 0;
}
0を返します。
・prio_changedメンバ
static void
prio_changed_stop(struct rq *rq, struct task_struct *p, int oldprio)
{
BUG(); /* how!?, what priority? */
}
stopクラスでは優先度という概念は存在しないため、本関数が呼ばれたらBUG( )で警告を出力します。
・switched_toメンバ
static void switched_to_stop(struct rq *rq, struct task_struct *p)
{
BUG(); /* its impossible to change to this class */
}
stopクラスでプロセス スイッチすることはできないため、本関数が呼ばれたらBUG( )で警告を出力します。
・update_currメンバ
static void update_curr_stop(struct rq *rq)
{
}
空関数です。
以上で、stopクラスの各関数を一通り見ました。（文字にすると長い…。）
次回はdeadlineクラスとrtクラスを見ます。
なお、スケジューラを理解するにあたって、rtクラスとfair（一般）クラスを理解することが肝だと考えています。
その後、コア部を読解することでコア部と各クラスの処理内容が結びつき、スケジューラをざっくり理解していただければ、と思います。
初回：【読解入門】Linuxカーネル （概要編）
前回：【読解入門】Linuxカーネル （スケジューラ編その2）
次回：【読解入門】Linuxカーネル （スケジューラ編その3-2）