Linuxのプロセススケジューリング

ここで説明するキューや時間配分は、プロセススケジューラーの考え方を理解するための簡略化したモデルです。実際のLinuxカーネルでは、バージョンやスケジューリングクラスによって実装の詳細が異なります。

00:00 — プロセススケジューリングの基本
#

プロセススケジューリングの目的は、複数のプロセスへCPU時間を合理的に配分することです。プロセスが自発的にCPUを返すだけでは、無限ループに入ったプロセスやCPUを長時間使い続けるプロセスによって、他のプロセスが実行できなくなる可能性があります。

そこでOSはタイマー割り込みを利用します。一定時間が経過すると割り込みが発生し、カーネルは実行中のプロセスを切り替えます。これがプリエンプティブスケジューリングの基本です。

プロセスの状態は、概念的には次のように管理されます。

たとえば5つのプロセスがあり、スケジューラーが一定間隔で切り替えるとします。プロセスAがI/O待ちになった場合、Aを待ちキューへ移し、別の実行可能なプロセスを選べば、CPUを無駄に待機させずに済みます。

プロセス数が数百、数千に増えると、各プロセスへ短い時間だけCPUを割り当てる方式は、切り替えのコストを無視できなくなります。

コンテキストスイッチでは、レジスター、スタック、アドレス空間などの実行状態を保存し、次のプロセスの状態を読み戻します。たとえば、各プロセスの実行時間が10msで切り替え自体に1msかかるなら、CPU時間の一部が切り替えだけで消費されます。

時間片を短くすれば応答性は上がりますが、コンテキストスイッチは増えます。逆に時間片を長くすれば効率は上がりやすい一方、対話的な処理の応答が遅くなります。スケジューラーはこのトレードオフを調整します。

教材では、実行可能なプロセスをactiveキューとexpiredキューに分けるモデルを使うことがあります。

activeキューが空になると、2つのキューを交換します。こうすると、同じプロセスだけがCPUを占有し続けることを防ぎ、待っているプロセスにも実行機会を与えられます。

たとえば、次のような状態を考えます。

active  : [A, B, C]
expired : [D, E]

A、B、Cの時間片が尽きてactiveキューが空になると、キューを交換し、DとEを実行対象にします。これはスケジューラーの公平性を説明するためのモデルであり、現行Linuxの内部実装をそのまま表したものではありません。

優先度を使うスケジューラーでは、プロセスごとにCPUの配分を変えます。単純なモデルでは、高い優先度のプロセスへ短い時間片を頻繁に割り当てたり、優先度に応じて異なる重みを設定したりします。

しかし、優先度が1段階違うだけでCPU時間が大きく変化すると、公平性が損なわれる可能性があります。そのため、実際のスケジューラーでは、優先度、重み、待ち時間、実行済み時間、対話性などを組み合わせて判断します。

重み付きスケジューリングでは、各プロセスの重みに応じてCPU時間を配分します。たとえば、Aの重みが1、Bの重みが2なら、理想的にはBがAの約2倍のCPU時間を得ます。

ただし、実際の実行ではI/O待ち、スリープ、最低時間片、優先度、CPUコア数なども影響します。時間片をすべて使わずにブロックしたプロセスは、後で早く選ばれる場合があります。重みだけを掛け算すれば常に同じCPU時間になるわけではありません。

公平性を説明する代表的な考え方が、仮想実行時間（virtual runtime）です。各プロセスが実際に消費したCPU時間を、重みなどに応じて補正して記録します。仮想実行時間が小さいプロセスを優先すれば、長く待っているプロセスへCPUを戻せます。

このような候補を効率よく選ぶために、スケジューラーが木構造などのデータ構造を使うことがあります。典型的な説明では、仮想実行時間の小さいプロセスを素早く見つけられるように、最小値を先頭付近に保持します。

Linuxのスケジューリング実装は、カーネルのバージョンやスケジューリングクラスによって変化します。O(1)スケジューラー、CFS、より新しいスケジューラーを同一視せず、ここでは「公平にCPUを分配するための考え方」として理解してください。