マルチタスク――プロセススケジューリング（その1）：UNIX USER2004年6月号「Linuxカーネル2.6解読室」より転載

「UNIX USER」誌上で連載されている「Linuxカーネル2.6解読室」から、カーネル機能の本体ともいえるプロセススケジューラについて、設計ポリシーとその実装についての解説を数回に分けてお届けする。

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

　UNIX/Linux情報を扱う月刊誌「UNIX USER」では、2004年6月号より、「Linuxカーネル2.6解読室」という連載を開始している。同連載では、Linuxカーネルの実装機能が詳細に解説されており、Linuxカーネルを学ぶにはよいドキュメントとなっている。

　ここでは、同連載の第一回を転載する形で、カーネル機能の本体ともいえるプロセススケジューラについて、設計ポリシーとその実装を数回に分けてお届けする。

　ちなみに、本誌の連載予定は次のようになっている。興味を持たれたらぜひ手にしてみてはいかがだろう。

月号	回数	内容
2004年6月号	第1回	プロセススケジューリング
2004年7月号	第2回	割り込み処理
2004年8月号	第3回	時計
2004年9月号	第4回	システムコール
2004年10月号	第5回	同期と排他
2004年11月号	第6回	プロセス管理
2004年12月号	第7回	シグナル、スレッド
2005年1月号	第8回	実メモリ管理
2005年2月号	第9回	仮想記憶
2005年3月号	第10回	仮想ファイルシステム
2005年4月号	第11回	Linux標準ファイルシステムExt2
2005年5月号	第12回	ジャーナリングファイルシステムExt3
2005年6月号	第13回	ブロック型デバイス
2005年7月号	第14回	ネットワーク
2005年8月号	第15回	Linuxカーネルの起動
2005年9月号	第16回	プロセス間通信

マルチタスク

　Linuxカーネルはマルチタスクの仕組みを提供し、複数のプロセス（後述）を同時に実行可能です。ここで同時と書きましたが、ある一時点で動作しているプロセス数は、そのシステムに搭載されているCPU数以上には決してなりません。しかし、管理利用者の視点からは、多数のプロセスが同時に並列動作しているように感じられます。

　Linuxカーネルは、複数のプロセスを細かく切り替えながら動作させ、いかにも同時動作しているような環境を作り出しています。Linuxカーネルは、その時点で最も重要と思われるプロセスに実行権を与えるように動作します。マルチタスク環境を提供するOSであれば、どのOSでもほぼ同様の仕組みで実現されています。

　この処理を行う機能のことをプロセススケジューラと呼びます。Linuxカーネルを理解するうえで最も根本的な機能であるため、Linuxカーネル解説の最初の話題として取り上げることにしました。

　Linuxカーネル2.6におけるプロセススケジューリングの方針は、Linuxカーネル2.4のそれとは大きな違いはありません。しかし、その実装は、Linuxカーネル2.4のものから全面的に書き直されました。新しいプロセススケジューラは、「O(1)スケジューラ」（オーダーワン・スケジューラ）と呼ばれています。このプロセススケジューラは、数多くのプロセスが同時に動作する大規模システムにおいて、プロセススケジューリングのオーバーヘッド※を減らすことを目的として導入されました。

プロセスとは？

　プログラムが動いている状態のことをプロセスと呼びます（タスクと呼んでいるOSもあります）。psコマンドによって表示できるものがプロセスです。プログラムが1つであっても、そのプログラムを実行しているプロセスが複数存在することもあります。

　おのおののプロセスは、そのプロセス固有のコンテキストを持ちます。コンテキストとは、そのプロセスが動作するためのプロセス空間、そのプロセスが動作するときのレジスタ※値などです。これらの個々のプロセスに関する情報は、task_struct構造体（task_t型）※で管理されています（図1）。Linuxカーネルがプロセスを操作するときは、この構造体を操作することになります。

図1　task_struct構造体

