🫠
LinuxのSCHED_BATCHスケジューリングは何をしているのか

2024/06/01に公開
※ この内容はkernel 6.10-rc1(2024/5)時点のものです

Linuxのスケジューリングポリシーの中にSCHED_BATCHというものがあるが一体何をしているのか、という疑問に答える文章になります。

 はじめにLinuxのタスクスケジューラーにはいくつかのスケジューリングポリシーがあり、それらの説明はsched(7)のmanページにまとまっています(debianの日本語訳):
https://man7.org/linux/man-pages/man7/sched.7.html
ポリシーは以下のように分類されます:
リアルタイムポリシー (通常ポリシーのタスクよりも常に高い優先度を持つ)
SCHED_DEADLINE (*)
SCHED_FIFO
SCHED_RR

通常ポリシー
SCHED_OTHER (SCHED_NORMAL**)
SCHED_BATCH
SCHED_IDLE

(*) ... SCHED_DEADLINEはSCEHED_FIFO/SCHED_RRよりも高い優先度を持ちます

(**) ... SCHED_OTHERはPOSIXで定義される名前。linuxコード中はSCHED_NORMALです
デフォルトのポリシーはSCHED_OTHERです。ポリシーはsched_setscheduler(2)やsched_setattr(2)システムコール、あるいはchrtコマンドなどで変更します。
よくLinuxのタスクスケジューラーはCFS(Complete Fair Scheduler*)と説明されますが、これはSCHED_OTHERとSCHED_BATCHに使用されるロジックであり、タスクに割り当てるCPU時間が均等になるようにスケジューリングします。例えば1CPUに5タスク存在する場合はそれぞれのタスクが20%のCPU時間を使うようにスケジューリングします。ただし割り当て時間は各タスクのnice値によって重みづけされて変動します。なおSCHED_IDLEは最低nice値(20)よりもさらに低い優先度を持つリシーになります(つまり他に動かすタスクがない時以外スケジュールされない)。
(*) CFSは6.6よりEEVDF(Earliest Eligible Virtual Deadline First)schedulerに置き換え(アップデートというべき？)られていますが、依然としてCFSという名前は残っているように見えます。なおEEVDFはタスクに割り当てるCPU時間を均等にするという点でCFSと同じですが、それに加えて各タスクのレイテンシ要件も考慮する仕組みであり、低レイテンシを必要とするタスクに対する一回の割り当て時間（タイムスライス）を短くします。タスクに分配される総時間は変わらないため1回のタイムスライスが短い分そのタスクはより多くの回数スケジューリングされることになり、低レイテンシになります（つまり各タスクに対しnice値に加えてレイテンシ要件のパラメータを設定できます。ただしレイテンシ要件を個別に設定する仕組みは6.10の時点ではマージされていません。sched_setattr経由でレイテンシ要件を設定する仕組みが議論中です: Linux ML)。EEVDFについてはlwnの記事も参考にしてください。
さてそれぞれのポリシーの動きについてはschedのmanページにまとめられているのですが、SCHED_BATCHの具体的な動きについてはいまいちはっきりしません:
   SCHED_BATCH: Scheduling batch processes
       (Since Linux 2.6.16.)  SCHED_BATCH can be used only at static
       priority 0.  This policy is similar to SCHED_OTHER in that it
       schedules the thread according to its dynamic priority (based on
       the nice value). The difference is that this policy will cause
       the scheduler to always assume that the thread is CPU-intensive.
       Consequently, the scheduler will apply a small scheduling penalty
       with respect to wakeup behavior, so that this thread is mildly
       disfavored in scheduling decisions
SCHED_BATCHは名前の通りバッチジョブを意識したポリシーで、CPU-intensiveかつインタラクティブ性を必要としないタスクで使うことを想定しています。前半の説明にはSCHED_OTHERと基本的に同じであると書かているだけなので問題ありません。しかしながら後半、特に最後の文の"mildly disfavored in scheduling decisions"(日本語訳は"若干冷遇される")などの説明はかなりふわっとした感じです。ネットを調べてみても具体的な動作についてはあまり情報がなさそうです。
一方でkernelドキュメントの方を見ると以下の記述があります:
SCHED_BATCH: Does not preempt nearly as often as regular tasks would,
thereby allowing tasks to run longer and make better use of caches but
at the cost of interactivity. This is well suited for batch jobs.
こちらには通常のタスクよりpreemptしないと書かれています。これらを踏まえてSCHED_BATCHの場合に実際に何をしているのか確かめようというのが今回の話です。

 結論結論は以下です(kernel 6.10の時点)
