基礎から覚える 最新OSのアーキテクチャー 第10回

AMD FX向けにパッチで修正 スケジューラーが抱える難題

Windows以外でのスレッドスケジューリングは？

　優先順位付きキューを使う方式では、スレッド数が多いと優先度の非常に低いスレッドが、実行されなくなってしまう可能性がある。Windowsではこれを監視して、一定時間(3秒といわれている)実行されなかったスレッドは、優先度を一時的に上げて実行させる仕組みがある。

　一方Unix系では、「多段フィードバックキュー」という方式が使われていた。これはキューを複数持つ方式である。新しく生成されたスレッドは、最上位のキューの最後尾に追加される。スケジューラーは最上位キューの先頭から実行可能なスレッドを探していき、最初に見つかった実行可能なスレッドを実行する。もし、スレッドがタイムスライスを使い切った場合、一段下のキューにおとされる。タイムスライスを使い切らずに、I/O待ちなどで実行を中断した場合には、実行が再開できるまでキューからは外されるが、実行可能になったときに同じキューに戻される。最下段はラウンドロビン方式になっており、すべてのスレッドが均等に実行される。

　このような仕組みにすることで、優先度の低いスレッドでも最初は最上段のキューに追加され、実行の機会を得る。しかし、タイムスライスをすべて使い切ってしまうような処理量の大きなスレッドであれば、だんだんと下位のキューに下がっていくわけだ。最下段はラウンドロビン方式なので、そこまで落ちれば確実に順番が回ってくる。

　逆に、I/O操作が多いスレッドの場合、タイムスライスを使い切ることがなく、同じレベルにとどまるため、常に一定の実行機会を得られる。またこうしたスレッドは、OS側から見ればタイムスライスを使い切らない「軽い」スレッドであり、他のスレッドが実行される機会を多く作るスレッドといえる。

　Unixに似ているといわれるLinuxだが、カーネル自体の実装は独自のものであり、スケジューリングアルゴリズムにも違いがある。現在のLinuxは、「O(1)スケジューラー」と呼ばれるものが使われている。これは2つの優先順位付きキューを使い、スケジューラー自身の実行時間が、スレッド数に影響されないようにしたものだ。“O(1)”とは、アルゴリズムの手順の数を表す「オーダー」が、対象の数によらず常に一定であることを表す記号である。

　スケジューリングアルゴリズムが面倒なのは、ハードウェアの進歩とともに、一定時間内に実行できるプログラムの量は増えたものの、システムの巨大化などにより同時実行されるスレッド数や、それらが利用するリソース量も増えていくことにある。Linuxはカーネル2.6で、このO(1)スケジューラーに切り替えた。今後増大するだろうスレッド数の増加により、スケジューラーの実行比率が高くならないようにしたわけだ。

　O(1)スケジューラーは、2つある優先順位付きキューの片方(activeキュー)を使い、次に実行するスレッドを選択する。スレッドが割り当てられたタイムスライスを使い果たしたら、もう一方のキュー(expiredキュー)へと登録される。これを続けていくと、最後にはactiveキューのスレッドはなくなってしまう。そこでactiveキューとexpiredキューを逆にして、expiredキューをactiveキューとして扱うようにする。

　マルチプロセッサーの場合には、プロセッサーごとに2つのキューを用意し、基本的にスレッドは同一のプロセッサーで実行されるようにする。ただしこの場合、長い時間で見るとプロセッサー間でスレッド数の偏りが出てしまうため、これを監視して調整している。