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

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

スレッドの順序を決める
スケジューリングアルゴリズム

　前回で解説したように、スケジューリングでは次に実行すべきスレッドを選択するために、多くの条件を調べなければならない。すぐにでも実行可能なスレッドがあったとしても、スレッドにはそれぞれ優先度があり、優先度の高いものから実行する必要がある。しかし優先度だけを見ていると、優先度の低いスレッドは、いつまでも実行されなくなってしまうという話だった。

　ここで登場するのが「スケジューリングアルゴリズム」だ。簡単に言えばスケジューリングアルゴリズムとは、「次に実行すべきスレッドを選択するための手順」である。

　最も簡単なスケジューリングアルゴリズムは、「ラウンドロビン」と呼ばれる方法だ(図1)。これはすべてのスレッドを円環状に並べて、順番に実行していく方法だ。時計の針が文字盤のすべての数字をさすように、スレッドを順番に実行していく。このようにしておくと、すべてのスレッドに実行される機会が与えられる。

図1 ラウンドロビン方式でのスレッドスケジューリングの仕組み。すべてのスレッドが順番に実行されていく

　しかし、優先度など複雑な制御を入れたり、「仮想メモリーでスワップアウトされているかどうか」を考慮する、あるいは複数のプロセッサーとそれぞれに接続された物理メモリー(NUMA、Non Uniform Memory Access)の関係を考慮したりするなど、スレッドの選択条件が複雑になってくると、このやり方では対応できなくなる。

優先度の高いスレッドを割り込みで
処理させる「優先順位付きキュー」

　もうひとつの方法が「キュー」と呼ばれる仕組みを使う方法だ(図2)。キューとは、筒の一方から球を入れ、もう一方から取り出すような仕組みである。最初に入れたもの(First In)が最初に出る(First Out)であるため「FIFO」とも呼ぶ。

図2 キューの概念。入れた順に出てくるシンプルな仕組み

　OSのスケジューリングアルゴリズムでキューを使う場合は、優先度などの仕組みを実現するために、少し変形して利用する。スレッドはキューに入れられると、実行を待つ状態になる。キューの先頭にあるスレッドは、取り出されたら実行され、タイムスライス(割り当てられたCPU時間)を使い果たすと、OSに制御が戻ったときにキューに戻される。

　スレッドをキューに戻す際に、優先度が高いものはキューの前方に「割り込む」ようにすると、優先度の高いスレッドの実行が優先されるようになる。これを「優先順位付きキュー」(図3)などと呼ぶことがある。

図3 優先順位付きキューの概念。優先度の高い「3」や「2」は、キューの途中に割り込みで入れられるので、先に処理されるという仕組み

　具体的な実装としては「スロット付きキュー」といった方法もあるが、ここでは実装方法に関わらず、優先順位を考慮したキューを一括して優先順位付きキューと呼ぶことにする。ただし、同じ優先順位付きキューであっても、実装方法により効率は異なる。キューにスレッドを追加しようとしたとき、優先順位やキューに入った順番を考慮して、スレッドを挿入する場所を探さねばならないからだ。