SCHED_BATCHポリシーのタスクはwakeupした際(ブロック状態から実行可能状態になったとき)に他のタスクをpreemptしなくなる
それ以外の動きはSCHED_OTHERと同じです。よってSCHED_BATCHのタスクはレイテンシがやや大きくなる代わりに、他のタスクを邪魔することが減るはずです(kernelドキュメントの説明と同じ)。
以下でSCHED_BATCHの変遷について説明します。

 調査過程
 現時点(6.10-rc1)のコードまず現時点のコードを見てみると、驚くことに(?)SCHED_BATCHを使用している箇所がコード中にありません: https://elixir.bootlin.com/linux/v6.10-rc1/A/ident/SCHED_BATCH
正確に言うとないわけではありませんが
uapiの定義
sched_get_priority_{min,max}システムコールの応答
taskのポリシーがfairポリシーかどうかの判定 (SCHED_NORMAL or SCHED_BATCHの判定)
ドキュメント・コメント
の箇所でしか参照されておらず、SCHED_BATCHに対して特別な処理をしているところがありません。

いつのまにかdeprecateされてしまったのか...?とも思いますがさすがにそれだったらニュースになっているはずなのでもう少し確認すると以下のコードが見つかります。
/*
 * Preempt the current task with a newly woken task if needed:
 */
