<style>
/* code要素の設定。バッククォーテーションで囲まれた要素に対する設定。 */
.markdown-body code {
font-family: 'Roboto Mono', menlo, monospace;
font-size: 0.9em;
line-height: 1em;
color: #0177aa !important;
background-color: transparent !important;
}
/* codeの前後に挿入される空白を消す */
.markdown-body code::before,
.markdown-body code::after { content: ""; }
/* code block */
.markdown-body pre code {
color: black !important;
}
/* リンクの見た目 */
.markdown-body a {
color: inherit; /* 色は本文と同じ */
text-decoration: underline dashed #BDBDBD 0.1em; /* 下線のスタイル */
text-underline-offset: 0.3em; /* 下線の位置の調整 */
}
/* リンク要素の上にマウスが乗ったときの見た目 */
.markdown-body a:hover {
text-decoration: underline dashed #E080A0 0.1em;
text-underline-offset: 0.3em;
}
/* 下線の設定。++で囲まれた要素につく下線のスタイルを設定する。 */
ins {
text-decoration: underline solid black 0.05em;
text-underline-offset: 0.25em;
}
p {
font-family: Roboto Condensed;
}
.markdown-body mark {
padding: 0;
background: linear-gradient(transparent 60%, #FDBF60 60%);
}
</style>
# 概要
sched_class はv2.6.23で導入された。
スケジューラの各所で呼び出されるコールバック関数を寄せ集めた構造体であり、異なるスケジューリングポリシー（RTやFAIRなど）を実現するために、いくつかのインスタンスがカーネルに実装されている。
sched_class は、一種のスケジューラの抽象化を行うものだと思うのだが、どのように抽象化を行っているのか、などの文献は見つけることができない。ただし、2020年ごろにスケジューラ周りのドキュメントを充実させようという議論があり、sched_classに関する説明も少し書かれていたので、見てみると良さそう。
https://lwn.net/ml/linux-doc/20200507180553.9993-3-john.mathew@unikie.com/
色々と調べてきて思ったのは、これは完全な抽象化というわけではなさそう、ということである。スケジューラのコア部の至るところで呼び出されるコールバック関数の寄せ集めに過ぎず、このクラスが単体で意味を持ったものとしてみることは難しそう。
# === UP部分 ===
# enqueue_task
```c
void enqueue_task(struct rq *rq, struct task_struct *p, int flags);
```
フラグに使われるのは以下のマクロたち（[kernel/sched/sched.h:1634](https://elixir.bootlin.com/linux/v5.1.21/source/kernel/sched/sched.h#L1634)）。フラグの主な目的は（非公式ではあるが）[ここ](https://lwn.net/ml/linux-doc/20200507180553.9993-3-john.mathew@unikie.com/#:~:text=The%20main%20purpose%20of%20the%0A%2B%20%20%20%20flags%20is%20to%20describe%20why%20the%20enqueue%20or%20dequeue%20is%20being%20called.)で説明されている。その説明によると、++なぜそのタスクがenqueue/dequeueされたのかを意味する++らしい。
|フラグ|値|意味|
|-|-|-|
|ENQUEUE_WAKEUP |0x01| タスクが丁度実行可能になった。 |
|ENQUEUE_RESTORE |0x02| DEQUEUE_SAVEとペアで使用される。一時的にキューを移動するときに使用される？直線の状態を保存してキューから取り出し、その保存した状態を復元して戻すときに指定される。 |
|ENQUEUE_MOVE |0x04| キュー間を移動するときに指定される。直前の状態は保存しないため、SAVE/RESTOREとは区別される。 |
|ENQUEUE_NOCLOCK |0x08| ソースコードを見る限り、エンキューの動作中に、キューの時刻を更新しないことを示すフラグ。
|ENQUEUE_HEAD |0x10| RUNキューの先頭に配置する。指定されていなければ最後尾に配置する。
|ENQUEUE_REPLENISH|0x20| DLクラスのCBSで使われる。
|ENQUEUE_MIGRATED |0x40| （SMPのみ有効）タスクは移動させられた。
このコールバックのラッパー関数として、コア部に同名の [`enqueue_task`](https://elixir.bootlin.com/linux/v5.1.21/source/kernel/sched/core.c#L763) 関数が実装されている。この関数の呼び出し経路は以下のようになっていた。
```mermaid
flowchart LR
activate_task --> enqueue_task
move_queued_task --> enqueue_task
do_set_cpus_allowed --> enqueue_task
rt_mutex_setprio --> enqueue_task
set_user_nice--> enqueue_task
__sched_setscheduler --> enqueue_task
sched_setnuma --> enqueue_task
sched_move_task --> enqueue_task
```
この経路情報からも分かるが、enqueue_taskが呼び出されるケースとしては大まかに以下の2つが考えられる。
* タスクの状態がTASK_RUNNINGになったとき
* タスクの優先度やスケジューリングポリシーが変更されたときにキューの移動があれば呼び出される。
# dequeue_task
```c
void dequeue_task(struct rq *rq, struct task_struct *p, int flags);
```
enqueue_task と対で考えられるもの。
同様にフラグ用マクロが設定してある（[kernel/sched/sched.h:1629](https://elixir.bootlin.com/linux/v5.1.21/source/kernel/sched/sched.h#L1629)）。
|フラグ|値|意味|
|-|-|-|
|DEQUEUE_SLEEP |0x01| タスクが実行可能状態でなくなったことを示すフラグ。 |
|DEQUQUE_SAVE |0x02| ENQUEUE_RESTOREとペアで使用される。 |
|DEQUEUE_MOVE |0x04| ENQUEUE_MOVEとペアで使用される。キュー間を移動するときに指定される。 |
|DEQUEUE_NOCLOCK |0x08| ENQUEUE_NOCLOCKとペアで使用される。ソースコードを見る限り、エンキューの動作中に、キューの時刻を更新しないことを示すフラグ。
# yield_task
```c
static void yield_task(struct rq *rq)
```
rq上で実行中のタスクがCPU資源を他のプロセスに明け渡させるメンバ関数。
とはいっても、あくまでスケジューラのキューの内部状態を変更する（rq->curr をキューの最後尾に配置するなど）だけであり、実際にタスクを入れ替える処理は行わない。
使われ方としては、[`do_sched_yield`](https://elixir.bootlin.com/linux/v6.2.16/source/kernel/sched/core.c#L8424) 関数から呼び出される。この処理が行われた後に、`schedule() --[...]--> pick_next_task()` が呼び出されるので、そのときに適切なタスクを取得できるようにするだけである。
**sleepとは本質的にやっていることが違うので注意！！！**
:::danger
この処理が適切に使われる状況ってどんなものなのだろう、、。
これからバッチ処理があるから、他のタスクが待機中だったらいったんCPUを明け渡してあげよう、的な感じなのだろうか？
:::
# yield_to_task
このメンバは未実装でもいい（NULL）。
というか、CFSクラスしか実装していないみたい。
# check_preempt_curr
```c
static void
check_preempt_curr_rt(struct rq *rq, struct task_struct *p, int flags)
```
引数で指定されたタスクが current をプリエンプトすべきかどうかを検証するメンバ関数。
タスクが実行可能状態に遷移したときに呼び出される（他のケースはあるか？）。具体的には以下のようなケース。
* 負荷分散処理によってタスクがRUNキュー間を移動したとき
* TTWU（Try To Wake Up）処理で起こされたとき
* 新しくタスクを生成したとき
タスクをCPU間で移動する場合もあるので、`rq` は現在のCPUと異なるCPU上のRUNキューである可能性がある。`p` が `rq` に含まれているというのは条件として入っていても良さそう？？
このメンバ関数は、コア部の [check_preempt_curr](https://elixir.bootlin.com/linux/v6.2.16/source/kernel/sched/core.c#L2177) によってラッピングされている。`current` との比較を役割分担していて、++コア部の実装ではsched_class同士の優先度の比較、メンバ関数ではそのクラス内での優先度の比較をしている++。
コア部の [`wake_up_new_task`](https://elixir.bootlin.com/linux/v6.2.16/source/kernel/sched/core.c#L4772) の実装を見てみると、以下のようにタスクをRUNキューにプッシュした直後に [`check_preempt_curr`](https://elixir.bootlin.com/linux/v6.2.16/source/kernel/sched/core.c#L2177) が呼ばれていた。
クラス内部の実装については、RTクラスの実装を実際に見てみるとわかりやすいと思う。メンバ関数は [`check_preempt_curr_rt`](https://elixir.bootlin.com/linux/v6.2.16/source/kernel/sched/rt.c#L1718) という名前で定義されており、実装としては、p と current の優先度を比較しているだけである（UP環境を想定）。
```c
static void
check_preempt_curr_rt(struct rq *rq, struct task_struct *p, int flags)
{
if (p->prio < rq->curr->prio) { // pの優先度がcurrよりも高いなら
resched_curr(rq); // 再スケジューリング要求を出す
return;
}
}
```
# pick_next_task
```c
static struct task_struct *_pick_next_task_rt(struct rq *rq)
```
次にスケジュールするタスクを決定するメンバ関数。
スケジューラで最も重要な関数になる。
* rqは、このコードを実行しているCPUに紐付けられたRUNキューである（つまり、他のCPUのRUNキューが渡されることはない）。
* このメンバ関数が実行される直前に、put_prev_taskが呼び出される（キュー内の順番入れ替えをどっちのメンバでやればいいのだろうか？）。
* **次に実行状態に遷移させたいプロセスがなければNULLを返す**。NULLを返したら、自動で次に優先度の高い sched_class からタスクを取り出しに行くことになっている。
* 次のタスクが見つかれば、内部で set_next_task を呼び出すことになっている（これはRTクラスだけ？）？
コア部の `schedule()` の中から呼びだされる。
最新のバージョンには `CONFIG_SCHED_CORE` というオプションが追加されており、このオプションが有効かどうかで呼ばれ方は変わってくる。ただし、基本的には [`__pick_next_task`](https://elixir.bootlin.com/linux/v6.2.16/source/kernel/sched/core.c#L5908) 関数が呼ばれ、その内部でこのメンバ関数が呼ばれる、という流れになる。
呼ばれる部分を以下に示す。
```c
static inline struct task_struct *
__pick_next_task(struct rq *rq, struct task_struct *prev, struct rq_flags *rf)
{
[ ... ]
restart:
// ここでput_prev_taskメンバ関数が呼び出される。
put_prev_task_balance(rq, prev, rf);
for_each_class(class) { // 優先度の高いクラス順にpick_next_taskが呼び出される。
p = class->pick_next_task(rq);
if (p)
return p;
}
BUG(); /* The idle class should always have a runnable task. */
}
```
# put_prev_task
実行中のタスクがCPUを明け渡したときに呼ばれるメンバ関数。
このメンバの実装はスケジューラ特有になっており、これといった仕事は決められていない（特になければ空でいい？）。
使われ方は色々あるが、最もよく使われるのは、[`__pick_next_task`](https://elixir.bootlin.com/linux/v6.2.16/source/kernel/sched/core.c#L5908) の部分。ここで `sched_class->pick_next_task` と呼び出す前に、[`put_prev_task_balance`](https://elixir.bootlin.com/linux/v6.2.16/source/kernel/sched/core.c#L5882) で呼び出されている。
CPUを使用するタスクが入れ替わったときに後述する `set_next_task` とセットで呼び出される、と考えて良い。入れ替わりのときに、スケジューラの状態を更新するでもいいし、ログを取るでもいいし、整合性をチェックするでもいい？
参考程度に、CFSではこの関数内で `current` を赤黒木の中にプッシュするらしい。
vruntimeを更新する冗長なコードを防ぐための設計らしい。
# set_next_task
どうやら最近追加されたメンバ関数っぽい。
LKML：https://lore.kernel.org/all/20181026131743.21786-1-smuchun@gmail.com/T/#u
昔は set_curr_task や put_prev_task というメンバだった？
現在はこの名前で実装されていて、タスクが入れ替わったときに put_prev_task とセットで呼ばれることになっている。
内部実装では、RUNキューの統計情報を更新すること、
これら3つのメンバ関数の呼び出され方として最もよくあるものを以下に示す。
# task_tick
```c
static void
task_tick(struct rq *rq, struct task_struct *curr, int queued);
```
scheduler_tick() や hrtick() などから呼び出されるメンバ関数。
タイムスライスなどを管理するスケジューラの場合は、ここでタイムスライスの更新を行ったりして、再スケジューリング要求を出したりする（NEED_RESCHED_FLAG）。
毎度タイマー割り込み時に呼び出される、というのではなく、currentが属しているsched_classのメンバ関数しか呼び出されないので注意！
引数は、以下のような意味を持つ。
* `rq`： タイマー割り込みが入ったCPUに対応するRUNキューへのポインタ。
* `curr`： rq上で現在実行状態のタスク。呼び出し側は `rq->curr` をセットしたりする。
* `queued`： よく分かっていない。RTクラスでは使われていなかった。
呼び出し時の処理を見る限りだと、++このコードを実行しているCPUとrqが属するCPUが同じであることを確認してから呼び出している++感じがする。ただし、[ここ](https://elixir.bootlin.com/linux/v6.2.16/source/kernel/sched/core.c#L770)では警告を発しているだけで、そのような可能性を排除しているわけではない。
```c
[ ... ]
WARN_ON_ONCE(cpu_of(rq) != smp_processor_id());
[ ... ]
rq->curr->sched_class->task_tick(rq, rq->curr, 1);
[ ... ]
```
# task_fork
```c
static void task_fork(struct task_struct *p);
```
sched_fork() から呼ばれるメンバ関数。実際の呼び出され方としては、
```
fork
--[call]--> ...
--[call]--> copy_process
--[call]--> sched_cgroup_fork
--[call]--> sched_class->task_fork
```
のように呼び出される。
ここは未実装でも良さそう。RTクラスなんかも未実装となっている。
# task_dead
未実装で良さそう。
タスクが終了したときに呼び出される？
# switched_from & switched_to
sched_setscheduler システムコールなどによって、タスクが属する sched_class が変更されたときに呼び出されるメンバ関数。変更前に属していたクラスの switched_from と変更後に属する switched_to が呼ばれる。
例えば、fairクラスに属しているタスクがrtクラスに移動した場合は、以下のように fair_sched_class->switched_from と rt_sched_class->switched_to が呼ばれる。
コア部の [`check_class_changed`](https://elixir.bootlin.com/linux/v6.2.16/source/kernel/sched/core.c#L2164) から呼び出されている。呼び出しを見ると分かると思うが、++`switched_from` は未実装でもいいのに対し、`switched_to` は実装が必須になっている++（さもないとセグフォする）。
```c
static inline void
check_class_changed(struct rq *rq, struct task_struct *p,
const struct sched_class *prev_class,
int oldprio)
{
if (prev_class != p->sched_class) {
if (prev_class->switched_from)
prev_class->switched_from(rq, p);
p->sched_class->switched_to(rq, p);
} else if (oldprio != p->prio || dl_task(p))
p->sched_class->prio_changed(rq, p, oldprio);
}
```
:::danger
タスクが実行途中で別のクラスに移動しない限りは、中身は未実装でも良い。
RTクラスなどを見ていると、MIGRATIONと密接な関係がありそう。
特に、task_struct->on_rq メンバについては詳しく調べたい。
:::
check_class_changed 関数が呼び出されるコールパスを見てみる。
```mermaid
flowchart TB
A["sched_setscheduler（システムコール）"] -->
do_sched_setscheduler -->
C["sched_setscheduler（カーネル内部の関数）"] -->
_sched_setscheduler -->
__sched_setscheduler -->
check_class_changed
```
# prio_changed
タスクの優先度が変わったときに呼ばれる関数。
このメンバ関数が呼び出される場所としては、以下が考えられる。
* `sched_setscheduler` システムコールなどによって、ポリシーに変項はないが、優先度に変項があったとき。この場合は `switched_{from, to}` と同様に [`check_class_changed`](https://elixir.bootlin.com/linux/v6.2.16/source/kernel/sched/core.c#L2164) から呼び出される。
* [`set_user_nice`](https://elixir.bootlin.com/linux/v6.2/source/kernel/sched/core.c#L7101) によってタスクのnice値に変更があり、その結果優先度に変化が合ったとき。
このメンバ関数の実装としてRTクラスを参考にしてみる。簡単にするために、UPシステムを考える。実装は [`prio_changed_rt`](https://elixir.bootlin.com/linux/v6.2/source/kernel/sched/rt.c#L2560) という名前で定義されている。
```c
static void
prio_changed_rt(struct rq *rq, struct task_struct *p, int oldprio)
{
if (!task_on_rq_queued(p))
// ① pが実行可能状態でない場合は特に何もしない
return;
if (task_current(rq, p)) {
// ② pが現在実行状態で、
if (oldprio < p->prio)
// 優先度が下がった場合は、再スケジューリング要求を出す
resched_curr(rq);
} else {
// ③ pは現在実行状態ではないが、
if (p->prio < rq->curr->prio)
// 優先度が上がった場合は、再スケジューリング要求を出す
resched_curr(rq);
}
}
```
この実装を見ると、**優先度の変更の末、実行状態でないタスクが最高優先度となってしまう可能性がある場合は、再スケジューリング要求を出す**、といった処理をやっていると理解することができる。この実装は無駄な処理を減らすためにこうなっているが、愚直に実装する場合は以下のようにしても動くには動くはず。
```c
static void
prio_changed_rt(struct rq *rq, struct task_struct *p, int oldprio)
{
resched_curr(rq);
}
```
# get_rr_interval
スケジューリングポリシーがRRのときのみ、そのタイムスライス値を返す関数。
このメンバ関数は未実装でも良い。このメンバ関数を呼び出すときにはNULLチェックが挟まるので、セグフォになることはない。
:::warning
:information_source: fairクラスにも実装されていた。CFSにもラウンドロビン的な考え方を適用させることができる、ということなのだろうか？
:::
# update_curr
currentプロセスの統計情報の更新などを実装する。
このメンバ関数は [`task_sched_runtime`](https://elixir.bootlin.com/linux/v6.2/source/kernel/sched/core.c#L5458) から呼び出される。
おそらく実装は必須で、task_struct内のseメンバの時刻を更新したりする必要がありそう。
# === SMP部分 ===
# balance
```c
int balance(struct rq *rq, struct task_struct *prev, struct rq_flags *rf);
```
このメンバ関数は、[`put_prev_task_balance`](https://elixir.bootlin.com/linux/v6.2.16/source/kernel/sched/core.c#L5896) から呼ばれる。イメージとしては、タスク `prev` がCPUを明け渡すときに、`put_prev_task` メンバ関数の前に呼び出されるメンバ関数、である。
処理を見てみると、優先度がprevが所属しているクラス以下のクラスそれぞれについて、balanceを実行している。
```c
static void put_prev_task_balance(struct rq *rq, struct task_struct *prev,
struct rq_flags *rf)
{
#ifdef CONFIG_SMP
const struct sched_class *class;
/*
* We must do the balancing pass before put_prev_task(), such
* that when we release the rq->lock the task is in the same
* state as before we took rq->lock.
*
* We can terminate the balance pass as soon as we know there is
* a runnable task of @class priority or higher.
*/
for_class_range(class, prev->sched_class, &idle_sched_class) {
if (class->balance(rq, prev, rf))
break;
}
#endif
put_prev_task(rq, prev);
}
```
# task_woken
タスクをWAKEUPするときに呼ばれるコールバック。
UPでも必要な機能に感じるが、なぜかSMP専用になっている。
その理由を理解するのが一番の目標。
このコールバックの呼び出し経路には以下の2つがある。
```mermaid
flowchart BT
A["wake_up_new_task"] -->
sched_class.task_woken
B["ttwu_do_wakeup"] -->
sched_class.task_woken
click A "https://elixir.bootlin.com/linux/v5.1.21/source/kernel/sched/core.c#L2446" "This is a link"
click B "https://elixir.bootlin.com/linux/v5.1.21/source/kernel/sched/core.c#L1697" "This is a link"
```
[`ttwu_do_wakeup`](https://elixir.bootlin.com/linux/v5.1.21/source/kernel/sched/core.c#L1697) の方はの
RTクラスの実装を参考にしてみる。
```c
/*
* If we are not running and we are not going to reschedule soon, we should
* try to push tasks away now
*/
static void task_woken_rt(struct rq *rq, struct task_struct *p)
{
if (!task_running(rq, p) &&
!test_tsk_need_resched(rq->curr) &&
p->nr_cpus_allowed > 1 &&
(dl_task(rq->curr) || rt_task(rq->curr)) &&
(rq->curr->nr_cpus_allowed < 2 ||
rq->curr->prio <= p->prio))
push_rt_tasks(rq);
}
```
if文の条件が読みづらいが、つまりは以下の条件を全て満たすとき、rqのRTタスクを他のRUNキューにマイグレートしようと試みる。
* **pが実行可能状態ではない**、かつ
* 実行状態で呼ばれた場合はキャッシュにデータが残っている可能性があるので、マイグレートのタイミングとしては適切でない？
* **pがすぐに再スケジューリングされようとしていない**、かつ
* CPUがすぐに空きそうなら、マイグレートする必要はない？
* **pと親和しているCPUが2つ以上ある**、かつ
* そもそも単一CPUとしか親和していなかったらマイグレートする意味ない。
* **rq上で現在実行中のタスクがDLクラスかRTクラスのものである**、かつ
* **rq->currと親和しているCPUが1つのみ**、または、**rq->currの優先度 >= pの優先度**
# select_task_rq
```c
int select_task_rq(struct task_struct *p, int cpu, int sd_flags, int wake_flags)
```
起床したタスクpが次に管理されるRUNキューを選ぶ関数。
ロードバランスの1つの機能として考えて良さそう。ただし、呼び出し経路が以下のようになっていて、**タスクが新しくプログラムを実行したときやスリープから復帰したとき**に行われる負荷分散処理の中で呼ばれるコールバックである。
呼び出し経路は以下のとおりである。
```mermaid
flowchart BT
wake_up_new_task --> select_task_rq
try_to_wake_up --> select_task_rq
select_task_rq --> sched_class::select_task_rq
sched_exec --> sched_class::select_task_rq
```
コア部の select_task_rq があるが、この処理はタスクが属すスケジューラクラスの select_task_rq に丸投げしている。
CFSクラスの実装を見てみる。
CFSクラスの実装では、ドメインの中から最も負荷の小さいCPUを見つけ出して、そのCPU番号を返している。
TODO:
Sign in with Wallet
Connect another wallet