=== 1.5 プロセススケジューラ プロセスディスパッチャは、指定されたプロセスに実行権を与える、つまりCPUを割り当てる処理を行いまし た。しかし、どのプロセスに実行権を与えるかの判断は行いません。 実行可能なプロセス群全体を監視し、どのプロセスに実行権を与えるか判断を下すのはプロセススケジューラ です（図1-3）。プロセススケジューラは、いつどのプロセスに実行権を与えるかを決断し、プロセスディスパッ チャに切り替え要求を出します。 [[Thumb(fig1-3.png, size=256x357, caption=図1-3 プロセススケジューラ)]] では、プロセススケジューラはどのような方針に基づいて、いつ、どのプロセスに実行権を与えるべきだと判 断するのでしょうか？ ==== 1.5.1 スケジューリングの方針 プロセススケジューラの役目は、多くの実行可能プロセスから最も動作するにふさわしいプロセスを選び出す ことです。Linuxカーネルのプロセススケジューラは、応答性能とスループットという、互いに矛盾する要求に 対応できることを方針として設計されています。シェルプログラムのような対話型プロセスには応答性を保証し、 数値計算プログラムを実行するプロセスにはスループットを保証する必要があります。また、多くのプロセスが 同時に動作する環境でも、必ずすべてのプロセスに実行権が割り当てられる保証をする必要があります。 ===== 1.5.1.1 対話型プロセスの応答性能向上 システム利用者の体感速度を上げるために、対話型プロセスが動作を始めたときは、即座にプロセス切り替え を行い優先的に動作させます。逆にバッチ型プロセスは、その必要がないため、対話型プロセスに実行権を譲り ます。とはいってもカーネルからプロセスの種類を区別できないので、Linuxカーネルでは、単位時間当たりの 実行時間が少ないプロセスは対話型のプロセスであろうという仮定を行い、スケジューリングします[[(footnote(ほとんどの場合は期待どおりにいきますが、この仮定がうまく成り立たないXサーバーのような例もあります。)]]。 ===== 1.5.1.2 優先度の指標 各プロセスは実行優先度として、niceコマンドで指定する固定優先度のほかに変動優先度を持ちます（図1-4）。 Linuxカーネルは時間経過とともにプロセスの変動優先度を変更し、固定優先度と変動優先度の合計が最も大き なプロセスに実行権を与えます。より多くCPUを利用したプロセスほど、低い変動優先度を持つようになり、シ ェルのような対話型プロセスはあまりCPUを利用しないため、相対的に高い変動優先度が割り当てられることに なります。 また、Linuxカーネルのプロセススケジューラは、プロセス動作の統計を基にし、対話型プロセスのような動 作をするプロセスに対して、特別に実行優先度を高めるような仕掛けも入っています。 たとえば、あるプロセスAが走行中に、対話型プロセスBが実行可能になったとしましょう。プロセススケジュ ーラは、対話型プロセスBのほうがプロセスAより実行優先度が高いことを認識すると、プロセスディスパッチャ を呼び出し、プロセスを切り替えます。この実行中のプロセスから実行権を奪い取ることを「プリエンプトする」 といい、その処理は「プリエンプション」と呼びます。プロセススケジューラは、新しいプロセスが実行可能状態 になるたびに、プリエンプトする必要があるか否かを判断します。この機能により、応答性を確保しています。 [[Thumb(fig1-4.png, size=374x224, caption=図1-4 実行優先度)]] ===== 1.5.1.3 実行保証 また、プロセスのスケジューリングは、公平性を保つことにも配慮されています。すべてのプロセスは、時分 割で動作します。一部のプロセスだけが長時間実行権を握ってしまい、スケジューリング対象から漏れてしまう プロセスが発生しないように、すべてのプロセスへ公平に実行権を与えます。 具体的には、実行可能状態になったプロセスに実行割り当て時間（タイムスライス）を与えます。実行権を与 えられたプロセスは、そのプロセスの実行割り当て時間が残っている間は、実行権を持ち続けることができます。 実行割り当て時間を使い切ったプロセスは、ほかのプロセスに実行権を明け渡さなければなりません。一度実行 割り当て時間を使い果たしたプロセスは、再度実行割り当て時間を割り当てられるまでスケジューリングの対象 にはなりません。新たに実行割り当て時間が与えられるのは、Linuxカーネル上に実行割り当て時間が残ってい る実行待ちプロセスが1つもいなくなったときです[[(footnote(例外的に、対話型と判断したプロセスに対しては、即座に持ち時間を与えることがあります。)]]。この仕組みによって、どんなに実行優先度の低いプロセ スであっても、必ずCPU上での実行権が回ってくることが保証されています。 この実行割り当て時間の長さは固定優先度を基に計算します。高い固定優先度を持つプロセスほど長めの実行 割り当て時間が与えられ、ほかのプロセスに比べて実行権を握ることのできる機会が増します。 実行割り当て時間は、Linuxカーネルの時計（「第4章 時計」参照）から、周期的に監視します（scheduler_tick 関数）。時計処理の中で実行中プロセスの実行割り当て時間を減らしていき、実行割り当て時間がなくなったと ころでプロセススケジューラに再スケジューリング要求を出します。 ===== 1.5.1.4 カウンタ方式によるスループットの向上 Linuxカーネルのこれらの仕組みは、スループットの点でも有利です。 伝統UNIXでも同様の方針でプロセススケジューリングが行われていましたが、古いUNIXの実装では、時計 から実行中プロセスの変動優先度を再計算していました。そのため、プロセスの実行中に実行優先度が下がり、 簡単に実行待ち状態にあるほかのプロセスの実行優先度を下回ってしまいます。そして、この下がった瞬間に再 スケジューリング要求が発生し、プロセス切り替えが行われていました。 それに比べLinuxの実装方式では、一度実行権を握ったプロセスは一定時間継続して実行できるため、プロセ スの再スケジューリングの回数を最小限に抑え込むことができます。 ==== 1.5.2 スケジューリング契機 すでにいくつか見てきましたが、どのようなときにプロセススケジューラが動作するのでしょうか？ 現在実行中のプロセスが、自ら実行権を手放したときは、当然プロセススケジューラが動作します。具体的に は2つの場合があり、1つは、ある事象が成立することを待ち合わせるために、待機状態に遷移したときです。実 行権を手放したプロセスは実行可能状態ではなくなるため、残りの実行待ちプロセス群の中から最も実行優先度 の高いプロセスを探し出し、実行権を与えます。もう1つは、明示的にほかのプロセスに実行権を譲る場合です。 非常に長いカーネル処理を実行するときなど、応答性に悪影響を与えないように自ら実行権を譲ることができま す。この場合、このプロセスは実行待ち状態になり、次回のスケジューリングのときに再度実行権を得るかもし れません。 これらのように実行中プロセスの意思で実行権を渡すのではなく、実行中プロセスから実行権を奪い取ること もできます。先ほども説明したプリエンプションと呼ばれているものです。新しいプロセスが実行待ち状態のプ ロセス群に加わったとき、その新しいプロセスが現在実行中のプロセスより実行優先度が高いことが分かると、 プロセススケジューラに対して再スケジューリング要求を出します（resched_task関数）。プロセススケジューラ はこの要求に応答して、最も高い実行優先度を持つプロセスを選択し、プロセス切り替えを行います。たいてい の場合、いま実行待ち状態のプロセス群に加わった新しいプロセスが選択されます。 また、先ほども述べたように、プロセスが実行割り当て時間を使い果たした場合も、Linuxカーネルは強制的 に実行権を取り上げ、プロセススケジューラに再スケジューリング要求を出します。プロセスが自主的に実行権 を手放したときは、即座にプロセススケジューラが起動し、ほかのプロセスに切り替えますが、実行権を強制的 に奪い取る場合は、再スケジューリング要求を出した瞬間にプロセススケジューラが動作するとは限りません。 実際にプロセスケジューラが動作するのは、Linuxカーネルが行うべき処理（システムコール処理や割り込み処 理）が完了するまで遅延させられます。 もともとは、Linuxカーネルのコードが複雑にならないように、Linuxカーネル内の任意の個所でプロセス切り 替えをすることを禁止していました。しかし、Linuxカーネル2.6では応答性を向上させるため、少しオーバーヘ ッドは大きくなりますが、Linuxカーネルコード実行中のプリエンプションを許す設定も可能となっています（割 り込み処理、遅延処理、排他区間実行中は除く）[[footnote(固定プリエンプションポイント方式も撰択できます。スケジューリング処理のオーバーヘッドを抑えつつ、応答性も確保しようとする試みです。カーネル内にプリエンプション可能個所を明示的に埋め込み1つのプロセスが長時間カーネルコードを実行し続けることがないようにします。SVR 4.0などでも採用されていた方式です。)]]。 ==== 1.5.3 リアルタイムプロセス Linuxのプロセススケジューリングは、すべてのプロセスを公平に扱うことを方針としています。しかし、実 時間処理を行いたい場合、この公平性が逆にあだとなります。音声や画像に関する記録/再生処理や、機器制御 を行う場合、ある時間以内に目的の処理を完了させる必要があります。しかし、スケジューリングの公平性を重 視したプロセススケジューリング方式では、いつプロセスが実行権を得て、いつ目的の処理が完了するかを予測 できません。 そこでLinuxカーネルは、このような用途のためにリアルタイムプロセス機能を提供しています。リアルタイ ムプロセスは、通常のプロセスより高い実行優先度を持ち、優先的にスケジューリングされます。通常のプロセ スは時間とともに変動優先度が下げられ、また実行割り当て時間も減らされていきますが、リアルタイムプロセ スは特別扱いされ、勝手に優先度を下げられることはなく、また実行割り当て時間も無制限です。 実行中のリアルタイムプロセスに対してプロセス切り替えが発生するのは、自ら実行権を放棄したときか、よ り高い実行優先度のリアルタイムプロセスが実行可能となり、プリエンプションが発生したときです。 1.5.4 マルチプロセッサシステムにおけるプロセススケジューリング 対称型マルチプロセッサ（SMP）システムにおいて、最も適切なプロセススケジューリングはどのようなもの でしょうか？ 実行可能なプロセスのうち、最も実行優先度の高いものからCPUと同じ数のプロセスを選択し、 実行権を与えることが最も優れたスケジューリングでしょうか？ あるCPU上でプロセスが起床した場合、そのCPU上では実行権が得られなくとも、ほかのCPU上ではすぐに実 行可能かもしれません。ほかのCPUがアイドル状態であったり、動作しているプロセスの実行優先度が低かった りする場合もあり得ます。 実際には、実行優先度の逆転が起きても、プロセスがCPU間を移動しないように抑制したほうが、処理効率 は良くなります。あるプロセスがあるCPU上で一度動作した場合、次回動作する場合も同じCPU上で動作させ るべきです。これは、一度あるCPU上でプロセスが動作すると、そのプロセスが利用した実メモリの内容がキャ ッシュメモリに蓄えられているからです。次にこのプロセスが再スケジューリングされるときは、このキャッシ ュメモリを有効に利用できるように同じCPUに割り付けるようにします。キャッシュメモリの大容量化に加え、 実メモリとキャッシュメモリの速度差は大きくなる傾向にあるので、キャッシュメモリをどれだけ有効利用でき るかが、性能を高める鍵となっています（図1-5）。 また、TLB（Translation Lookaside Buffer:アドレス変換バッファ）の利用効率もあります。TLBは、仮想アド レスから物理アドレスへの変換を高速化するためのキャッシュです。CPUはアドレス変換を行うために、一度ペ ージテーブルなどのメモリ上に置かれたデータ構造をたどり、実アドレスを求めます（「第9章アドレス変換機 構」参照）。しかし、メモリアクセスの度にこのデータ構造を参照することは非常にオーバーヘッドが大きくなる ため、最近利用されたアドレス変換情報をTLBと呼ばれる領域にキャッシュしておきます。つまりプロセス空間 に対するTLB情報を有効に利用するためには、プロセスを再スケジューリングするときに、やはり同じCPU上で 動作させたほうが有利であることが分かります。 Linuxカーネル2.6のプロセススケジューラは、各CPU上でそれぞれ独立して動作しており、それぞれのCPUで 動作するのに最も適したプロセスを選択します。プロセスはどこかのCPUにくくり付けるようになっていて、 CPU間の負荷バランスが大きく崩れたときのみ、プロセスを別のCPU上で再スケジューリングします。 CPUごとに用意されたプロセススケジューラが、それぞれのCPUに属するプロセス群を管理するようにさせる と、もう1つ別のメリットも生まれます。プロセススケジューラどうしが、互いに同じデータ構造を操作するこ とによる競合発生がなくなり、性能向上に貢献します。 [[Thumb(fig1-5.png, size=546x267, caption=図1-5 プロセスとキャッシュの関係)]] [[Thumb(fig1-6.png, size=149x240, caption=図1-6 ハイパースレッディング)]] ===== 1.5.4.1 ハイパースレッディング ハイパースレッディングは、Intel Xeonプロセッサから導入された新しい技術で、最近のPentium 4も利用で きます。CPU内部の演算器は、メモリアクセスなど遅延が発生する処理を実行すると遊んでしまいます（ストー ルしてしまいます）。ハイパースレッディングは、この遊んでいる演算器を有効に利用するために導入されまし た（図1-6）。 Xeonプロセッサでは、演算器1つにレジスタセット2組を持っています。一方のレジスタセットを利用して動 作している命令コード列がメモリアクセスのためにストールした場合、もう一方のレジスタセットで別の命令コ ード列の実行を行います。OSから見た場合、2つの仮想的なCPUが存在するように見えます。マルチプロセッサ 対応のOSであれば、ほぼ変更なくこの2つの仮想CPUを利用して動作できます。 Linuxカーネル2.6のプロセススケジューラは、原則としてハイパースレッディングを意識することなく、通常 のSMPと同様のスケジューリング処理を行っています[[footnote(一方のレジスタセットに、非常に優先度の高いプロセスを割り当てた場合、もう一方のレジスタセットにはプロセスを割り当てないことがあります。)]]。 ===== 1.5.4.2 NUMA SMPシステムでは、スケーラビリティに限界があります。すべてのCPUが等価にバスやメモリを共有している ため、それらへのアクセスがネックとなります。そこで、対称型であることを捨てる代わりに、多プロセッサ構 成時の性能メリットを得る仕組みとして、NUMA（Non-Uniformed Memory Architecture）が採用されるケース が増えてきています。NUMAを採用したシステムでは、SMPマシンを1つのノードとし、複数のノードを高速ス イッチで相互接続したような構造をしています（図1-7）。 あるCPUから見た場合、同じノード内のメモリアクセスの速度と比較し、ほかのノード上にあるメモリへのア クセスには遅延が生じます。Linuxカーネルはこのことを強く意識してプロセスをスケジューリングします。各 プロセスは特定のノードに縛り付け、ほかのノードへの移動を禁止します。そのプロセスは、必要なメモリはそ のノード上から確保します。SMPで負荷に偏りができたときには、プロセスをほかのCPUへ移動させることによ って負荷バランスを取ってきました。NUMAではノード間を超えてのプロセス移動はできません。実行性能の 劣化が大きいためです。 しかし、ノード間でまったく負荷バランスを取ることができないわけではなく、exec処理のタイミングで最も 負荷の低いノードにプロセスを移動させます。exec処理は、プロセスが利用していたメモリを一度捨てて再確保 するため、プロセス移動の非常に良い機会です。
Linux Kernel Documents
Fork
edit