いつどのようにプロセスを切り替えるのか

• 7.1 スケジューリング方針
  • 7.1.1 プロセスプリエンプション
  • 7.1.2 最適なクォンタムの長さ
• 7.2 スケジューリングアルゴリズム
  • 7.2.1 従来型プロセスのスケジュール
  • 7.2.2 リアルタイムプロセスのスケジュール

• 7.3 スケジューラが使用するデータ構造
• 7.4 スケジューラが使用する関数
• 7.5 マルチプロセッサにおける実行キューの負荷均衡化処理
  • 7.5.1 スケジューリングドメイン
• 7.6 スケジューリング関連のシステムコール

求めるもの

• 良好な応答時間
• バックグラウンドジョブの高いスループット
• プロセス飢餓(fdなどのシステム資源を獲得できない状態の回避
• 低い優先度のプロセスと高い優先度のプロセスからの要求の調整

Linux のスケジューリング: 時分割(タイムシェアリング)

• 複数のプロセスを「同時多重」に動作する
• CPU 時間を大まかなスライスに分割し、それぞれのスライスを各実行可能プロセスに割り当てる
• 1つのプロセッサは、一時点では1つのプロセスしか実行できない
• カレントプロセスがタイムスライスやクォンタムを使い切っても終了していないときには、プロセス切り替えを実行

優先度に基づいたスケジューリング

• プロセスの優先度を動的に変更
• 長時間CPUを使えなかったプロセスの優先度は動的に上ける
• 逆に、長時間動作しているプロセスの優先度を下げる

スケジューリングにおけるプロセスの分類その１

• 1) I/Oバウンド型
  • 多くの時間を I/O 操作の完了待ちに費やすやつ
• 2) CPUバウンド型
  • 多くの CPU 時間を必要とする大量の演算を行うやつ

スケジューリングにおけるプロセスの分類その２

• 1) 対話型プロセス
  • ユーザと対話的に動作、キー入力やマウス操作を待つ
  • 入力があったときにはすぐにプロセスを起床しなければならない
  • 平均的な遅延時間が50ミリ秒から 150ミリ秒の範囲であるべき
  • ex) コマンドシェル、テキストエディタ、GUI アプリケーション

スケジューリングにおけるプロセスの分類その２

• 2) バッチプロセス
  • ユーザの操作が必要ない、よくバックグラウンドで実行される
  • 応答性が重要でないため、優先度を下げられがち
  • ex) コンパイラ、データベー スの検索エンジン、科学計算
• 3) リアルタイムプロセス
  • スケジューリング要求が非常に厳密なプロセス
  • 短い応答時間を保証し応答時間のばらつきも最小限にすべき
  • ex) ビデオやサウンド

• 高度な発見的アルゴリズム
  • 対話型、バッチの区別は難しいが、リアルタイムを区別
  • I/O バウンド型か CPU バウンド型か認識

• プリエンプト、つまりタスクの差し替えが可能
• プロセスが TASK_RUNNING になったら
  • そのプロセスの動的優先度とカレントプロセスの優先度を比較
  • 優先度が高ければ割り込んでスケジューラを呼び出す(そのプロセスになるとは限らない)
• プロセスがクォンタム時間を使い切ったら
  • プリエンプトされる(実行権を奪われる)

用例

• × オレを malloc していいかな?!
• ○ オレが preempt していいかな?!

• テキストエディタとコンパイラ
• 1) コンパイラが動いている
• 2) ユーザ入力 -> 割り込み発生
• 3) テキストエディタのプロセスを起床
  • 3.1) カーネルがTIF_NEED_RESCHED フラグを設定(スケジューラを強制的に起動)
  • 3.2) スケジューラがテキストエディタへプロセス切り替え
• 4) エディタが文字を画面に表示 -> 待ち状態(TASK_RUNNING ready)
• 5) コンパイラのプロセスが実行

• 実行権を奪われたプロセスは待ちに入るわけではなく、TASK_RUNING のまま

• 短いとプロセス切り替えが頻発して辛い
• 長すぎるとプロセスが同時に実行されているように見えなくなる
  • 対話型は優先度が高いし割り込みを使うので大抵すぐ実行される
• 常に妥協の産物。経験則

