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

大きなシステムへのLinuxカーネル適用を考えたとき、従来の構造ではオーバーヘッドが大きくなる。そこで、Linuxカーネル2.6ではプロセス数によらず、プロセススケジューラの処理量が一定となる構造のプロセススケジューラが導入された。この仕組みを見ていこう。

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

　Linuxカーネル2.6のプロセススケジューラには、スケーラビリティがあります。Linuxカーネル2.4以前のプロセススケジューラは非常に単純な構造で、マルチプロセッサシステムであっても、単一のキューに実行可能プロセスをすべてつなぎ、再スケジューリングの度にキューに登録されているすべてのプロセスを検索して、実行権を与えるプロセスを選び出していました。

　実行可能プロセス数があまり多くならないシステムでは、これでも十分期待どおりの結果が出ていましたが、大きなシステムへのLinuxカーネル適用を考えたとき、従来の構造ではオーバーヘッドが大きくなります。そこで、Linuxカーネル2.6ではプロセス数によらず、プロセススケジューラの処理量が一定となる構造のプロセススケジューラが導入されました。

INDEX　プロセススケジューラの実装

1. 実行優先度ごとのRUNキュー 2. 2種類のRUNキュー 3. CPUごとのRUNキュー 4. アイドルプロセス 5. カレントプロセス 6. プロセッサバインド機能 7. プロセススケジューラのアルゴリズム

実行優先度ごとのRUNキュー

　実行可能なプロセスはRUNキューに登録されます。Linuxカーネル2.6のRUNキューは実行優先度ごとにスロットを用意しています。次に実行するプロセスは、プロセスが存在する最も高い実行優先度のスロットから、先頭に登録されているプロセスを選択するだけです。これによって、再スケジューリング時、最も実行優先度の高いプロセスを容易に見つけることができます。実行可能なプロセスがいくつ存在していても、検索量は常に一定であるため、検索指定（オーダー）が1のスケジューラ、つまり「O(1)スケジューラ」と呼ばれています（図8）。

図8 O(1)スケジューラの構造（クリックで拡大します）

2種類のRUNキュー

　Linuxカーネル2.6は、2種類のRUNキューを持ちます。それぞれ、activeキュー、expiredキューと呼ばれています。activeキューには、実行可能で、実行割り当て時間を持っているプロセスを登録します。expiredキューには、実行可能状態だが、実行割り当て時間を使い果たしてしまったプロセスを登録します。expiredキューの構造はactiveキューの構造とまったく同じで、プロセスは実行優先度ごとに分類して登録されています。

　実行を続けているとactiveキュー上のプロセスは、実行割り当て時間を使い果たしてexpiredキューに移動するか、もしくは何らかの事象待ちのために待機状態に遷移します。いずれactiveキュー上のすべてのプロセスがいなくなります。すると、プロセススケジューラはactiveキューをexpiredキューと交換して処理を継続します。それまでのexpiredキューがactiveキューとなり、プロセススケジューラは、そのキューに登録されている中で最も実行優先度の高いプロセスに実行権を与えます。

　このRUNキューの構造によって、一度実行割り当て時間を与えられactiveキューに登録されたプロセスは、いくら低い優先度であっても、必ず実行権が回ってくることが保証されます。

CPUごとのRUNキュー

　マルチプロセッサシステムでは、RUNキュー（activeキューとexpiredキューの組み）をCPUごとに用意します（図9）。CPUごとに用意したプロセススケジューラは、そのCPU用のRUNキュー上のプロセスに対して働きます。この構造により、特定のプロセスは、毎回特定のCPU上で実行されることとなり、キャッシュメモリやTLBが有効利用されます。

　ただし、RUNキュー間で負荷状態に偏りが出たときは、RUNキュー間で実行待ちプロセスの移動を行いバランスを取ります（load_balance関数）。

図9 CPUごとのRUNキュー間の負荷バランス（クリックで拡大します）

アイドルプロセス

　実行可能なプロセスが1つも存在しないとき、Linuxカーネルは実行権を与えるべき対象がありません。このようなときには、プロセススケジューラ自体がアイドル状態となるOSもありますが、Linuxカーネルの実装では何も実行しないアイドルプロセスを用意し、このプロセスに実行権を与えます。アイドルプロセスは何もせず、実行可能なプロセスが現れ、プリエンプトされるのを待ち続けます。

　このアイドルプロセスを、各CPUに1つ用意しています。アイドルプロセスはRUNキューには登録されておらず、RUNキュー上に実行可能プロセスが1つも存在しなくなったときにのみ、プロセススケジューラが実行対象として選択します。

カレントプロセス

　まさにCPU上で実行中のプロセスのことを、カレントプロセスと呼ぶこともあります。カレントプロセスはCPUの数だけ存在します。

　Linuxカーネルの実装では、カレントプロセスもRUNキューに登録されたままになっています。データ構造上での実行待ち状態のプロセスとの違いは、currentというポインタで指されていることです（RUNキューのcurrメンバーによっても指されています）。

　Linuxカーネルコード中には、カレントプロセスを指すcurrentというポインタ変数が頻繁に登場します。このcurrentという変数は各々のCPUで異なる値となるため、Intel x86用Linuxカーネルの実装では、スタックポインタの値を基に計算※して求めるようになっています。

　Linuxカーネル2.4では、カーネルスタックはtask_struct構造体中に確保されていたのですが、Linuxカーネル2.6ではtask_struct構造体中の一部のメンバーとともに、thread_info構造体に分割されました。そのため、スタックポインタ（EIP）の下位ビットをマスクすることによって、このプロセス用のthread_info構造体が求められ、さらにthread_info構造体からtask_struct構造体を求めます（図10）。

図10 スタックポインタとカレントプロセス（クリックで拡大します）

プロセッサバインド機能

　プロセスを明示的に特定のCPU用のRUNキューにくくり付けることが可能です。これにはsched_setaffinityシステムコールを使います。この情報は、task_struct構造体中に保存され、RUNキュー間での負荷バランス調整を行うときに考慮されます。

　O(1)スケジューラは、プロセスのCPU間移動を抑制する構造になっていますが、プロセッサバインド機能によってプロセス移動を禁止できます。システム構築者が、前もって負荷バランスを見積もり、プロセスを割り付けるCPUを決定したい場合に使えます。

　また、カーネルスレッドの中には特定のCPU用のデータ構造操作を目的とするものがあり、これらのスレッドもプロセッサバインド機能を利用して、必ず目的のCPU上で動作するようにしています。

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

スタックポインタの値を基に計算 個人的には、CPU固有空間を用意して、その上にCPU固有のデータを置けば美しいと思う。