OSにおけるCPUのスケジューリング機能は、複数のプロセスを「いかに効率的に」処理するかという目的のためにあります。OSの種類や目的によりスケジューリングアルゴリズムは異なり、OSによっては何種類かのスケジューリングアルゴリズムを搭載しています。
CPUのスケジューリングにおいて、すべての要件を満たす理想のアルゴリズムはありません。各要件は相反する条件を持っており、それら全てを満たすことはできないためです(一定の範囲で、制約付きながらなるべく満たすアルゴリズムの中から最適なものを選択することとなります)。
CPUスケジューリングに求められる要件としては、下記のようなものがあります。
- リソースの割り当てが公平であること
- CPUリソースを最大限プロセスのために使うこと
- より沢山のプロセスを処理できること
- プロセスの処理時間を最小限にすること
- プロセスの応答時間を最小限にすること
たとえば、プロセスの処理時間を最小化するためにはプロセスの実行時間を最大化する必要がありますが、それは全体的には実行待ちとなるプロセスの応答速度の低下に繋がってしまうというトレードオフの関係にあります(プロセスAの処理時間を最小にするためには、処理完了までプロセスAに対してCPUリソースを割り当て続けることが最適な選択となりますが、そうするとプロセスA以外の全てのプロセスについては応答待ちとしてしまうこととなるため)。
スケジューリングアルゴリズムとして最もシンプルな仕組みは、FIFO (First In First Out) です。投入されたプロセスを、投入された順に1つずつ処理していき、1つのプロセスの処理が終わったら次のプロセスの処理へ…と処理を進めていくやり方です。この方式の場合、要件の2, 4は満たしていますが、他の要件、特に3と5については仕組み的に対応できないアルゴリズムとなっています。
FIFOを発展させたスケジューリングアルゴリズムとしては、Round Robbin があります。プロセスの処理に「時間」という概念を追加し、各プロセスの処理に時間枠(タイムスライス)を設けます。これにより、FIFOの最大の問題点である「処理の長いプロセスが終わらないと全てのプロセスの処理が待たされる」という課題に対応することができます。プロセスは割り当てられたタイムスライス枠内で処理が終わらなかった場合には処理待ち行列(キュー)の一番後ろに並び直させることによって、特定のプロセスがCPUリソースを占有してしまうことを防止します。この方式により、FIFOでは対応することができなかった3と5の要件に対して、一定の対応ができますが、逆に2についてはプロセスを切り替える処理のためにある程度の犠牲を払うこととなり、4についてもタイムスライス内で処理できなかったプロセスはより長く待たされることとなります。
Round Robbinをさらに改良したスケジューリングアルゴリズムとしては、優先度スケジューリングがあります。実際にはすべてのプロセスが求める要件は異なり、大きく区分すると長期的にリソースを必要とするが即時性は求めていないタイプのプロセスと、即時性が求められるが比較的短時間の処理で終わるプロセスがあります。前者はCPUリソースを使った計算サイクルを必要とするプロセス、後者はI/O要求を求めるプロセスが主なものとなります。優先度スケジューリングは、そうした実体を踏まえて、プロセスに優先度を設定して複数のキューを用意、優先度別にプロセスを処理します。この方式の優れているところは、「あとから投入されたプロセスであっても、優先度が高ければ先に処理(割り込み)される」点です。また、優先度を必要に応じて調整することができるため、たとえば優先度が低くて待ち時間が長くなってしまったプロセスについては優先度を上げることで「いつまでも処理されない」問題に対応することができるなど、CPUスケジューリングに求められる要件すべてをベストではないにしろベターに満たすスケジューリングアルゴリズムといえます。Linux Kernel 2.6系で長いこと使われてきたO(1)スケジューラや、Kernel 2.6.32から実装されたCFS (Completely Fair Scheduler) は基本的には優先度スケジューリングアルゴリズムの一種といえます。
ではESXホストにおけるVMkernelが使用するスケジューリングアルゴリズムはどうなっているのでしょうか。
ESXでは優先度の代わりに比例比率に基づいた実行プロセス(ESXでは、仮想マシン毎にプロセス群をまとめて「ワールド」として扱います)の選定方式が採用されています。VMwareの資料では、Proportional Share-Based Algorithm (共有比例比率に基づくアルゴリズムとでも訳せばよいでしょうか…) と書かれていたりします。仮想化環境であるHyperviorにおけるCPUスケジューリングが難しい点は、リソース割り当ての対象が「自分自身がすべてのリソースを管理している」という前提で設計されているOS(正確には仮想マシンであってゲストOSではないのですが)であるということ、そしてさらに、ゲストOSに実装されているCPUスケジューリングアルゴリズムがさらにゲストOS上で実行されているプロセスに対するCPUスケジュールを行っているということです。ESXは各仮想マシン毎に用意されたVMM (Virtual Machine Monitor) 単位でCPUリソースの割り当てを管理しており、仮想マシンの中で実際にCPUリソースを必要としているプロセスがどれなのかというレベルまでは認識していません。そのため、特に仮想マシンに対してCPUリソースのシェア値が特に設定されていない場合は、それぞれの仮想マシンに構成された仮想CPU数に応じた比例比率が構成されます。
話をシンプルにするためにVMkernel自身の計算処理はないものと考えて2コア(HTとかはなし)環境があり、そこで1 vCPUの仮想マシンAと2 vCPUの仮想マシンBがパワーオン状態かつゲストOSとしてはCPU使用率100%状態となっているとします。この場合、仮想マシンAがCPUリソースを獲得できる可能性は1/3、仮想マシンBがCPUリソースを獲得できる可能性は2/3となります。ただし、仮想マシンBはvSMP構成のため、「同時に2つのCPUリソースを確保して計算サイクルを回す」必要があります。つまり、仮想マシンAが2つあるコアのうちのどちらかのコアを使って計算サイクルを実行している間は、もう一方のコアが空いていたとしても、仮想マシンBは計算サイクルを回すことはできません。そのため結果としては、2台ある仮想マシンは「CPUリソースを使用できる機会」としては均等ということになります。
実際には、ゲストOSのCPU使用率が100%という状態が続くなどということはないため、「多くのタイミングでは、仮想マシンはCPUリソースを必要としたタイミングで使用することができる」可能性は高いといえます。昨今CPUのマルチコア化が進み、1ソケット当たり8コアや10コアといったCPUも登場していますが、1台の物理ホスト上で合計すると物理コア数／HT使用の場合の論理CPU数以上のvCPUが仮想マシン前代分を足し合わせると割り当てられて動作しているという場合は多くあります。つまりメモリのオーバーコミットには注意を払っていても、CPUのいわばオーバーコミットは意外と普通にやってしまっている場合がかなりあります。それでもそれが問題とはならないのは、各仮想マシンのCPU使用率が平均すると10%であったり15%であったりなど、それほど高くはない場合が多いため、結果的にCPUリソースの割り当て待ちでパフォーマンスが劣化してしまう(待たされてしまう)ことはそれほど発生しないからといえます(発生するタイミングは必ずありますが、時間軸を加味して考えると、CPUリソースの割り当て待ちが発生している頻度は高くない)。
まだ概要レベルの話ですが、次第にもうちょっと入っていきたいと思います。