• 初期: 全走査して優先度を計算、選択。O(N)
• 2.6: プロセス数、CPU数によらず一定。O(1)
  • 実行可能なプロセスのキューを各CPUが個別にもっている
• CPUバウンド、I/Oバウンドの識別が向上
  • 対話型アプリケーション(I/Oバウンド)の応答がよくなったと感じるはず
• 実行可能なプロセスは必ず見つけ出すことができる
  • PID 0 の swapper プロセスが各 CPU ごとにいる

• SCHED_NORMAL (or OTHER): 普通のやつ。nice 値で優先度設定
• (追加) SCHED_BATCH: バッチ形式
• (追加) SCHED_IDLE: 「非常に」低い優先度のバックグラウンドジョブ
• リアルタイム用: SCHED_FIFO と SCHED_RR
• sched_setschduler(2) で指定

リアルタイム

• SCHED_FIFO
  • nice 値のかわりに 1(最低) から 99 (最高) の固定優先度
  • 必ず SCHED_NORMAL より優先
  • 同じか低い優先度がいても実行し続ける
• SCHED_RR
  • 同じ優先度のものがあれば平等に切り替える

SCHED_OTHER

• 静的優先度の値を100(最高値)から 139(最低値)までの範囲て表現
• 100 == nice(-20). 139 == nice(19)
• 新しいプロセスは、親プロセスから静的優先度を引き継ぐ
• ユーザが所有するプロセスなら、nice(2)やsetpriority(2)で変更できる

• 静的優先度が基礎クォンタム時間を決定
• 優先度が高いほど基礎クォンタム時間が長くなる

動的優先度 = max ( 100, min (静的優先度 - ボーナス + 5, 139 ) )

• 動的優先度も100(最高値)から、139(最低値)の範囲
• ボーナスは 0 - 10。5より小さい場合は優先度が低下
• top コマンドの PRI 列(100 引かれているが)

• ボーナスは、プロセスの平均休止時間に関係
• 平均休止時間 = プロセスが休止している間に経過した時間
• ただし
  • TASK_INTERRUTIBLE と TASK_UNINTERRUTIBLE での休止時間では、平均休止時間の算出が違ったり
  • プロセス実行の間、平均休止時間は減算されたり
  • 平均休止時間は１秒より大きくならなかったりする

平均休止時間とボーナス値の関係式。タイムスライス粒度はあとで

• 平均休止時間(ボーナス)を元にI/Oバウンド型か判断
• 「静的優先度 / 4 - 28」対話型差分と呼ばれる

動的優先度 <= 3 x 静的優先度 / 4 + 28

または(上下は同等な式)

ボーナス値 - 5 >= 静的優先度 / 4 - 28

• 優先度の高いプロセスのほうが対話型(I/Oバウンド)になりやすい
• 例えば、標準優先度(120)のプロセスは、平均休止時間が700ミリ秒を超えると対話型になる

• 活動プロセス(active processes)
  • 実行可能プロセスがクォンタムを使い切っておらず、実行を許されている。
• 時間切れプロセス(expired processes)
  • 実行可能プロセスがクォンタムを使い切っており、すべての活動プロセスが時間切れするまで実行を禁止されている

• どちらもTASK_RUNNABLEだけど、activeキューとexpiredキューがある

cf. Linx Kernel Documents 1.6 プロセススケジューラの実装

• バッチ型プロセスがクォンタムを使い切ると必ず時間切れ状態に
• 対話型プロセスがクォンタムを使い切っても活動状態のまま
• しかし
  • 対話型プロセスを時間切れ状態のプロセスに移動することもある
  • 1) 最初に時間切れ状態に移行したプロセスがすでに長い時間待っている場合
  • 2) 時間切れ状態のプロセスの静的優先度が対話型よりも高い場合
• 結果、活動状態のプロセスの集合はやがて空になり、時間切れプロセスに実行の機会が与えられる
• プロセススケジューラはactiveキューをexpiredキューと交換して処理を継続

• リアルタイムプロセス: 1(高優先度) - 99 (低優先度)
• 常に活動状態
• SCHED_FIFO: 優先度が同じならば実行し続ける
• SCHED_RR: クォンタム時間を使い切ったら切り替える

