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

プロセススケジューラは実行可能なプロセス群全体を監視し、どのプロセスに実行権を与えるか判断を下している。では、プロセススケジューラはどのような方針に基づいて、いつ、どのプロセスに実行権を与えるべきだと判断するのだろうか?

» 2004年06月10日 00時00分 公開
[高橋浩和(VA Linux Systems Japan),UNIX USER]

UNIX USERプロセスディスパッチャは、指定されたプロセスに実行権を与える、つまりCPUを割り当てる処理を行いました。しかし、どのプロセスに実行権を与えるかの判断は行いません。

 実行可能なプロセス群全体を監視し、どのプロセスに実行権を与えるか判断を下すのはプロセススケジューラです(図3)。プロセススケジューラは、いつどのプロセスに実行権を与えるかを決断し、プロセスディスパッチャに切り替え要求を出します。

 では、プロセススケジューラはどのような方針に基づいて、いつ、どのプロセスに実行権を与えるべきだと判断するのでしょうか?

図3 図3 プロセススケジューラ(クリックで拡大します)
INDEX プロセススケジューラを知る
1. スケジューリングの方針
2. スケジューリング契機
3. リアルタイムプロセス
4. マルチプロセッサシステムにおけるプロセススケジューリング


スケジューリングの方針

 プロセススケジューラの役目は、多くの実行可能プロセスから最も動作するにふさわしいプロセスを選び出すことです。Linuxカーネルのプロセススケジューラは、応答性能とスループットという、互いに矛盾する要求に対応できることを方針として設計されています。シェルプログラムのような対話型プロセスには応答性を保証し、数値計算プログラムを実行するプロセスにはスループットを保証する必要があります。また、多くのプロセスが同時に動作する環境でも、必ずすべてのプロセスに実行権が割り当てられる保証をする必要があります。

対話型プロセスの応答性能向上

 システム利用者の体感速度を上げるために、対話型プロセスが動作を始めたときは、即座にプロセス切り替えを行い優先的に動作させます。逆にバッチ型プロセスは、その必要がないため、対話型プロセスに実行権を譲ります。とはいってもカーネルからプロセスの種類を区別できないので、Linuxカーネルでは、単位時間当たりの実行時間が少ないプロセスは対話型のプロセスであろうという仮定を行い、スケジューリングします。

優先度の指標

 各プロセスは実行優先度として、niceコマンドで指定する固定優先度のほかに変動優先度を持ちます(図4)。Linuxカーネルは時間経過とともにプロセスの変動優先度を変更し、固定優先度と変動優先度の合計が最も大きなプロセスに実行権を与えます。より多くCPUを利用したプロセスほど、低い変動優先度を持つようになり、シェルのような対話型プロセスはあまりCPUを利用しないため、相対的に高い変動優先度が割り当てられることになります。

図4 図4 実行優先度(クリックで拡大します)

 また、Linuxカーネルのプロセススケジューラは、プロセス動作の統計を基にし、対話型プロセスのような動作をするプロセスに対して、特別に実行優先度を高めるような仕掛けも入っています。

 たとえば、あるプロセスAが走行中に、対話型プロセスBが実行可能になったとしましょう。プロセススケジューラは、対話型プロセスBのほうがプロセスAより実行優先度が高いことを認識すると、プロセスディスパッチャを呼び出し、プロセスを切り替えます。この実行中のプロセスから実行権を奪い取ることを「プリエンプトする」といい、その処理は「プリエンプション」と呼びます。プロセススケジューラは、新しいプロセスが実行可能状態になるたびに、プリエンプトする必要があるか否かを判断します。この機能により、応答性を確保しています。

実行保証

 また、プロセスのスケジューリングは、公平性を保つことにも配慮されています。すべてのプロセスは、時分割で動作します。一部のプロセスだけが長時間実行権を握ってしまい、スケジューリング対象から漏れてしまうプロセスが発生しないように、すべてのプロセスへ公平に実行権を与えます。

 具体的には、実行可能状態になったプロセスに実行割り当て時間(タイムスライス)を与えます。実行権を与えられたプロセスは、そのプロセスの実行割り当て時間が残っている間は、実行権を持ち続けることができます。実行割り当て時間を使い切ったプロセスは、ほかのプロセスに実行権を明け渡さなければなりません。一度実行割り当て時間を使い果たしたプロセスは、再度実行割り当て時間を割り当てられるまでスケジューリングの対象にはなりません。新たに実行割り当て時間が与えられるのは、Linuxカーネル上に実行割り当て時間が残っている実行待ちプロセスが1つもいなくなったときです。この仕組みによって、どんなに実行優先度の低いプロセスであっても、必ずCPU上での実行権が回ってくることが保証されています。

 この実行割り当て時間の長さは固定優先度を基に計算します。高い固定優先度を持つプロセスほど長めの実行割り当て時間が与えられ、ほかのプロセスに比べて実行権を握ることのできる機会が増します。

 実行割り当て時間は、Linuxカーネルの時計から、周期的に監視します(scheduler_tick関数)。時計処理の中で実行中プロセスの実行割り当て時間を減らしていき、実行割り当て時間がなくなったところでプロセススケジューラに再スケジューリング要求を出します。

