プロセススケジューラを知る――プロセススケジューリング（その3）：UNIX USER 2004年6月号「Linuxカーネル2.6解読室」より転載（2/2 ページ）

[高橋浩和（VA Linux Systems Japan），UNIX USER]

リアルタイムプロセス

　Linuxのプロセススケジューリングは、すべてのプロセスを公平に扱うことを方針としています。しかし、実時間処理を行いたい場合、この公平性が逆にあだとなります。音声や画像に関する記録/再生処理や、機器制御を行う場合、ある時間以内に目的の処理を完了させる必要があります。しかし、スケジューリングの公平性を重視したプロセススケジューリング方式では、いつプロセスが実行権を得て、いつ目的の処理が完了するかを予測できません。

　そこでLinuxカーネルは、このような用途のためにリアルタイムプロセス機能を提供しています。リアルタイムプロセスは、通常のプロセスより高い実行優先度を持ち、優先的にスケジューリングされます。通常のプロセスは時間とともに変動優先度が下げられ、また実行割り当て時間も減らされていきますが、リアルタイムプロセスは特別扱いされ、勝手に優先度を下げられることはなく、また実行割り当て時間も無制限です。

　実行中のリアルタイムプロセスに対してプロセス切り替えが発生※するのは、自ら実行権を放棄したときか、より高い実行優先度のリアルタイムプロセスが実行可能となり、プリエンプションが発生したときです。

マルチプロセッサシステムにおけるプロセススケジューリング

　対称型マルチプロセッサ（SMP）システム※において、最も適切なプロセススケジューリングはどのようなものでしょうか？　実行可能なプロセスのうち、最も実行優先度の高いものからCPUと同じ数のプロセスを選択し、実行権を与えることが最も優れたスケジューリングでしょうか？

　あるCPU上でプロセスが起床した場合、そのCPU上では実行権が得られなくとも、ほかのCPU上ではすぐに実行可能かもしれません。ほかのCPUがアイドル状態であったり、動作しているプロセスの実行優先度が低かったりする場合もあり得ます。

　実際には、実行優先度の逆転が起きても、プロセスがCPU間を移動しないように抑制したほうが、処理効率は良くなります。あるプロセスがあるCPU上で一度動作した場合、次回動作する場合も同じCPU上で動作させるべきです。これは、一度あるCPU上でプロセスが動作すると、そのプロセスが利用した実メモリの内容がキャッシュメモリに蓄えられているからです。次にこのプロセスが再スケジューリングされるときは、このキャッシュメモリを有効に利用できるように同じCPUに割り付けるようにします。キャッシュメモリの大容量化に加え、実メモリとキャッシュメモリの速度差は大きくなる傾向にあるので、キャッシュメモリをどれだけ有効利用できるかが、性能を高める鍵となっています（図5）。

図5 プロセスとキャッシュの関係（クリックで拡大します）

　また、TLB（Translation Lookaside Buffer:アドレス変換バッファ）の利用効率※もあります。TLBは、仮想アドレスから物理アドレスへの変換を高速化するためのキャッシュです。CPUはアドレス変換を行うために、一度ページテーブルなどのメモリ上に置かれたデータ構造をたどり、実アドレスを求めます。しかし、メモリアクセスの度にこのデータ構造を参照することは非常にオーバーヘッドが大きくなるため、最近利用されたアドレス変換情報をTLBと呼ばれる領域にキャッシュしておきます。つまりプロセス空間に対するTLB情報を有効に利用するためには、プロセスを再スケジューリングするときに、やはり同じCPU上で動作させたほうが有利であることが分かります。

　Linuxカーネル2.6のプロセススケジューラは、各CPU上でそれぞれ独立して動作しており、それぞれのCPUで動作するのに最も適したプロセスを選択します。プロセスはどこかのCPUにくくり付けるようになっていて、CPU間の負荷バランスが大きく崩れたときのみ、プロセスを別のCPU上で再スケジューリングします。

　CPUごとに用意されたプロセススケジューラが、それぞれのCPUに属するプロセス群を管理するようにさせると、もう1つ別のメリットも生まれます。プロセススケジューラどうしが、互いに同じデータ構造を操作することによる競合発生がなくなり、性能向上に貢献します。