• sched_setscheduler(2) でできるのはそうだけど、
• それを使った chrt コマンドというものがある
• cf. リアルタイムの優先度を変更してプログラムを実行する - TK’s HP
• 動的にリアルタイムプロセスに移行することがある？？ない？(追記)A.ない

• SCHED_OTHER と同様の動作
• スケジューラが「常に負荷のかかる処理を行う」と仮定し、プロセスにペナルティを課すため、プロセスはスケジューリングの決定で若干冷遇される
• SCHED_OTHER と異なり、平均休止時間を最小として、動的優先度の計算を行う

• 何に使ってるのか不明

Go to p284

• TASK_RUNNING プロセスをのキュー
• active と expired があり、それぞれが別のプロセスリスト

• arrays[0] と arrays[1] のどちらかが active で expired (切り替わる)
• active[0]、なければ active[1] のように高い優先度から順繰りアクセス
• 0..139 と書いてあるが、100..139 (もしくは 100 引いて 0..39) では？

Go to p285

• copy_process した時に、
• 親プロセスの残り tick 数を、親と子に半分ずつ分ける
• 際限なくCPUを使うチート術を防ぐため

• scheduler_tick(): カレントプロセスの time_slice カウンタを最新の値に更新する
• try_to_wake_up(): 休止状態のプロセスを起床する
• recalc_task_prio(): プロセスの動的優先度を更新する
• schedule(): 新しく実行すべきプロセスを選択する
• load_balance(): マルチプロセッサシステムの実行キューの負荷を均衡化する

• Timer 割り込みで1ms刻みで実行
• 現在走っているプロセスのtimeslice -= 1
• 現在走っているプロセスのtimeslice == 0 だったらそのプロセスを expired array に退避させ(I/Oバウンド型の場合はactive arrayに再挿入)、TIF_TASK_NEED_SCHEDフラッグを立て、schedule()が呼ばれるようにする。
• InteractiveプロセスがTIME_GRANUALITY走ったら次のプロセスに譲るように施す。

cf. http://www.logos.ic.i.u-tokyo.ac.jp/~kenny/presentation/linux_sched26.ppt

7.4.1.1 リアルタイムプロセスのタイムスライスの更新

• SCHED_FIFO の場合、scheduler_tick() はなにもしない
• クォンタム関係ない。タイムライスカウンタを減算する意味がない。
• SCHED_RR なら減算する

• 休止または中断しているプロセスを起床 (TASK_RUNNING)
• ここでプロセスを起床する CPU を決定する
  • 前回に実行したCPUの負荷がローカルCPUの負荷よりもずっと小さい場合は、前回に実行したCPU
  • プロセススがつい最近実行されていた場合は、前回に実行したCPU
  • ローカルCPUに移動して負荷を均衡化できるなら、ローカルCPU
• CPUを移動した場合に
  • タイマ割り込みのズレを補正
  • 新しいCPUで優先度が高ければ実行権を奪う

• プロセスの平均休止時間と動的優先度を更新
• sleep_avg を計算して、そこから prio を計算

• 寝るプロセスはrunqueueから外す。
• Active Arrayの中から一番優先度の高いプロセスを見つけ、CPUを今まで使っていたプロセスとcontext switchを行う。(CPU、メモリの交換)
• 主にscheduler_tick()によって呼ばれる。
• プロセスが明示的にschedule()を呼んで、CPUを返上することも出来る。

cf. http://www.logos.ic.i.u-tokyo.ac.jp/~kenny/presentation/linux_sched26.ppt

• 直接呼び出し
  • 資源が利用不可な場合、schedule() を直接呼び出して、CPUを他のプロセスに譲る
• 遅延呼び出し
  • クォンタムを使い果たした or プロセス起床時にカレントプロセスの優先度よりも高い
  • TIF_NEED_RESCHEDフラグを1に設定して、遅延呼び出し