　また、Linuxカーネルではスレッド※も一種のプロセスとして管理しています。スレッドどうしが同じプロセス空間を共有していることを除けば、通常のプロセスと同じです。各スレッドにもtask_struct構造体が割り当てられています。プロセススケジューリングの点からは、どちらもまったく同じものとして扱われます。

　さらに、Linuxカーネルのコードのみを実行するカーネルスレッド（別途詳しく説明予定）も、プロセススケジューリングの視点からは、プロセスと同じものです。固有のプロセス空間を持たないことを除けば、task_struct構造体が割り当てられ、プロセスと同様に管理されます。

プロセス切り替え

　限られた数のCPUを、数多くのプロセスから同時に利用するため、プロセススケジューラは最も動作させるにふさわしいプロセスにCPU実行権を与えようとします。最もふさわしいプロセスに実行権を与えるためには、もともとそのCPU上で動作していたプロセスの実行を中断し、新しいプロセスの実行を開始することになります。この処理のことを「プロセス切り替え」または、「プロセスディスパッチ」と呼びます。また、プロセス切り替えを行う機能を「プロセスディスパッチャ」と呼びます。

　ところで、プロセスを切り替えるとは具体的にはどのような作業でしょうか？　あるCPU上で動作しているプロセスAから、別のプロセスBに切り替えることを考えてみましょう（図2-1）。

　プロセスAは、プロセスAのために用意されたプロセス空間上で走行しています。プロセスAで実行中のプログラムでは、変数の値はメモリもしくはレジスタ上に存在し、実行中の命令はプログラムカウンタレジスタ※が指しています。プロセスAが利用中のスタック※はスタックポインタが指しています。また、プロセスAのプロセス空間そのものも、特殊レジスタによって管理されています。

　つまり、これらレジスタ群をすべてプロセスB用のレジスタ値で書き直せば、その瞬間からプロセスBが動作を始めることが理解できると思います（図2-2）。また、再度プロセスAの実行を再開できるようにするためには、プロセスB用のレジスタ値で書き直す前に、プロセスA用のレジスタ値を退避しておく必要があることも分かると思います（図2-3）。

　これらレジスタ群の値のことをコンテキスト※と呼びます。実行待ち状態のプロセスは、これらコンテキストをtask_struct構造体やカーネルスタックに退避しておき、実際に実行状態になると、そのコンテキストをCPU上に読み込みます。

図2　プロセスの切り替え（クリックで拡大します）

---

　次回はプロセスディスパッチャの実装などについて触れていく。

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

オーバーヘッド 本来の目的の処理以外に、必要となる処理の総計。 レジスタ CPU内部の演算や実行状態を保持している記憶領域。CPUとのやり取りはレジスタを介して行う。 task_struct構造体（task_t型） カーネルのソースコード中では、task_struct構造体型がtask_t型として定義し直され、task_struct構造体型とtask_t型との両方が混在している。ソースコードを読むときに注意。 スレッド ソフトウェアの実行単位。1つのプログラムが複数のスレッドを持ち、複数のスレッドで1つのプログラムで実行できれば（マルチスレッド）、同時に複数の処理を実行できる。プロセスとの違いは、メモリなどのリソースの扱い。同じプログラムに属するスレッドはお互いにリソースを共有し、マルチプロセスと比べタスク切り替えのオーバーヘッドが小さい。プロセスはそれぞれ独立したリソースを持っている。 プログラムカウンタレジスタ 実行中のコードがどこか（次の実行コードのアドレス）を示しているもの。Intel x86の場合は、EIP（Extended Instruction Pointer）レジスタである。プログラムカウンタと命令（インストラクション）ポインタは同じ意味。CPU機能の拡張に伴い、現在はEIPを用いている。 スタック 最後に入力したデータが先に出力されるという特徴を持つデータ構造の一種。本を積んで（stack）いって上から取リ出すイメージ。多くのCPUはスタックにデータを出し入れする命令を持っており、簡単に利用できる。スタックとは逆に、先に入力したデータが先に出力されるデータ構造は、キュー（待ち行列）と呼ばれている。 コンテキスト 正確にはレジスタだけでなく、プロセスを形作るものすべて。

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