カウンタ方式によるスループットの向上

 Linuxカーネルのこれらの仕組みは、スループットの点でも有利です。

 伝統UNIXでも同様の方針でプロセススケジューリングが行われていましたが、古いUNIXの実装では、時計から実行中プロセスの変動優先度を再計算していました。そのため、プロセスの実行中に実行優先度が下がり、簡単に実行待ち状態にあるほかのプロセスの実行優先度を下回ってしまいます。そして、この下がった瞬間に再スケジューリング要求が発生し、プロセス切り替えが行われていました。

 それに比べLinuxの実装方式では、一度実行権を握ったプロセスは一定時間継続して実行できるため、プロセスの再スケジューリングの回数を最小限に抑え込むことができます。

スケジューリング契機

 すでにいくつか見てきましたが、どのようなときにプロセススケジューラが動作するのでしょうか?

 現在実行中のプロセスが、自ら実行権を手放したときは、当然プロセススケジューラが動作します。具体的には2つの場合があり、1つは、ある事象が成立することを待ち合わせるために、待機状態に遷移したときです。実行権を手放したプロセスは実行可能状態ではなくなるため、残りの実行待ちプロセス群の中から最も実行優先度の高いプロセスを探し出し、実行権を与えます。もう1つは、明示的にほかのプロセスに実行権を譲る場合です。非常に長いカーネル処理を実行するときなど、応答性に悪影響を与えないように自ら実行権を譲ることができます。この場合、このプロセスは実行待ち状態になり、次回のスケジューリングのときに再度実行権を得るかもしれません。

 これらのように実行中プロセスの意思で実行権を渡すのではなく、実行中プロセスから実行権を奪い取ることもできます。先ほども説明したプリエンプションと呼ばれているものです。新しいプロセスが実行待ち状態のプロセス群に加わったとき、その新しいプロセスが現在実行中のプロセスより実行優先度が高いことが分かると、プロセススケジューラに対して再スケジューリング要求を出します(resched_task関数)。プロセススケジューラはこの要求に応答して、最も高い実行優先度を持つプロセスを選択し、プロセス切り替えを行います。たいていの場合、いま実行待ち状態のプロセス群に加わった新しいプロセスが選択されます。

 また、先ほども述べたように、プロセスが実行割り当て時間を使い果たした場合も、Linuxカーネルは強制的に実行権を取り上げ、プロセススケジューラに再スケジューリング要求を出します。プロセスが自主的に実行権を手放したときは、即座にプロセススケジューラが起動し、ほかのプロセスに切り替えますが、実行権を強制的に奪い取る場合は、再スケジューリング要求を出した瞬間にプロセススケジューラが動作するとは限りません。実際にプロセスケジューラが動作するのは、Linuxカーネルが行うべき処理(システムコール処理や割り込み処理)が完了するまで遅延させられます。

 もともとは、Linuxカーネルのコードが複雑にならないように、Linuxカーネル内の任意の個所でプロセス切り替えをすることを禁止していました。しかし、Linuxカーネル2.6では応答性を向上させるため、少しオーバーヘッドは大きくなりますが、Linuxカーネルコード実行中のプリエンプションを許す設定も可能となっています(割り込み処理、遅延処理、排他区間実行中は除く)。

このページで出てきた専門用語
実行時間が少ないプロセスは対話型のプロセスであろうという仮定
ほとんどの場合は期待どおりにいくが、この仮定がうまく成り立たないXサーバーのような例もある。

niceコマンド
UNIXではプロセスの実行優先度をNICE値で指定する。niceコマンドは各プロセスのNICE値を指定するもので、Linuxでは、-20(優先度高)〜19の値となる。

プロセス動作の統計を基にし
Linuxカーネル2.6の実装では、変動優先度を、CPUの利用統計情報から必要なときに毎回動的に計算する。

稼働時間が残っている実行待ちプロセスが1つもいなくなったときです
例外的に、Linuxカーネルが対話型と判断したプロセスに対しては、即座に持ち時間を与えることがある。

Linuxカーネルの時計
時刻管理と時限処理を実現する機能。Intel x86用のLinuxカーネルでは、1ミリ秒ごとに動作する。連載で解説予定。

       1|2 次のページへ

Copyright(C) 2010 SOFTBANK Creative Inc. All Right Reserved.

注目のテーマ