「Linuxカーネル2.6解読室」（以降、旧版）出版後、Linuxには多くの機能が追加され、エンタープライズ領域をはじめとする様々な場所で使われるようになりました。
それに伴いコードが肥大かつ複雑化し、多くのエンジニアにとって解読不能なブラックボックスとなっています。
世界中のトップエンジニア達の傑作であるLinuxカーネルにメスを入れ、ブラックボックスをこじ開けて、時に好奇心の赴くままにカーネルの世界を解読する「新Linuxカーネル解読室」プロジェクト。
本稿では、(その1)、(その2)、(その3)に引き続き、カーネルv6.8におけるタスクスケジューラの仕組みや実装について解説したいと思います。
執筆者 : 西村 大助
※ 「新Linuxカーネル解読室」連載記事一覧はこちら
はじめに
本稿では、「タスクスケジューラ編」の締めくくりとして、「どのCPUでタスクを実行するか」の選択ロジックについて説明したいと思います。
引き続き、章節番号は(その1)、(その2)、(その3)からの連番となっています。
4. どのCPUでタスクを実行するか
4.1 分類
sched_setaffinity(2)やCPUSET等により明示的にCPUのaffinityを変更する場合(その変更により別CPUに移動しなければならなくなる場合)を除けば*1、タスクの動作CPUを選択・変更するタイミングやそのロジックにはいくつかパターンがあります。
本節ではまずそれを分類・整理しますが、広い意味で負荷分散(ロードバランス)を目的としている、という意味ではどれも同じです。
具体的なロジックについては、以降の節でこれらのそれぞれのパターン・スケジューリングクラス毎に簡単に説明したいと思いますが、記事の長さの都合上、SCHED_FAIRとSCHED_RTに絞って解説します*2。
4.1.1 select_task_rq()
1つ目は、タスクの起床といったタスクの状態遷移に伴い、そのタスク自身の動作CPU*3をselect_task_rq()で選択するパターンです。状態遷移の具体的なタイミングとしては、
- fork(2)直後の子プロセスの起床(
wake_up_new_task()) - 一般的なタスクの起床(
try_to_wake_up()) - exec(2)実行時(
sched_exec())
の3つがありますが、どのタイミングでの呼び出しかは引数(@wake_flags)で判断できます。具体的には、それぞれWF_FORK/WF_TTWU/WF_EXECが@wake_flagsで渡されます。また、select_task_rq()の実装を見ればわかる通り、その実体は対象となるタスクのスケジューリングクラスのselect_task_rq()ハンドラです。
4.1.2 balance()ハンドラ
2つめは、次に実行するタスクの選択時に(__schedule()->pick_next_task()の延長で)実行される、balance()ハンドラによりタスクを移動するパターンです。
5981 static void put_prev_task_balance(struct rq *rq, struct task_struct *prev, 5982 struct rq_flags *rf) 5983 { 5984 #ifdef CONFIG_SMP 5985 const struct sched_class *class; 5986 /* 5987 * We must do the balancing pass before put_prev_task(), such 5988 * that when we release the rq->lock the task is in the same 5989 * state as before we took rq->lock. 5990 * 5991 * We can terminate the balance pass as soon as we know there is 5992 * a runnable task of @class priority or higher. 5993 */ 5994 for_class_range(class, prev->sched_class, &idle_sched_class) { 5995 if (class->balance(rq, prev, rf)) 5996 break; 5997 } ...
上記の通り、balance()ハンドラは、実行中(切り替え前)タスクのスケジューリングクラスから始まり、より優先度の低いクラスにかけて、当該ハンドラがtrueを返すまで実行されますが、当該ハンドラは「そのスケジューリングクラス(もしくはより優先度の高いスケジューリングクラス)で、このCPUで実行すべきタスクがある、もしくは、他CPUからタスクを移動することができればtrueを返す」という動作をします。そうすることで、この処理の後に実行されるpick_next_task()ハンドラで次に実行すべきタスクが見つかるようにしているわけです。また、その実行タイミングから、あるCPUがidleになろうとしている時にone-shotで行われるロードバランスと考えることもできます。
ちなみに、balance()ハンドラのように「自CPUに他CPUからタスクを移動する」タイプのロードバランスをpull型と呼ぶことがあります。
4.1.3 SCHED_SOFTIRQ
3つ目は、SCHED_FAIR限定ではあるのですが、(前述のbalance()ハンドラがone-shotであるのに対し)tickを契機として定期的に発生するSCHED_SOFTIRQから行われるロードバランス処理です。
詳細は後述しますが、これもpull型に該当します。
4.1.4 balance_callback
最後に4つ目は、balance_callbackと呼ばれる枠組み*4を使ったロードバランス処理で、タスクを移動するためのcallback関数*5を介してロードバランスを行います。
3つ目とは逆にRT系クラス(SCHED_DEADLINE, SCHED_RT)でのみ使われていて、callback関数にはpull型だけでなく、それとは逆の「自CPUから他のCPUにタスクを移動する」タイプ(push型)も存在します。
ちなみに、balance_callbackで登録された各callbackは、以下のシーケンスにより__schedule()の最後に実行されますが、
__schedule()
(prev != next: context switch が発生する場合)
└ context_switch(rq, prev, ...)
└ finish_task_switch(prev)
└ finish_lock_switch(rq)
└ __balance_callbacks(rq)
└ do_balance_callbacks(rq, __splice_balance_callbacks(rq, false))
(prev == next: context switch が発生しない場合)
└ __balance_callbacks(rq)
└ do_balance_callbacks(rq, __splice_balance_callbacks(rq, false))
いずれの場合も、__splice_balance_callbacks()によりcallbackの登録が解除されるので、登録したcallbackが実行されるのは1度きりです(必要に応じて、都度、登録の必要があります)。
4.2 SCHED_FAIR
4.2.1 スケジューリングドメイン
具体的な動作CPU選択(≒ロードバランス)処理のロジックについて解説する前に、本節ではSCHED_FAIRロードバランス処理において*6鍵となるデータ構造である、スケジューリングドメイン(sched_domain構造体とsched_group構造体を中心としたデータ構造)について解説します*7。
スケジューリングドメインは結構複雑な構造をしているのですが、その核をなすsched_domainとsched_groupについて、いくつか重要な点を挙げておきます。
- sched_domainは階層構造を持ち、その階層構造はCPU毎に存在する。
- 階層構造にはSMT, MC, PKG, NUMA,... 等があり、何を共有しているかで階層が分かれている(例:SMT層の場合は物理コアを共有している)。
- sched_domainは対応するCPUの一覧(spanと呼ばれるビットマップ)を持っていて、spanは上層に行くほど範囲が広くなり、最上層のsched_domainのspanはシステム全体のCPUと一致する。
- sched_domainはそれに対応したsched_groupを持つ(sd->groups)。
- sched_groupもsched_domain同様にspanを持っていて、sched_groupのspanは1つ下層のsched_domainのspanと一致する(最下層のsched_groupのspanは対応するCPUと一致する)。
- sched_groupのspanに含まれるCPU間でsched_groupは共有される。
- 同じspanを持つsched_domainに対応するsched_group同士がリンクリストで繋がっている。
- ロードバランス処理の考え方
- sched_group単位で「負荷」が管理され、 同一層の(リンクリストに繋がっている)sched_group間でロードバランスを行う(ロードバランスは階層毎に行われる)。
- sched_domainにはフラグ(
SD_*)や各種パラメータがあり、その階層でロードバランスを行うべきかどうかの判断に使われる(基本的な方針としては、上層に行くほどロードバランスが発生しづらくなっている)。
文字だけでこの構造をイメージするのは難しいので、例として2core/4threadのCPUが2つあるシステム(0と1、2と3、…がSMTのペア(同一物理コア)で、0-3、4-7が同一物理CPUとします)のsched_domainとsched_group、およびそれぞれのspanの関係を図示してみました。
具体的に何層のスケジューリングドメインが構成されるかは、ハードウェアの構成や設定(マルチCPUやNUMA構成等)によって変わります。スケジューリングドメインの作成は、起動時にbuild_sched_domains()を中心とした一連の処理で行われますが、やや本筋からずれてしまうため本稿では触れません。
ただ、実際にどのようなスケジューリングドメインが構成されているかは、カーネルパラメータでsched_verboseを指定すれば起動時のログで確認できます。
以下のログは、Intel Xeon Gold 6208U(16C/32T)/Ubuntu 24.04.4 LTS(6.8.0-101-generic)で確認した際のスケジューリングドメインです。
- HT-onの場合
[ 0.279500] CPU0 attaching sched-domain(s):
[ 0.279502] domain-0: span=0,16 level=SMT
[ 0.279505] groups: 0:{ span=0 }, 16:{ span=16 }
[ 0.279510] domain-1: span=0-31 level=MC
[ 0.279512] groups: 0:{ span=0,16 cap=2048 }, 1:{ span=1,17 cap=2048 }, 2:{ span=2,18 cap=2048 }, 3:{ span=3,19 cap=2048 }, 4:{ span=4,20 cap=2048 }, 5:{ span=5,21 cap=2048 }, 6:{ span=6,22 cap=2048 }, 7:{ span=7,23 cap=2048 }, 8:{ span=8,24 cap=2048 }, 9:{ span=9,25 cap=2048 }, 10:{ span=10,26 cap=2048 }, 11:{ span=11,27 cap=2048 }, 12:{ span=12,28 cap=2048 }, 13:{ span=13,29 cap=2048 }, 14:{ span=14,30 cap=2048 }, 15:{ span=15,31 cap=2048 }
[ 0.279547] CPU1 attaching sched-domain(s):
[ 0.279548] domain-0: span=1,17 level=SMT
[ 0.279549] groups: 1:{ span=1 }, 17:{ span=17 }
[ 0.279553] domain-1: span=0-31 level=MC
[ 0.279555] groups: 1:{ span=1,17 cap=2048 }, 2:{ span=2,18 cap=2048 }, 3:{ span=3,19 cap=2048 }, 4:{ span=4,20 cap=2048 }, 5:{ span=5,21 cap=2048 }, 6:{ span=6,22 cap=2048 }, 7:{ span=7,23 cap=2048 }, 8:{ span=8,24 cap=2048 }, 9:{ span=9,25 cap=2048 }, 10:{ span=10,26 cap=2048 }, 11:{ span=11,27 cap=2048 }, 12:{ span=12,28 cap=2048 }, 13:{ span=13,29 cap=2048 }, 14:{ span=14,30 cap=2048 }, 15:{ span=15,31 cap=2048 }, 0:{ span=0,16 cap=2048 }
...
[ 0.280125] CPU16 attaching sched-domain(s):
[ 0.280126] domain-0: span=0,16 level=SMT
[ 0.280127] groups: 16:{ span=16 }, 0:{ span=0 }
[ 0.280131] domain-1: span=0-31 level=MC
[ 0.280132] groups: 0:{ span=0,16 cap=2048 }, 1:{ span=1,17 cap=2048 }, 2:{ span=2,18 cap=2048 }, 3:{ span=3,19 cap=2048 }, 4:{ span=4,20 cap=2048 }, 5:{ span=5,21 cap=2048 }, 6:{ span=6,22 cap=2048 }, 7:{ span=7,23 cap=2048 }, 8:{ span=8,24 cap=2048 }, 9:{ span=9,25 cap=2048 }, 10:{ span=10,26 cap=2048 }, 11:{ span=11,27 cap=2048 }, 12:{ span=12,28 cap=2048 }, 13:{ span=13,29 cap=2048 }, 14:{ span=14,30 cap=2048 }, 15:{ span=15,31 cap=2048 }
[ 0.280164] CPU17 attaching sched-domain(s):
[ 0.280164] domain-0: span=1,17 level=SMT
[ 0.280166] groups: 17:{ span=17 }, 1:{ span=1 }
[ 0.280169] domain-1: span=0-31 level=MC
[ 0.280171] groups: 1:{ span=1,17 cap=2048 }, 2:{ span=2,18 cap=2048 }, 3:{ span=3,19 cap=2048 }, 4:{ span=4,20 cap=2048 }, 5:{ span=5,21 cap=2048 }, 6:{ span=6,22 cap=2048 }, 7:{ span=7,23 cap=2048 }, 8:{ span=8,24 cap=2048 }, 9:{ span=9,25 cap=2048 }, 10:{ span=10,26 cap=2048 }, 11:{ span=11,27 cap=2048 }, 12:{ span=12,28 cap=2048 }, 13:{ span=13,29 cap=2048 }, 14:{ span=14,30 cap=2048 }, 15:{ span=15,31 cap=2048 }, 0:{ span=0,16 cap=2048 }
最下層にSMTレベルのsched_domain(spanはSMTのペア)が作成され、SMTペアそれぞれの論理コアがそのsched_domainを持ち、sched_groupとしてはspanが自CPUに対応するsched_groupのリストを形成しています。また、次の層としてMCレベルのsched_domain(spanは全CPU)が作成され、sched_groupとしてはspanが1階層下のsched_domainのspan、すなわちSMTのペアとなっているsched_groupのリストを形成しています。
つまり、SMTペア間のロードバランスと物理コア間のロードバランスの2段階のロードバランスが行われることを意味しています。
- HT-offの場合
[ 0.267968] CPU0 attaching sched-domain(s):
[ 0.267969] domain-0: span=0-15 level=MC
[ 0.267972] groups: 0:{ span=0 }, 1:{ span=1 }, 2:{ span=2 }, 3:{ span=3 }, 4:{ span=4 }, 5:{ span=5 }, 6:{ span=6 }, 7:{ span=7 }, 8:{ span=8 }, 9:{ span=9 }, 10:{ span=10 }, 11:{ span=11 }, 12:{ span=12 }, 13:{ span=13 }, 14:{ span=14 }, 15:{ span=15 }
[ 0.267998] CPU1 attaching sched-domain(s):
[ 0.267999] domain-0: span=0-15 level=MC
[ 0.268001] groups: 1:{ span=1 }, 2:{ span=2 }, 3:{ span=3 }, 4:{ span=4 }, 5:{ span=5 }, 6:{ span=6 }, 7:{ span=7 }, 8:{ span=8 }, 9:{ span=9 }, 10:{ span=10 }, 11:{ span=11 }, 12:{ span=12 }, 13:{ span=13 }, 14:{ span=14 }, 15:{ span=15 }, 0:{ span=0 }
...
この場合はもっとシンプルで、最下層にMCレベルのsched_domain(spanは全CPU)が作成され、sched_groupとしてはspanが自CPUに対応するsched_groupのリストが形成されるだけなので、物理コア間のロードバランスのみが行われることを意味しています。
4.2.2 select_task_rq_fair()
SCHED_FAIRのselect_task_rq()ハンドラはselect_task_rq_fair()です。
この関数はWF_TTWUの場合は少し違った動きをする*8ので、ここではWF_FORKorWF_EXECの場合の動きについてのみ解説します。WF_FORK/WF_EXECの場合に限定したselect_task_rq_fair()を疑似的に書くと以下のようになります。
static int select_task_rq_fair(struct task_struct *p, int prev_cpu, int wake_flags) { int sync = (wake_flags & WF_SYNC) && !(current->flags & PF_EXITING); struct sched_domain *tmp, *sd = NULL; int cpu = smp_processor_id(); int new_cpu = prev_cpu; /* SD_flags and WF_flags share the first nibble */ int sd_flag = wake_flags & 0xF; for_each_domain(cpu, tmp) { ┐ if (tmp->flags & sd_flag) │ sd = tmp; │ ① else │ break; │ } ┘ new_cpu = find_idlest_cpu(sd, p, cpu, prev_cpu, sd_flag); ② return new_cpu; }
このコードの中身を追いかける前に、引数の@wake_flags(WF_EXEC/WF_FORK/WF_TTWU)とsched_domainのフラグ(SD_BALANCE_EXEC/SD_BALANCE_FORK/SD_BALANCE_WAKE)の関係について説明します。sched_domainのフラグはその定義方法がやや特殊*9なため詳細には触れませんが、以下に示すように一致しないとエラーとなることからも解る通り、これらのWF_*とSD_BALANCE_*は一致するように定義されています。
/* Wake flags. The first three directly map to some SD flag value */ #define WF_EXEC 0x02 /* Wakeup after exec; maps to SD_BALANCE_EXEC */ #define WF_FORK 0x04 /* Wakeup after fork; maps to SD_BALANCE_FORK */ #define WF_TTWU 0x08 /* Wakeup; maps to SD_BALANCE_WAKE */ static_assert(WF_EXEC == SD_BALANCE_EXEC); static_assert(WF_FORK == SD_BALANCE_FORK); static_assert(WF_TTWU == SD_BALANCE_WAKE);
この事を踏まえた上で前述の疑似コードを見てみると、前半のループ①は、引数の@wake_flagsに対応するフラグが立っている最上位のsched_domainを求めるための物であるとわかります。
そしてその最上位のsched_domainをfind_idlest_cpu()への引数として渡すことでタスクの動作CPUを決定します。詳細については触れませんが、この関数はその名前が示す通り、引数のsched_domain配下の最もidleなCPUを見つけるための物なので、SD_BALANCE_EXECなりSD_BALANCE_FORKが立っているsched_domainの範囲で最もidleなCPUでタスクを動作させることになるわけです。
4.2.3 balance_fair()
SCHED_FAIRのbalance()ハンドラはbalance_fair()です。
static int balance_fair(struct rq *rq, struct task_struct *prev, struct rq_flags *rf) { if (rq->nr_running) ① return 1; return newidle_balance(rq, rf) != 0; ② }
既にこのCPUで実行可能なタスクがあるのであれば、特にすることはありません(①)。
そうでない場合、newidle_balance()(後述します)で他のビジーなCPUから、実行可能なタスクをこのCPUに移動しますが、newidle_balance()は、このCPUで実行可能なタスクがある状態にできれば0以外を返すので、balance_fair()はtrue(1)を(そうでない場合はfalse(0)を)返すことになります。
newidle_balance()の鍵となるのは以下のループ部分です(わかりやすくするため、意図的にロードバランスコストに関する処理を省略しています)。
for_each_domain(this_cpu, sd) { ① int continue_balancing = 1; update_next_balance(sd, &next_balance); if (sd->flags & SD_BALANCE_NEWIDLE) { pulled_task = load_balance(this_cpu, this_rq, ┐ sd, CPU_NEWLY_IDLE, │ ② &continue_balancing); ┘ } /* * Stop searching for tasks to pull if there are * now runnable tasks on this rq. */ if (pulled_task || this_rq->nr_running > 0 || ┐ this_rq->ttwu_pending) │ ③ break; ┘ }
②で呼ばれるload_balance()という関数*10は、引数のsched_domainの範囲で最もbusyなCPUから自CPU(@this_cpu)へタスクを移動を試みる関数で、その結果、自CPUで実行可能なタスクが出てくればループを終了します(③)。また、for_each_domain(this_cpu, sd)を使って、自CPUのスケジューリングドメインの最下層のsched_domainから徐々に遡っていくので(①)、下層の処理でタスクを移動できなければ、より上層(つまり、広い範囲のCPU)でタスクが移動できないかを確認していくことになります。
この流れについて、load_balance()のロジックも交え、もう少し掘り下げてみましょう。
まず、load_balance()ですが、基本的には、
find_busiest_group()で引数のsched_domainに対応するsched_groupリストから最もbusyなsched_groupを探す。- そのsched_group内で最もbusyなCPU(run queue)を
find_busiest_queue()で探す。 - そのCPUからタスクを
detach_tasks()でdequeueする。 - dequeueできたタスクを
attach_tasks()で自CPUにenqueueする。
という流れになっていて*11、自CPUに移動できたタスクの数を返します。
ここで、4core/8threadのCPU(0と1、2と3、…がSMTのペア)で、CPU:0とCPU:1の負荷状態が高く(CPU:0の方がより高い)、他CPU負荷が低めという状態という状況で、CPU:2においてnewidle_balance()が実行された場合を考えます。
①のループにより、まずはSMT層でload_balance()が実行されますが(a)、sg:2*12、sg:3共に負荷が低い(ロードバランスが必要な程の負荷ではない)ためfind_busiest_group()がNULLを返し(b)、処理を終了します。
次に、①のループで1つ層を登って、MC層でload_balance()が実行されますが(c)、今度はfind_busiest_group()がsg:0-1を返し(d)、更に、find_busiest_queue()によりCPU:0(sg:0-1のspan内で最もbusyなCPU)が返され(e)、CPU:0からCPU:2にタスクの移動が発生し、ロードバランスが行われます。
4.2.4 SCHED_SOFTIRQ
4.1.3で「tickを契機として定期的に発生するSCHED_SOFTIRQから行われるロードバランス処理」と説明しましたが、具体的には、tick毎の処理であるscheduler_tick()の最後に呼ばれるtrigger_load_balance()を発端として処理が行われます。
/* * Trigger the SCHED_SOFTIRQ if it is time to do periodic load balancing. */ void trigger_load_balance(struct rq *rq) { /* * Don't need to rebalance while attached to NULL domain or * runqueue CPU is not active */ if (unlikely(on_null_domain(rq) || !cpu_active(cpu_of(rq)))) return; if (time_after_eq(jiffies, rq->next_balance)) raise_softirq(SCHED_SOFTIRQ); ① nohz_balancer_kick(rq); ② }
この関数からは、定期的に直接SCHED_SOFTIRQが発行される他(①)、nohz_balancer_kick()から、他のidleなCPUに対してIPIを飛ばしてSCHED_SOFTIRQを発行させるパスもあります(②)。後者のパスが必要になる理由は、CPUがidleになってtickそのものが止まっているケース(NOHZ)もあるためです。
いずれにしても、SCHED_SOFTIRQのハンドラであるrun_rebalance_domains()が実行されますが、
run_rebalance_domains()
└─ rebalance_domains()
└─ load_balance()
という流れで、最終的には前項でも触れたload_balance()が呼ばれ、当該処理を実行中のCPUに他のCPUからタスクを移動しようとすることになります。
4.3 SCHED_RT
4.3.1 概要
SCHED_RTではその名の通りリアルタイム性を重視するため、実行可能状態なタスクは可能な限り実行できるよう、できるだけ同じCPUにRTタスクが重ならないような工夫がなされています。以降の項で具体的にどのような方法がとられているかを見ていきますが、RTタスクの配置は常に最適な状態に保たれているという前提のもと、RTタスクの起床やスリープ等のイベントが発生した際に、より最適な配置に移行できないかを試みるというのが基本的な考え方です。
次にこれを実現するために使われるいくつか重要な管理データについて説明しておきます。
pushable_tasks(rq->rt.pushable_tasks)- そのCPUで実行可能状態にあるRTタスク(実行状態にあるRTタスクは含まれない)を、優先度(p->
prio)順にリスト化した物で、他のより優先度の高いタスクのため、実行できないでいるタスクの一覧と見なすことができる。 - 厳密には、リスト化されたRTタスクは他のCPUでも動作可能である必要がある(p->
nr_cpus_allowed> 1かどうかで確認)。
- そのCPUで実行可能状態にあるRTタスク(実行状態にあるRTタスクは含まれない)を、優先度(p->
highest_prio(rq->rt.highest_prio)curr- そのCPUの「最高優先度」。具体的には、そのCPUで実行(可能)状態にあるRTタスクの内、最も優先度の高いタスクの
prio(p->prio)*13。 - 実行可能なRTタスクが無いCPUについては、
MAX_RT_PRIO-1(99)が設定される。
- そのCPUの「最高優先度」。具体的には、そのCPUで実行(可能)状態にあるRTタスクの内、最も優先度の高いタスクの
next- 上記
pushable_tasksの中で最も優先度の高いタスクのprio(p->prio)。 - こちらもリストが空の場合は
MAX_RT_PRIO-1が設定される。
- 上記
rto_mask(rq->rd.rto_mask)*14*15- 上記
pushable_tasksが空ではないCPUの一覧を保持しているビットマスク
- 上記
詳細は触れませんが、これらのデータは、RTタスクのenqueue/dequeueやset_next_task/put_prev_taskといったスケジューリングイベントで更新されます。
また、select_task_rq()ハンドラによる物を除けば、SCHED_RTでのロードバランスはpushable_tasksを中心とした処理になっています。
具体的には、他CPUのpushable_tasksから自CPUにRTタスクを移動するpull型と、自CPUのpushable_tasksのRTタスクを他CPUに移動するpush型のロードバランスがあり、それぞれ、pull_rt_task()/push_rt_tasks()という関数で移動処理を行います。これらの関数は直接呼び出される場合と、本稿冒頭で説明したbalance_callbackという枠組みのcallback関数として呼び出される場合があり、以降の項で具体的な例を用いて解説しますが、
- CPUの「最高優先度」が下がることにより、他CPUのRTタスクを自CPUに移動できる可能性がでてきたら、他のCPUの
pushable_tasksからタスクを自CPUに移動しようとする。 - 自CPUの
pushable_tasksが空でなくなったら(実行可能だがキューの中で待たされているRTタスクがでてきたら)、pushable_tasksのタスクを他CPUに移動しようとする。
というのが基本的な考え方で、これらを組み合わせることで最適なRTタスクの再配置を行っています。
4.3.2 select_task_rq_rt()
SCHED_RTのselect_task_rq()ハンドラはselect_task_rq_rt()です。
heterogeneousな環境でないとすれば、rt_task_fits_capacity()は常にtrueを返すため、select_task_rq_rt()を簡単に書くと以下のようになります。
static int select_task_rq_rt(struct task_struct *p, int cpu, int flags) { struct task_struct *curr; struct rq *rq; bool test; /* For anything but wake ups, just return the task_cpu */ if (!(flags & (WF_TTWU | WF_FORK))) ┐ ① goto out; ┘ rq = cpu_rq(cpu); rcu_read_lock(); curr = READ_ONCE(rq->curr); /* unlocked access */ test = curr && ┐ unlikely(rt_task(curr)) && │ ② (curr->nr_cpus_allowed < 2 || curr->prio <= p->prio); ┘ if (test) { int target = find_lowest_rq(p); ③ /* * Don't bother moving it if the destination CPU is * not running a lower priority task. */ if (target != -1 && ┐ p->prio < cpu_rq(target)->rt.highest_prio.curr) │ ④ cpu = target; ┘ } out_unlock: rcu_read_unlock(); out: return cpu; }
まず、①の通りWF_EXECの場合は特に何もしません(現在動作中のCPU(@cpu)で動作し続けます)。
@cpu(WF_FORKの場合は親プロセスの動作CPU、WF_TTWUの場合は起床対象タスクが以前動作していたCPU)のcurrent taskが、RTタスクで且つ他CPUに移動する事ができないか生成/起床しようとしているタスクより優先度が高ければ(②)、生成/起床しようとするタスクを別のCPUで動作させるべく適切なCPUを探します(後述)が、そうでない場合は、@cpuでタスクを生成/起床します(その場合、仮にcurrent taskが優先度の低いRTタスクだった場合、後述するpush型ロードバランスによりcurrent taskが別のCPUへ移されます)。
生成/起床しようとするタスクを別のCPUで動作させる場合は、当該タスクを実行できるCPUの中で「最高優先度」が最も低いCPUを探してきて(③)、その「最高優先度」が生成/起床しようとするタスクの優先度より低い場合は、そのCPUでタスクを生成/起床します(④)。
4.3.3 pull型ロードバランス(pull_rt_task())
pull型ロードバランスについては、SCHED_RTのbalance()ハンドラであるbalance_rt()を使って説明します。
static int balance_rt(struct rq *rq, struct task_struct *p, struct rq_flags *rf) { if (!on_rt_rq(&p->rt) && need_pull_rt_task(rq, p)) { ① /* * This is OK, because current is on_cpu, which avoids it being * picked for load-balance and preemption/IRQs are still * disabled avoiding further scheduler activity on it and we've * not yet started the picking loop. */ rq_unpin_lock(rq, rf); pull_rt_task(rq); ② rq_repin_lock(rq, rf); } return sched_stop_runnable(rq) || sched_dl_runnable(rq) || sched_rt_runnable(rq); }
balance()ハンドラなので、RTタスクが__schedule()を呼んだ延長で実行されますが、そのタスクがdequeueされた結果、CPUの「最高優先度」が下がってしまった場合(①)、pull_rt_task()でpull型ロードバランスを行っていることがわかります。
前述の通り、pull型ロードバランス処理を担うpull_rt_task()の役割は、他のCPUのpushable_tasksからRTタスクを自CPUに移動する事ですが、主な処理を抜粋すると以下のようになります。
static void pull_rt_task(struct rq *this_rq) { int this_cpu = this_rq->cpu, cpu; struct task_struct *p; struct rq *src_rq; for_each_cpu(cpu, this_rq->rd->rto_mask) { ① if (this_cpu == cpu) continue; src_rq = cpu_rq(cpu); /* * Don't bother taking the src_rq->lock if the next highest * task is known to be lower-priority than our current task. * This may look racy, but if this value is about to go * logically higher, the src_rq will push this task away. * And if its going logically lower, we do not care */ if (src_rq->rt.highest_prio.next >= ┐ this_rq->rt.highest_prio.curr) │ ② continue; ┘ /* * We can potentially drop this_rq's lock in * double_lock_balance, and another CPU could * alter this_rq */ double_lock_balance(this_rq, src_rq); /* * We can pull only a task, which is pushable * on its rq, and no others. */ p = pick_highest_pushable_task(src_rq, this_cpu); ③ /* * Do we have an RT task that preempts * the to-be-scheduled task? */ if (p && (p->prio < this_rq->rt.highest_prio.curr)) { ④ deactivate_task(src_rq, p, 0); set_task_cpu(p, this_cpu); activate_task(this_rq, p, 0); /* * We continue with the search, just in * case there's an even higher prio task * in another runqueue. (low likelihood * but possible) */ } double_unlock_balance(this_rq, src_rq); } resched_curr(this_rq); }
rto_maskの各CPUについて(①)、そのCPUのpushable_tasks内で最高優先度のタスクが自CPUの「最高優先度」より優先度が高ければ(②)、pushable_tasks内から自CPUで動作可能で且つ優先度の高いタスクを選択し(③)、そのタスクが自CPUの「最高優先度」より優先度が高ければ(④)*16、自CPUにそのタスクを移動する、ということを繰り返します。
pull型ロードバランスについて、具体的な例を使って図解してみます(4CPUのシステムで、□がRTタスク(中の数値はprio))。
「CPU:0にprio:10とprio:50のタスク(prio:10のタスクが実行状態で、prio:50のタスクが実行待ち)、CPU:1-2にprio:20のタスクが1つずつ割り当てられている」状況を考えます。この時、CPU:0ではprio:50のタスクがpushable_tasksに入っているので、rto_maskも立てられています。また、それぞれのCPUの「最高優先度」は、10、20、20、20となります。
ここで、CPU:1のRTタスクが何らかの理由でスリープするとすると、CPU:1の「最高優先度」は20→99と下がることになり、CPU:1の__schedule()の延長で、balance_rt()→pull_rt_task()が実行されます。
前述した通り、pull_rt_task()はrto_maskを参照し、ビットが立っているCPUのpushable_tasksからタスクを自CPUに移動するので、CPU:0にenqueueされていたprio:50のタスクをCPU:1に移動し、実行状態とします(同時に、CPU:0のrto_maskもクリアされます)。
4.3.4 push型ロードバランス(push_rt_tasks())
push型ロードバランスについては、4.3.2で少し触れました、「起床したRTタスクが実行中のRTタスクより優先度が高かった場合」を例に説明しますが、まずは、push型ロードバランス処理を担う、push_rt_tasks()について解説します。
前述の通り、この役割は、自CPUのpushable_tasksのRTタスクを他CPUに移動する事ですが、その実装は、pushable_taskのタスクを1つ他のCPUに移動する関数である、push_rt_task()がtrueを返す限り(つまり、pushable_tasksのタスクを移動できる限り)それを繰り返し実行する形になっています。
push_rt_task()の主な処理を抜粋すると以下のようになっています。
static int push_rt_task(struct rq *rq, bool pull) { struct task_struct *next_task; struct rq *lowest_rq; int ret = 0; next_task = pick_next_pushable_task(rq); ① if (!next_task) return 0; /* We might release rq lock */ get_task_struct(next_task); /* find_lock_lowest_rq locks the rq if found */ lowest_rq = find_lock_lowest_rq(next_task, rq); ② deactivate_task(rq, next_task, 0); ┐ set_task_cpu(next_task, lowest_rq->cpu); │ ③ activate_task(lowest_rq, next_task, 0); ┘ resched_curr(lowest_rq); ④ ret = 1; double_unlock_balance(rq, lowest_rq); put_task_struct(next_task); return ret; }
pushable_tasksの先頭からタスクを取り出し(①)、当該タスクを実行できるCPUの中で「最高優先度」が最も低いCPUを探してきて(②)*17、そのCPUにenqueueしなおし(③)、TIF_NEED_RESCHEDを立てることで今移動したタスクにスケジューリングの機会を与えます(④)。
push型ロードバランスについても、具体的な例を使って図解してみます(前項同様、4CPUのシステムで、□がRTタスク(中の数値はprio))。
「CPU:1でタスクα(prio:50)を実行中に、(スリープ状態に入る前は、CPU:1で動作していた)より優先度の高いタスクβ(prio:10)が(待っていたイベントが発生する等して)実行可能になった」状況とします。
この場合、push_rt_tasks()が実行されるまでの流れを整理、図解すると以下のようになります。
- タスクβ起床前
- タスクβの起床処理(
try_to_wake_up())- 前述の通り、CPU:1が動作CPUとして選択される。
- いくつかパターンがあるが、いずれにしても
ttwu_do_activate()で最終処理を行う。activate_task()でタスクβをenqueueする(一旦、タスクβはpushable_tasksに入る)。wakeup_preempt()->wakeup_preempt_rt()により、タスクαがプリエンプトされる。task_woken_rt()は、既にタスクαがプリエンプトされているため、何もしない。
- プリエンプトされたタスクαの
__schedule()での、次タスクの選択処理(__pick_next_task())balance_rt()は何もせずtrueを返す(4.3.4参照)。put_prev_task_rt()によりタスクαがpushable_tasksに入る。pick_next_task_rt()によりタスクβが選択されると共に、set_next_task_rt()で、タスクβがpushable_tasksから外され、push_rt_tasks()をbalance_callbackに登録する*18。
__schedule()の最後にbalance_callback経由でpush_rt_tasks()を実行
最後に
(その1)を皮切りに、「タスクスケジューラ」、即ち、どのタスクを、どのCPUで、どのくらいの時間実行するかの判断ロジックについて解説してきました。また、その前には、プロセスディスパッチャ(タスクの切り替え処理)についてもまとめています(前編/後編)。
割り込み処理など例外はありますが、システムは基本的に何らかのタスクを切り替えながら動いています*19。これらの一連の記事が、システムがどう動いているかを頭の中でイメージする一助になってくれれば幸いです。
*1:これらの仕組みはタスクのCPU affinityを更新するのが目的です。本記事では、設定されているCPU affinityの中でどのCPUでタスクを実行するか、という所にフォーカスしています。
*2:SCHED_DEADLINEはSCHED_RTと共通する部分も多い、というのもあります。
*3:後述する他のパターンでは対象となるタスクもその時の状況で変わります。
*4:rq->balance_callbackを先頭としたリストに、balance_callback構造体を繋げ、そのfunc()を実行する仕組みです。
*5:本稿ではbalance_callback構造体の事を「callback」、そのfunc()の事を「callback関数」と呼称します。
*6:他のスケジューリングクラスでも使われないわけではないですが、特に重要になるのがSCHED_FAIRの場合なので、ここで解説しています。
*7:本稿では、この構造全体の事を指す用語として「スケジューリングドメイン」を使い、sched_domain構造体自体を指す場合は単に「sched_domain」「sd」、sched_group構造体自体を指す場合は単に「sched_group」「sg」と表記します。
*8:元々動作していたCPUを優先的に割り当てようとします。
*9:とはいえLinuxではよくある方法です。
*10:pull型ロードバランスを行う関数で次項でも出てきます。
*11:これでタスクを移動できない場合、active load balanceという処理に移るのですが、本稿では触れません。
*12:説明の都合上、「span:2のsched_groupをsg:2」というように表記しています。
*13:"highest"とついていますが、高優先度になる程、値としては小さくなります。
*14:本稿では「rd(root_domain)」については触れていませんが、「システムの全CPU(厳密には違いますが)の負荷状態を管理するための管理データ」という理解で問題ありません。
*15:「rto」は「RT overload(ed)」の略だと思われます。
*16:②のチェックではタスクが自CPUで動作可能かどうかの確認は行っていないため、このチェックが必要となります。
*17:rq->lockも確保します。
*18:デッドロック回避のため直接呼び出したりはしません。
*19:ソフトウェア割り込みについてはこちらの記事にまとめてありますが、ハードウェア割り込み含め、カーネル空間⇔ユーザ空間のentry/exitの全体像についていつかまとめたいですね。