static void check_preempt_wakeup_fair(struct rq *rq, struct task_struct *p, int wake_flags)
{
...
	/*
	 * Batch and idle tasks do not preempt non-idle tasks (their preemption
	 * is driven by the tick):
	 */
	if (unlikely(p->policy != SCHED_NORMAL) || !sched_feat(WAKEUP_PREEMPTION))
		return;
SCHED_NORMALでないかどうかで判定しているため単純なgrepに引っ掛かりません(SCHED_BATCHとSCHED_IDLEを対象にするため)。このcheck_preempt_wakeup_fairはタスクがwakeupしたタイミングで呼ばれる関数(*)で、実行中のタスクをpreemptするか判定します（もう少し正確に説明すると、preemptすると判断した場合はresched_curr()経由でpreemptされるタスクに_TIF_NEED_RESCHEDフラグを立てます）。CFSの基本的な考えは各タスクにCPU時間を均等に割り振ることなので、wakeupした(≒しばらく実行されていない)タスクを優先して実行するべきか判断しているということになります。コメントの通りSCHED_BATCH(とSCHED_IDLE)の場合は無条件でpreemptせず、つまり実行中のタスクの邪魔をしない動きになります。
(*) 例えば以下のパス
- wake_up_process
  - try_to_wake_up
      - ttwu_queue
          - ttwu_do_activate
              - wakeup_preempt
                  - sched_class->wakeup_preempt (CFSならcheck_preempt_wakeup_fair)
さてSCHED_BATCHの挙動を知るという意味では以上の確認で十分ですが、manページの"mildly disfavored ..."という説明に少しあっていないようにも感じます。コードは頻繁に進化するのでドキュメントが書かれた時点からコードが進化したのかもしれません。ということで昔のコミットを確認します。

 過去に遡る(githubでもblameしたりlogをgrepできますが、あまり昔の情報は検索できないようなのでローカルにクローンして調査しています)

 SCHED_BATCH導入時そもそもSCHED_BATCHが導入されたコミットを探すと2.6.16(2006年)の以下のコミットであることが分かります: コミット

コミットログを確認すると気になる記述があります:
Add a new SCHED_BATCH (3) scheduling policy: such tasks are presumed
CPU-intensive, and will acquire a constant +5 priority level penalty. 
SCHED_BATCHの場合は一定のペナルティが課されると書いてあります。なおここで重要なポイントですが2.6.16の時点ではCFSは導入されていません。
さてコミットを見るとSCHED_BATCHのタスクのsleep_avgを0にセットしているようですがそれを使っているところがありません。コードの他の場所を見るとsleep_avgの値によってprioirtyに補正をかけていることが分かります(コード)。
#define CURRENT_BONUS(p) \
	(NS_TO_JIFFIES((p)->sleep_avg) * MAX_BONUS / \
		MAX_SLEEP_AVG)
...
/*
 * effective_prio - return the priority that is based on the static
 * priority but is modified by bonuses/penalties.
 *
 * We scale the actual sleep average [0 .... MAX_SLEEP_AVG]
 * into the -5 ... 0 ... +5 bonus/penalty range.
...
 */
static int effective_prio(task_t *p)
{
...
	bonus = CURRENT_BONUS(p) - MAX_BONUS / 2;
	prio = p->static_prio - bonus;
...
	return prio;
}
マクロの計算が煩雑のため引用は省略しますがMAX_BONUSは10になります。よってsleep_avgが0のときbonusは-5になり、effective_prio()の中でprioの値が+5されます。prioの値はnice値と同じで高いほど優先度が低くるため、コミットログの通りSCHED_BATCHの場合は優先度が常に5低くなります。
以上より実装当初はSCHED_BATCHのタスクの優先度を一律に下げていたことが分かります。

 CFS導入時約1年半後の2007年にリリースされた2.6.26にそれまでのスケジューラに代わりCFSが導入されます: コミット
これによりスケジューラの実装が変わったことにより先ほどのeffective_prioの処理は削除されました: このあたり

よってSCHED_BATCHに対する優先度の変更は行われなくなりました。
一方、新しく追加されたCFSのコードにおいて、SCHED_BATCHの場合はwakeup時に他のタスクをpreemptするかどうかの判断にSCHED_NORMALよりも補正をかけるようになりました。まず補正値が以下のようになっており:
unsigned int sysctl_sched_batch_wakeup_granularity __read_mostly =
							10000000000ULL/HZ;
...
unsigned int sysctl_sched_wakeup_granularity __read_mostly = 1000000000ULL/HZ;
wakeup時の呼ばれるコードは以下になっています：
/*
 * Preempt the current task with a newly woken task if needed:
 */
static void check_preempt_curr_fair(struct rq *rq, struct task_struct *p)
{
...
	gran = sysctl_sched_wakeup_granularity;
	/*
	 * Batch tasks prefer throughput over latency:
	 */
	if (unlikely(p->policy == SCHED_BATCH))
		gran = sysctl_sched_batch_wakeup_granularity;

	if (is_same_group(curr, p))
		__check_preempt_curr_fair(cfs_rq, &p->se, &curr->se, gran);
}
...
/*
 * Preempt the current task with a newly woken task if needed:
 */
static void
__check_preempt_curr_fair(struct cfs_rq *cfs_rq, struct sched_entity *se,
			  struct sched_entity *curr, unsigned long granularity)
{
	s64 __delta = curr->fair_key - se->fair_key;
...
	/*
	 * Take scheduling granularity into account - do not
	 * preempt the current task unless the best task has
	 * a larger than sched_granularity fairness advantage:
	 *
	 * scale granularity as key space is in fair_clock.
	 */
	if (__delta > niced_granularity(curr, granularity))
		resched_task(rq_of(cfs_rq)->curr);
}
wakeupされたタスクと実行中のタスクの実行時間の差が一定よりも大きい場合はpreemptしているようですが、SCHED_BATCHの際にはより差が大きくなければpreemptしないようにしています(NORMALは1msに対してBATCHは10ms)。もしかしたらsched(7)の記述("apply a small scheduling penalty with respect to wakeup behavior")はこのときの挙動の説明から来ていたのかもしれません。
しかし割とすぐに以下の変更でbatch_wakeup_granularityはなくなり、NORMALとBATCHの違いに関係なくwakeup_granularityだけ使われるようになります：コミット, コミット

1つになったwakeup_granularityはしばらく残っていたのですが、EEVDF導入時に他のいくつかのパラメータともになくなりました（ちなみにEEVDFの導入の目的の一つがCFSのヒューリスティックなロジックを削除することでした）: このあたり
一方でbatch_wakeup_granularityがなくなるのと同じころにSCHED_BATCHのときはそもそもwakeupしない処理が追加されました: コミット

ここの部分の処理（の発展）が上で説明した6.10の時点のコードになります。

 補足: yieldの扱いSCHED_BATCHの変更を追っていくとyieldの処理でもかつてはSCHED_BATCHで分岐処理をしていたことが分かります: コミット
これはyield(2)などでタスクが明示的にCPUを受け渡すときに呼ばれる処理です。このコミットの意図がやや読み解けないのですが、SCHED_BATCHの場合はyield時にタスクのvruntime(実行された時間)をrunqueueの最も右端のタスクの値+1としています（右端が最もvrumtimeが長くなるようにソートされています）。つまりyieldするSCHED_BATCHのタスクはすでに他のタスクよりも実行されたと見なされ、実質的にタスクの優先度が下がる動きになっていたようです。
ただしこれも数回変更のあったのち、最終的にEEVDF導入時になくなりました: このあたり

ということで6.10の時点ではyieldのパスにNORMALとBATCHの差はありません。

 終わりにすぐに結果が判明すると思って終わりを見ずにまとめ始めたら意外と遍歴がありました。まとめるとSCHED_BATCH導入時（やCFS導入時）にはSCHED_NORMALに比べてSCHED_BATCHタスクの優先度を下げる仕組みがあったものの、今ではそれは廃止され、wakeup時のpreempt抑制の処理のみが残っている状況なのではないかと推測します。よってドキュメントの説明の通りインタラクティブ性を必要しないバッチジョブに向いているポリシーと言えます。なお当然ながらコードはどんどん進化していくので今後も内部の動きは変わる可能性はあります。
以上
12/5 追記: 補足記事を書きました: LinuxのSCHED_BATCHスケジューリングは何をしているのか (補足)
はじめに

結論

調査過程

現時点(6.10-rc1)のコード

過去に遡る

SCHED_BATCH導入時

CFS導入時

補足: yieldの扱い

終わりに

Discussion