ハイパースレッディング

　ハイパースレッディングは、Intel Xeonプロセッサから導入された新しい技術で、最近のPentium 4も利用できます。CPU内部の演算器は、メモリアクセスなど遅延が発生する処理を実行すると遊んでしまいます（ストールしてしまいます）。ハイパースレッディングは、この遊んでいる演算器を有効に利用するために導入されました（図6）。

図6 ハイパースレッディング（クリックで拡大します）

　Xeonプロセッサでは、演算器1つにレジスタセット2組※を持っています。一方のレジスタセットを利用して動作している命令コード列がメモリアクセスのためにストールした場合、もう一方のレジスタセットで別の命令コード列の実行を行います。OSから見た場合、2つの仮想的なCPUが存在するように見えます。マルチプロセッサ対応のOSであれば、ほぼ変更なくこの2つの仮想CPUを利用して動作できます。

　Linuxカーネル2.6のプロセススケジューラは、とくにハイパースレッディングを意識することなく、通常のSMPと同様のスケジューリング処理※を行っています。

NUMA

　SMPシステムでは、スケーラビリティに限界があります。すべてのCPUが等価にバスやメモリを共有しているため、それらへのアクセスがネックとなります。そこで、対称型であることを捨てる代わりに、多プロセッサ構成時の性能メリットを得る仕組みとして、NUMA（Non-Uniformed Memory Architecture）が採用される※ケースが増えてきています。NUMAを採用したシステムでは、SMPマシンを1つのノードとし、複数のノードを高速スイッチで相互接続したような構造をしています（図7）。

図7 NUMAシステムにおける負荷バランス（クリックで拡大します）

　あるCPUから見た場合、同じノード内のメモリアクセスの速度と比較し、ほかのノード上にあるメモリへのアクセスには遅延が生じます。Linuxカーネルはこのことを強く意識してプロセスをスケジューリングします。各プロセスは特定のノードに縛り付け、ほかのノードへの移動を禁止します。そのプロセスは、必要なメモリはそのノード上から確保します。SMPで負荷に偏りができたときには、プロセスをほかのCPUへ移動させることによって負荷バランスを取ってきました。NUMAではノード間を越えてのプロセス移動はできません。実行性能の劣化が大きいためです。

　しかし、ノード間でまったく負荷バランスを取ることができないわけではなく、exec処理のタイミングで最も負荷の低いノードにプロセスを移動させます。exec処理は、プロセスが利用していたメモリを一度捨てて再確保するため、プロセス移動の非常に良い機会です。

---

　次回はプロセススケジューラの実装について解説していく。

このページで出てきた専門用語

リアルタイムプロセスに対してプロセス切り替えが発生 正確には、ラウンドロビン型のリアルタイムプロセスを選択した場合、同じ実行優先度のリアルタイムプロセス間で、一定時間ごとに実行権を譲り合う。 対称型マルチプロセッサ（SMP）システム 1台のコンピュータに複数のプロセッサ（CPU）を搭載しているシステム。複数のプロセッサを同等に接続する回路で構成され、それぞれのCPUが同等な立場で処理を分担する。 TLBの利用効率 この辺りの話は、空間管理の回にもう少し詳しく説明する予定。x86アーキテクチャではTLBは問題にならないが、ほかのアーキテクチャでは問題になる。 演算器1つにレジスタセット2組 ハイパースレッディングの実装には将来、さまざまな数の組み合わせのCPUが出てくる可能性がある。 通常のSMPと同様のスケジューリング処理 物理CPUも意識した負荷バランスを取るアイデアもあるが、Linuxカーネル2.6のコードには取り込まれていない。一方、Linuxカーネル2.4では、2つの仮想CPUがともにアイドルである物理CPUに優先して、プロセスを割り付けるようになっている。 NUMAが採用される Linuxでは、各ノード間のキャッシュメモリの整合性が自動的に行われるccNUMAと呼ばれる方式を前提としている。

最新号：UNIX USER 7月号の内容 第1特集 無線LANの構造と認証強化 第2特集 UNIX/LinuxからWindowsリソースを使うには？ ［特別企画］ ・新世代Very Secure FTPDを使いこなせ ・Fedora Core 2導入ガイド