時間ないし、詳細すぎるし、飛ばします(´・ω・`)

• 1) 古典的マルチプロセッサ (UMA)
  • すべてのCPUで共用するRAM
• 2) ハイパースレッディング
  • 同時に複数のスレッドを実行
  • 内部レジスタを複数組持ち高速に切り替える
• 3) NUMA
  • 全プロセッサから等価にアクセスできるグローバルなメモリの他に，プロセッサ専用のバスと接続されたメモリを持つ
  • ex) 24CPU => 2ノード x 12コア。1ノードにローカルメモリ

• cf. マルチプロセッサ用リアルタイムOSの解説 - ハードウェアアーキテクチャから見たマルチプロセッサの分類

• lscpu でノード数見れる
• /proc/cpuinfo でも分かる

• プロセスが実行可能状態であり続ける限り、プロセスはたいていどこか１つのCPUにくくりつけられる
• ハードウェアキャッシュが利いてうれしい
• 場合によっては、１つのCPUに集中してしまってうれしくない
• => 仕事量が偏っていないか定期的に確認する

• カーネルが負荷の均衡を保つべきCPUの集合体の概念
• 階層的
  • 最上位: システムの全CPUを管理、子ドメインを持つ
  • 子ドメイン: CPUの部分集合を持つ
• 複数のグループに分割される
  • グループ == ドメイン内のCPUの部分集合
• 負荷均衡処理は、同じドメイン内のグループ間でのみ行う

ハイパースレッディング

• 基礎ドメイン(一番下)
  • 各グループ１論理CPU
  • このグループ間で負荷均衡処理
• １つ上のドメイン
  • 各グループ１物理CPU
  • 物理CPUで負荷均衡処理

NUMA

• 基礎ドメイン
  • 各グループ１物理CPU
  • 物理CPUで負荷均衡処理
• １つ上のドメイン
  • 各グループ１NUMAノード
  • NUMAノードで負荷均衡処理

• tick ごとに１回呼び出される。負荷均衡を担当
• 基礎ドメインから最上位ドメインに至まで繰り返し処理を行う
• load_balance() を呼び出す

• 最も負荷の高いグループからローカル CPUに対して移動することによって、負荷の不均衡を削減できるかどうかを確認
• もし、不均衡を削減できる状態ならば、load_balance()関数は、プロセスの移動を試みる

• 別の実行キューからローカル実行キューへプロセスを移動
• can_migrate_task() が 1 を返したときだけなので、必ず移動するわけではない

• ユーザが自分のプロセス優先度を下げることはできる
• 他のユーザのプロセスや優先度を上げるには root 権限が必要

• 静的優先度の変更
• getpriority(), setpriority() に置き換えられている
• nice(1) コマンド。-20 (最高) 〜 19 (最低)

nice -n -20 find /
top # NI が nice で PR が動的優先度

• 指定したグループのプロセス全てを対象にする
• getpriority() はグループ内でも最も高い優先度を返す
• setpriority() はグループ内すべてのプロセスを設定する
• 第一引数に PRIO_PROCESS (pid指定), PRIO_PGRP (pgrp指定), PRIO_USER (uid指定) を指定する

• プロセスのCPUアフィニティマスクを取得
• このプロセスはCPUコア1番だけ使わせる！とか規定できる

taskset 0x00000001 pid

• 専用ではない
  • sched_getscheduler()、sched_setscheduler()
  • sched_getparam(), sched_setparam()
  • sched_yield
  • sched_get_priority_min()、sched_get_priority_max
• SCHED_RR 専用
  • sched_rr_get_interval()

• 静的優先度(nice値)だけじゃない。動的に優先度を変更
• 平均休止時間が長いとボーナス高くなる => I/Oバウンド型になりやすい
• 優先度が高いほどボーナスの閾値(対話型差分)が小さくなる => I/Oバウンド型になりやすい
• I/Oバウンド型に区別されると、クォンタムを使い切っても(通常)活動状態のままという特典

• O(1) で最高優先度のプロセスを見つけられるアルゴリズム
• O(1) でactiveキューとexpiredキューを入れ替えられる
• リアルタイムプロセスは必ず通常プロセスより優先
• スケジュールドメインという抽象概念で色々なCPU topologyをサポートしてリバランス

おまけで紹介したコマンド

• 静的優先度を変更する nice コマンド
• cpu の情報を見る lscpu コマンド
• リアルタイムプロセスを作れる chrt コマンド
• affinity を設定できる taskset コマンド

• 7.1. 高度な発見的アルゴリズムによってリアルタイムプロセスを区別
  • => SCHED_FIFO とかのフラグ見てるだけでは？(追記)A. そう
• リアルタイムプロセスがI/O待ち受けしてなかったら他のプロセスが何もできない？
  • => CPU１個だったらkill することもできない？(追記)A. そう