Linuxカーネルのスケジューリング機能の最前線を知る（1/2 ページ）

先日行われた「Miracle Technology Day」では、大規模システムにおける従来のLinuxカーネルのスケジューリングの問題点と、それがLinuxカーネル2.6系でどう改善されているかについての解説が行われた。

[西尾泰三，ITmedia]

　Linuxの適用範囲がエンタープライズにも広まったことで、カーネルのスケジューリング機能も大規模システムに対応したものが求められている。7月6日にミラクル・リナックスが開催した「Miracle Technology Day」では、Linuxカーネルのスケジューリング機能に関して、リリースされたばかりの「MIRACLE LINUX V3.0 - Asianux Inside」の話を交えながら解説が行われた。壇上に立ったのは、ミラクル・リナックスコアテクノロジー部の五十嵐聖一氏。

カーネルのスケジューリング機能とは

　そもそも、カーネルのスケジューリング機能とは何のための機能なのだろうか？　カーネルのスケジューリング機能を簡単に言えば、タスク（プロセス、スレッド）をCPUに割り振るための機能であるといえる。

　マルチタスクOSでは、多くの実行可能プロセスから最も動作するにふさわしいプロセスを選び出すことが求められる。ここで、それぞれのタスクの相対的優先順位（nice）に応じ公平に実行権を割り当てることになるが、一部のプロセスだけが長時間実行権を握ることがないようにすることはもちろんのこと、CPUリソースやキャッシュ利用率など、効率的なリソース配分が求められる。

スケジューリングを左右するハードウェア構造

　スケジューリングを左右するハードウェア構造には「SMT」「SMP」「NUMA」などいくつかの種類がある。

　「SMT」（Simultaneous Multi Threading）は、単一のCPUを2つのCPUに見せ、マルチスレッドに対応したOSやアプリケーションなど、2つのアプリケーションのスレッドを同時に扱うことが可能なハードウェア構造。1つの物理CPUの中に実行ユニットとキャッシュを共有する形で論理CPU（siblings）を設ることで、スレッド・レベルの並列化（TLP）を実現し、プロセッサの実行リソースの利用効率を高めようとするインテルの「Hyper-Threading Technology」もSMTの一種であるといえる。

　SMTが論理CPUという方法で並列化を実現しているのに対し、「SMP」（Symmetric Multi Processors）は、物理CPUを対称的に配置し、全てのメインメモリが共有されるマルチプロセッサシステムで、全CPUが共有メモリに対して均等にアクセスする。この場合、メモリ、I/O、外部割り込みへのアクセス権は、全てのプロセッサに均等に割り振られることになる。これらはUMA（Uniform Memory Access）であるといえる。

　そして、大規模サーバなどで採用されることが多いNUMA（Non-Uniform Memory Access）。NUMAでは、UMA（Uniform Memory Access）領域がメインメモリに当たる。ローカルの一連のプロセッサとUMAをあわせたものが「ノード」と呼ばれる。

　NUMAはSMPと比較すると、それぞれのCPUからのメモリアクセス時間が均一でない構造となっている。多少強引に解釈するならば、SMP構成を複数つなげ、各SMP間でメモリアクセスを許したのがNUMAであるといえるかもしれない。

　各CPUはノードをまたいだメモリアクセスが可能だが、ノード間が高速なバスやスイッチで相互接続されているとはいえ、ノード内でのメモリアクセスよりも遅くなる。逆に言えば、ノード間でのデータ転送や通信を最小限にすれば、システム全体の性能向上を図ることができることになる。

　NUMAはCPU間のメモリアクセスの競合が比較的生じにくく、プロセッサ数の多い大規模なマルチプロセッサシステムに適しているといえる。

　上記のようなハードウェア構成が存在しているため、最適なパフォーマンスを発揮させるためには、スケジューリングの方法もそれに応じたものにする必要があるのだ。

従来のスケジューラの問題点

　従来のスケジューラの実装は、単一の線形リストからなるランキュー（runqueue_headから始まるリスト）に基づくものである。このランキュー上の各タスクに対してgoodness()関数を用い、最も高い返り値のタスクを選択・実行している。goodness()はタスクのcounterメンバやniceメンバの値から計算されている。

　タスクは一定時間（10ミリ秒）実効されるごとにcounterの値を減らし、全てのタスクのcounterの値が0になった時点で、schedule()関数が全タスクのcounterを再計算する、といった流れになっている。

　この問題点としては、ランキュー上にタスクが多く存在すると、goodness()関数の処理時間が増大してしまうことだ。また、CPUの数が多くなると、ランキューの絶え間ないロックが発生することになる。

　また、複数のCPUシステムの場合、CPUを移動することで、キャッシュが効率よく使えなかったりといった場合も生じる。特にNUMAでは、CPUが移動してしまうとメモリとの距離が離れてしまうことになるので、パフォーマンスに大きな影響が出かねない。

　そのほか、優先度の高いタスクがCPU間を非効率に行き来するいわゆる「ピンポン」現象が発生してしまうなど、従来のスケジューラは複数CPUシステムへの対応が不十分な部分があることは否めない。

MIRACLE LINUX V3.0のスケジューラ