Linux Kernel Documents
Fork
edit[[PageNavi(NavigationList)]]
=== 1.5 プロセススケジューラ
{{{ html
<a name="fig1-3"></a>
}}}
[[Thumb(fig1-3.png, size=256x357, caption=図1-3 プロセススケジューラ, float=right)]]
プロセスディスパッチャは、指定されたプロセスに実行権を与える、つまりCPUを割り当てる処理を行いました。しかし、どのプロセスに実行権を与えるかの判断は行いません。実行可能なプロセス群全体を監視し、どのプロセスに実行権を与えるか判断を下すのはプロセススケジューラです（[#fig1-3 図1-3]）。プロセススケジューラは、いつどのプロセスに実行権を与えるかを決断し、プロセスディスパッチャに切り替え要求を出します。
では、プロセススケジューラはどのような方針に基づいて、いつ、どのプロセスに実行権を与えるべきだと判断するのでしょうか？
==== 1.5.1 スケジューリングの方針
プロセススケジューラの役目は、多くの実行可能プロセスから最も動作するにふさわしいプロセスを選び出すことです。Linuxカーネルのプロセススケジューラは、応答性能とスループットという、互いに矛盾する要求に対応できることを方針として設計されています。シェルプログラムのような対話型プロセスには応答性を保証し、数値計算プログラムを実行するプロセスにはスループットを保証する必要があります。また、多くのプロセスが同時に動作する環境でも、必ずすべてのプロセスに実行権が割り当てられる保証をする必要があります。
===== 1.5.1.1 対話型プロセスの応答性能向上
システム利用者の体感速度を上げるために、対話型プロセスが動作を始めたときは、即座にプロセス切り替えを行い優先的に動作させます。逆にバッチ型プロセスは、その必要がないため、対話型プロセスに実行権を譲ります。とはいってもカーネルからプロセスの種類を区別できないので、Linuxカーネルでは、単位時間当たりの実行時間が少ないプロセスは対話型のプロセスであろうという仮定を行い、スケジューリングします[[footnote(ほとんどの場合は期待どおりにいきますが、この仮定がうまく成り立たないXサーバーのような例もあります。)]]。
===== 1.5.1.2 優先度の指標
各プロセスは実行優先度として、niceコマンドで指定する固定優先度のほかに変動優先度を持ちます（[#fig1-4 図1-4]）。Linuxカーネルは時間経過とともにプロセスの変動優先度を変更し、固定優先度と変動優先度の合計が最も大きなプロセスに実行権を与えます。より多くCPUを利用したプロセスほど、低い変動優先度を持つようになり、シェルのような対話型プロセスはあまりCPUを利用しないため、相対的に高い変動優先度が割り当てられることになります。
{{{ html
<a name="fig1-4"></a>
}}}
[[Thumb(fig1-4.png, size=374x224, caption=図1-4 実行優先度)]]
また、Linuxカーネルのプロセススケジューラは、プロセス動作の統計を基にし、対話型プロセスのような動作をするプロセスに対して、特別に実行優先度を高めるような仕掛けも入っています。
たとえば、あるプロセスAが走行中に、対話型プロセスBが実行可能になったとしましょう。プロセススケジューラは、対話型プロセスBのほうがプロセスAより実行優先度が高いことを認識すると、プロセスディスパッチャを呼び出し、プロセスを切り替えます。この実行中のプロセスから実行権を奪い取ることを「プリエンプトする」といい、その処理は「プリエンプション」と呼びます。プロセススケジューラは、新しいプロセスが実行可能状態になるたびに、プリエンプトする必要があるか否かを判断します。この機能により、応答性を確保しています。
===== 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に割り付けるようにします。キャッシュメモリの大容量化に加え、実メモリとキャッシュメモリの速度差は大きくなる傾向にあるので、キャッシュメモリをどれだけ有効利用できるかが、性能を高める鍵となっています（[#fig1-5 図1-5]）。
{{{ html
<a name="fig1-5"></a>
}}}
[[Thumb(fig1-5.png, size=546x267, caption=図1-5 プロセスとキャッシュの関係)]]
また、TLB（Translation Lookaside Buffer:アドレス変換バッファ）の利用効率もあります。TLBは、仮想アドレスから物理アドレスへの変換を高速化するためのキャッシュです。CPUはアドレス変換を行うために、一度ページテーブルなどのメモリ上に置かれたデータ構造をたどり、実アドレスを求めます（「第9章アドレス変換機構」参照）。しかし、メモリアクセスの度にこのデータ構造を参照することは非常にオーバーヘッドが大きくなるため、最近利用されたアドレス変換情報をTLBと呼ばれる領域にキャッシュしておきます。つまりプロセス空間に対するTLB情報を有効に利用するためには、プロセスを再スケジューリングするときに、やはり同じCPU上で動作させたほうが有利であることが分かります。
Linuxカーネル2.6のプロセススケジューラは、各CPU上でそれぞれ独立して動作しており、それぞれのCPUで動作するのに最も適したプロセスを選択します。プロセスはどこかのCPUにくくり付けるようになっていて、CPU間の負荷バランスが大きく崩れたときのみ、プロセスを別のCPU上で再スケジューリングします。
CPUごとに用意されたプロセススケジューラが、それぞれのCPUに属するプロセス群を管理するようにさせると、もう1つ別のメリットも生まれます。プロセススケジューラどうしが、互いに同じデータ構造を操作することによる競合発生がなくなり、性能向上に貢献します。
===== 1.5.4.1 ハイパースレッディング
{{{ html
<a name="fig1-6"></a>
}}}
[[Thumb(fig1-6.png, size=149x240, caption=図1-6 ハイパースレッディング, float=right)]]
ハイパースレッディングは、Intel Xeonプロセッサから導入された新しい技術で、最近のPentium 4も利用できます。CPU内部の演算器は、メモリアクセスなど遅延が発生する処理を実行すると遊んでしまいます（ストールしてしまいます）。ハイパースレッディングは、この遊んでいる演算器を有効に利用するために導入されました（[#fig1-6 図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つのノードとし、複数のノードを高速スイッチで相互接続したような構造をしています（[#fig1-7 図1-7]）。
{{{ html
<a name="fig1-7"></a>
}}}
[[Thumb(fig1-7.png, size=548x537, caption=図1-7 NUMAシステムにおける負荷バランス)]]
あるCPUから見た場合、同じノード内のメモリアクセスの速度と比較し、ほかのノード上にあるメモリへのアクセスには遅延が生じます。Linuxカーネルはこのことを強く意識してプロセスをスケジューリングします。各プロセスは特定のノードに縛り付け、ほかのノードへの移動を禁止します。そのプロセスは、必要なメモリはそのノード上から確保します。SMPで負荷に偏りができたときには、プロセスをほかのCPUへ移動させることによって負荷バランスを取ってきました。NUMAではノード間を超えてのプロセス移動はできません。実行性能の劣化が大きいためです。
しかし、ノード間でまったく負荷バランスを取ることができないわけではなく、exec処理のタイミングで最も負荷の低いノードにプロセスを移動させます。exec処理は、プロセスが利用していたメモリを一度捨てて再確保するため、プロセス移動の非常に良い機会です。
[[PageNavi(NavigationList)]]