スレッドの順序を決める
スケジューリングアルゴリズム
前回で解説したように、スケジューリングでは次に実行すべきスレッドを選択するために、多くの条件を調べなければならない。すぐにでも実行可能なスレッドがあったとしても、スレッドにはそれぞれ優先度があり、優先度の高いものから実行する必要がある。しかし優先度だけを見ていると、優先度の低いスレッドは、いつまでも実行されなくなってしまうという話だった。
ここで登場するのが「スケジューリングアルゴリズム」だ。簡単に言えばスケジューリングアルゴリズムとは、「次に実行すべきスレッドを選択するための手順」である。
最も簡単なスケジューリングアルゴリズムは、「ラウンドロビン」と呼ばれる方法だ(図1)。これはすべてのスレッドを円環状に並べて、順番に実行していく方法だ。時計の針が文字盤のすべての数字をさすように、スレッドを順番に実行していく。このようにしておくと、すべてのスレッドに実行される機会が与えられる。
しかし、優先度など複雑な制御を入れたり、「仮想メモリーでスワップアウトされているかどうか」を考慮する、あるいは複数のプロセッサーとそれぞれに接続された物理メモリー(NUMA、Non Uniform Memory Access)の関係を考慮したりするなど、スレッドの選択条件が複雑になってくると、このやり方では対応できなくなる。
優先度の高いスレッドを割り込みで
処理させる「優先順位付きキュー」
もうひとつの方法が「キュー」と呼ばれる仕組みを使う方法だ(図2)。キューとは、筒の一方から球を入れ、もう一方から取り出すような仕組みである。最初に入れたもの(First In)が最初に出る(First Out)であるため「FIFO」とも呼ぶ。
OSのスケジューリングアルゴリズムでキューを使う場合は、優先度などの仕組みを実現するために、少し変形して利用する。スレッドはキューに入れられると、実行を待つ状態になる。キューの先頭にあるスレッドは、取り出されたら実行され、タイムスライス(割り当てられたCPU時間)を使い果たすと、OSに制御が戻ったときにキューに戻される。
スレッドをキューに戻す際に、優先度が高いものはキューの前方に「割り込む」ようにすると、優先度の高いスレッドの実行が優先されるようになる。これを「優先順位付きキュー」(図3)などと呼ぶことがある。
具体的な実装としては「スロット付きキュー」といった方法もあるが、ここでは実装方法に関わらず、優先順位を考慮したキューを一括して優先順位付きキューと呼ぶことにする。ただし、同じ優先順位付きキューであっても、実装方法により効率は異なる。キューにスレッドを追加しようとしたとき、優先順位やキューに入った順番を考慮して、スレッドを挿入する場所を探さねばならないからだ。

この連載の記事
-
第13回
PC
ARM版Windows 8実現の布石となったWindows 7の「MinWin」 -
第12回
PC
アプリがWindowsの機能を使うには? APIとDLLの仕組み -
第11回
PC
マルチコアCPUの消費電力はスケジューリングで変わる? -
第9回
PC
マルチコアCPUを賢く使いこなす スケジューリングの秘密 -
第8回
PC
意味の違いがわかる? タスクとプロセスとスレッド -
第7回
PC
Windowsのメモリー管理をx86の仕組みから読み解く -
第6回
PC
メモリー不足を根本的に解決する64bit OSの仕組み -
第5回
PC
Windows 8でMetro Styleアプリを動かす「WinRT」 -
第4回
PC
Windowsを動かすデバイスドライバーの仕組み 前編 -
第3回
PC
OSの仕事はハードウェアをアプリから「隠す」こと? - この連載の一覧へ