起床
I/Oやタイマーの完了でタスクが実行可能になると、runqueueへ追加されます。
02
実行可能なタスクをCPUへ割り当てる
プロセススケジューラ
LinuxのCPUスケジューラは、次に実行するタスクを選び、必要に応じて実行を中断し、複数のCPUへ処理を配置します。
スケジューラが扱う単位
プロセスとスレッドを、タスクとして扱う
Linuxカーネルは、プロセスプロセス実行中のプログラムを管理する単位。とプロセス内の各スレッドをタスクタスクLinuxカーネルがCPUへ割り当てる実行単位。として管理します。CPUスケジューラが直接選ぶ単位は、このタスクです。
CPUで動ける状態のタスクは実行可能実行可能CPUが空けば実行できる状態。です。各logical CPUのrunqueuerunqueue実行可能なタスクをCPUごとに管理する構造。で管理されます。ファイルやネットワークの応答を待つタスクは、イベントが届いて起床するとrunqueueへ戻ります。
1 logical CPUで同時に実行できるのは1タスク
複数のタスクが実行可能なら、スケジューラが選んだタスクだけがCPUを使います。CPUが複数ある場合は、各CPUで選択しながら、runqueue間の負荷も調整します。
選択
スケジューラコアはクラスの優先関係を確認し、選ばれたクラスの規則で次のタスクを決めます。
切り替え
タスクの待機、プリエンプションプリエンプション実行中のタスクを中断し、別のタスクへCPUを渡すこと。、時間配分の条件、yieldなどを契機に、別のタスクを選びます。
状態の交換
コンテキストスイッチコンテキストスイッチCPUで実行するタスクを入れ替える処理。でCPUレジスタなどを保存し、次のタスクの状態を復元します。
02.1
用途ごとに選択規則を分ける
スケジューリングクラス
Linuxは用途ごとに異なるスケジューリングクラスを持ちます。スケジューラコアはクラス間の優先関係を扱い、各クラスが自分の候補から次のタスクを選びます。
deadline
runtime、deadline、periodを指定し、時間制約と帯域を管理します。
リアルタイム
固定優先度を基準に選びます。SCHED_RRは同じ優先度のタスクへ時間を配分します。
fair
通常のアプリやサーバープロセスを扱います。公平なCPU配分と応答性を調整します。
02.2
通常のタスクをどう選んできたか
公平スケジューリングの世代交代
通常のタスクを選ぶ仕組みは、候補数の増加、対話的な処理の応答性、複数CPUでの拡張性に対応してきました。現在のEEVDFは、公平さの計算と要求された時間配分から仮想デッドラインを求めます。
代表的な選択処理記号は、各世代で次のタスクを選ぶ代表的な処理を示します。
CPU音楽
音楽
ブラウザ
ビルド
同期処理
選択中の方式
選択対象と仮想デッドラインで決める
選択対象になったタスクから、仮想デッドラインが最も早いものを選びます。
図では次のタスクを選ぶ考え方に絞っています。実装は優先度、CPU構成、省電力なども扱います。
コンテキストスイッチコンテキストスイッチCPUで実行するタスクを入れ替える処理。
CPUレジスタなどを保存し、次のタスクの状態を読み込みます。
仮想実行時間仮想実行時間各タスクがどれだけCPUを使ったか比べるための時計。
優先度を反映したCPU使用量です。CFSとEEVDFが計算に使います。
EEVDFEEVDFイー・イー・ブイ・ディー・エフ選択対象になったタスクから、仮想デッドラインが最も早いものを選ぶ方式。
選択対象と仮想デッドラインを使い、待ち時間と公平さを調整します。
期間方式主な構造選び方
〜2.4O(N)実行可能なタスクのリスト候補を順に調べる
2.6.0–2.6.22O(1)優先度別の配列とビットマップ一定の手順で優先度を探す
2.6.23–6.5CFS仮想実行時間を並べる赤黒木CPU使用量が少ない候補を選ぶ
6.6〜EEVDF選択対象と仮想デッドライン選択対象になったタスクから仮想デッドラインが最も早いものを選ぶ