Linux スケジューラーの内側

このあまりにも重要なカーネル・コンポーネントの最新バージョンがスケーラビリティーを改善

Linux® カーネルは、新しい技術を採り入れながら、また信頼性やスケーラビリティー、パフォーマンスを改善しながら、進化を続けています。2.6カーネルの最も重要な機能の 1 つが、Ingo Molnar によって実装されたスケジューラーです。このスケジューラーは、動的であり、ロード・バランシングをサポートし、また一定時間内の動作をします・・・つまりO(1) です。この記事では、Linux 2.6 のスケジューラーの持つこうした特徴などについて解説します。

M. Tim Jones (mtj@mtjones.com), Consultant Engineer, Emulex

M. Tim JonesM. Tim Jones は、埋め込みソフトウェアのエンジニアであり、GNU/Linux Application Programming, AI Application Programming と BSD Sockets Programming from a Multilanguage Perspective の著者でもあります。エンジニアとして経歴は幅広く、静止衛星用のカーネル開発から埋め込みシステム・アーキテクチャー、そしてネットワーク・プロトコル開発まで経験しています。現在は Emulex Corp. のシニア主席エンジニアです。


developerWorks 貢献著者レベル

2006年 6月 30日

この記事では、Linux 2.6 のタスク・スケジューラーと、その最も重要な特徴について解説します。詳細に入る前に、まずスケジューラーの基本的な目標を理解しましょう。

スケジューラーとは何か

一般的な感覚で言えば、オペレーティング・システムは、アプリケーションと利用可能なリソースとの間を仲介します。典型的なリソースとしては、メモリーや物理デバイスなどがあります。しかしCPU もまた、スケジューラーが (タイムスライスという単位で) 一時的にタスクを割り当てる対象となるリソースと考えることができます。スケジューラーのおかげで、複数のプログラムを同時に実行することができ、また要求程度の異なるユーザー同士がCPU を共有することができます。

スケジューラーの重要な目標は、応答性のよいユーザー・エクスペリエンスを提供しつつ、CPUのタイムスライスを効率的に割り当てることです。またスケジューラーには、クリティカルなリアルタイム・タスクへの応答時間を最小にし、なおかつ全体のCPU 使用率は最大化するという相反する目標があります。こうした目標を実現するために、これまでのスケジューラーと比べてLinux 2.6 スケジューラーがどのようなことをしているのか、見ていくことにしましょう。


これまでの Linux スケジューラーの問題

O 記法の重要性

O 記法を使うと、そのアルゴリズムがどのくらい時間を使うかの感覚をつかむことができます。O(n)アルゴリズムに必要な時間は、その入力に依存 (n に関してリニアー) しますが、O(n^2)は入力の 2 次式です。また O(1) は入力とは独立しており、一定時間内の動作をします。

2.6 カーネル以前は、数多くのタスクがアクティブな場合、スケジューラーは大きな制限を抱えていました。これは、O(n)の複雑さを持つアルゴリズムを使ってスケジューラーが実装されていたためです。このタイプのスケジューラーでは、ある1 つのタスクをスケジュールするために必要な時間は、システム中にあるタスクの数の関数になります。言い換えると、タスクの数(n) が多ければ多いほど、ある 1 つのタスクをスケジュールするための時間が長くなります。非常に高負荷の場合には、プロセッサーはスケジューリングに時間を取られてしまい、タスクそのものに費やす時間がほとんど無くなってしまいます。つまり、このアルゴリズムにはスケーラビリティーが欠けているのです。

また、2.6 以前のスケジューラーでは、SMP (symmetric multiprocessing system)の全プロセッサーに対して、1 つのランキュー (runqueue) を使っていました。これはつまり、あるタスクをどのプロセッサーに対してもスケジュールできることを意味します。これはロード・バランシングには好都合ですが、メモリー・キャッシュにとっては不都合です。例えば、あるタスクがCPU-1 上で実行され、そのタスクのデータが、そのプロセッサーのキャッシュの中にあると考えてみてください。もし、このタスクがCPU-2 に再スケジュールされると、CPU-1 の中のデータは無効にし、そのデータをCPU-2 に持ってこなければなりません。

また、これまでのスケジューラーでは、単一のランキュー・ロックも使っていました。そのためSMP システムでは、実行すべきタスクを選択するというアクションが、他のプロセッサーによるランキュー操作をロックアウトしてしまいます。その結果、アイドル・プロセッサーがランキュー・ロックの解放を待つことになり、効率の低下を招いていました。

そして最後に、これまでのスケジューラーではプリエンプションができませんでした。これは、優先度の低いタスクが実行されている間、優先度の高いタスクが待っていなければならなかったことを意味します。


Linux 2.6 のスケジューラーの紹介

2.6 のスケジューラーは、Ingo Molnar によって設計、実装されました。Ingoは 1995 年以来、Linux のカーネル開発に携わっています。彼が新しいスケジューラーに取り組む上で目標としたのは、ウェイクアップやコンテキスト・スイッチ、そしてタイマー割込みオーバーヘッドに関して完全にO(1) のスケジューラーを作ることです。新しいスケジューラーが必要と考えるきっかけとなった問題の1 つが、JVM (Java™ virtual machine) の使い方です。Java のプログラミング・モデルでは多くの実行スレッドを使います。そのため、O(n)スケジューラーによるスケジューリングでは大きなオーバーヘッドが生じます。O(1)スケジューラーは高負荷条件下でも影響を受けないため、JVM を効率的に実行させることができます。

2.6 スケジューラーは、これまでのスケジューラーに見られた、こうした主な3 つの問題 (O(n) と SMP スケーラビリティーの問題) や、その他の問題を解決しています。では、2.6スケジューラーの基本的な設計を見て行くことにしましょう。

主なスケジューリング構造

まず、2.6 スケジューラーの構造を見てみましょう。各 CPU は、FIFO の順番でサービスされる140 の優先リストから成る、1 つのランキューを持っています。実行に向けてスケジュールされるタスク群は、対応するランキューの優先リストの最後に追加されます。各タスクは、そのタスクに与えられる実行時間を決定するタイムスライスを持っています。ランキューの優先リストのうち、最初の100 はリアルタイム・タスク用に予約されており、残りの 40 がユーザー・タスク用に使われます(図 1) 。この区別が重要な理由については、後ほど説明します。

図 1. Linux 2.6 スケジューラーのランキューの構造
The Linux 2.6 scheduler runqueue structure

CPU のランキュー (active ランキューと呼ばれます) の他に、expired ランキューがあります。activeランキュー上のタスクが、そのタイムスライスを完全に使い切ってしまうと、expiredランキューに移動されます。この移動中、そのタスクのタイムスライスは再計算されます(優先度も再計算されますが、これについては後ほど説明します) 。与えられた優先度に対してactive ランキュー上に何もタスクが存在しない場合には、active ランキュー用のポインターとexpired ランキュー用のポインターは交換されます。これによって、expired 優先度リストはactive 優先度リストになります。

スケジューラーのジョブは単純です。最も優先度の高い優先リスト上のタスクを選択して実行するのです。このプロセスを効率的にするために、対象とする優先リスト上にタスク群をいつ載せるかを、ビットマップを使って定義します。従って大部分のアーキテクチャーでは、5つある 32 ビット・ワードの中で、140 の優先度に対してセットされているビットのうち、最も優先度の高いビットを見つけるために、find-first-bit-set命令が使われます。実行すべきタスクを見つけるために必要な時間は、アクティブなタスクの数に依存するのではなく、優先度の数に依存します。つまりアクティブなタスクの数に関わらずスケジューリングの時間は固定されて決められてしまうため、2.6スケジューラーは O(1) プロセスになるのです。

SMP システム用に改善されたサポート

では、SMP とは何なのでしょう。SMP というのは、個々のタスクを同時に実行するために複数のCPUが利用できるアーキテクチャーであり、1 つの CPU がすべてのタスクを実行するという伝統的な非対称プロセスとは異なります。SMPアーキテクチャーは、マルチスレッドのアプリケーションに有利なのです。

これまでのスケジューラーも SMP システムで動作したのですが、その巨大ロック(big-lock) アーキテクチャーのおかげで、ある CPU がディスパッチすべきタスクを選択している間、ランキューはそのCPU によってロックされてしまい、他の CPU は待たなければなりません。2.6スケジューラーはスケジューリング用に 1 つのロックのみを使うのではなく、各ランキューに対してロックを持っています。これによって、どのCPU も他の CPU と競合することなくタスクをスケジューリングすることができます。

さらに、プロセッサー毎にランキューがあるおかげで、一般的にタスクは CPUと親和性が高く、CPU のホット・キャッシュを効率的に利用することができます。

タスクのプリエンプション

Linux 2.6 スケジューラーの、もう 1 つの利点は、プリエンプションが許されていることです。これはつまり、優先度の高いタスクが実行待ちになっている間は、優先度の低いタスクが実行されることはない、ということを意味します。スケジューラーは優先度の低いプロセスをプリエンプトし、そのプロセスを優先リストに戻し、そして再スケジューリングを行います。


これだけではありません!

O(1) であることやプリエンプションが可能なだけでは不十分と言わんばかりに、2.6スケジューラーはタスク優先度の動的変更 (dynamic task prioritization) とSMP ロード・バランシングもサポートしています。これらがどんなものか、またその利点などを見てみましょう。

タスク優先度の動的変更

タスクが CPU を占有してしまい、他のタスクが CPU にアクセスできなくなるのを防ぐために、Linux2.6 のスケジューラーではタスクの優先度を動的に変更できるようになっています。つまり、CPUにバインドされているタスクにはペナルティーを与え、I/O にバインドされているタスクにはリワード(reward: ご褒美) を与えるようになっているのです。一般的に、I/O にバインドされたタスクはI/O の設定に CPU を使いますが、その後は I/O の完了を待ってスリープに入ります。この動作のおかげで、他のタスクがCPU にアクセスすることができます。

ユーザー応答性の改善

ユーザーとコミュニケーションするタスクは対話型であり、従って非対話型のタスクよりも高い優先度が与えられます。ユーザーに対するコミュニケーション(それが stdout へのデータ出力であれ、stdin からの入力待ちであれ) は、I/Oにバインドされています。そのため、こうしたタスクの優先度は高くなっており、その結果、対話動作の応答性が改善されています。

I/O にバインドされたタスクは CPU アクセスに関して利他的とみなされるため、その優先度は(リワードとして) 最大 5 段階高められています。一方、CPU にバインドされたタスクはペナルティーとして、優先度が最大5 段階低くされています。

タスクが I/O にバインドされているのか CPU にバインドされているかの判断は、対話動作を観察することで行われます。タスクの対話性メトリックは、そのタスクのスリープ時間の長さに対して実行時間がどれくらいかに基づいて計算されます。I/Oタスクは I/O をスケジュールしてから待ちに入るため、I/O にバインドされたタスクは実行よりもスリープとI/O の完了待ちに長い時間を費やすことに注意してください。これによって、こうしたタスクの対話性メトリックが大きくなります。

優先度の調整はユーザー・タスクに対してのみ行われ、リアルタイム・タスクには行われないことは重要ですので注意してください。

SMP ロード・バランシング

SMP システム内でタスクが作成される場合、タスクは対象となる CPU のランキューに置かれます。一般的に、あるタスクがどういう場合に実行時間が短く、どういう場合に長時間実行するかを知ることはできません。従ってCPU へのタスク割り当ては、最初は最適でない可能性があります。

複数の CPU にまたがって負荷バランスを維持するためには、負荷を再分散し、過負荷のCPU から負荷を減らして、低負荷状態にある CPU に負荷を回す必要があります。Linux2.6 のスケジューラーは、この機能をロード・バランシングを使って実現しています。プロセッサーは200ms 毎に、CPU 負荷がアンバランスではないかをチェックします。もしアンバランスな場合には、プロセッサーがCPU 全体にまたがってタスクのバランシング処理を行います。

このプロセスの負の側面として、新しい CPU のキャッシュが、移行されたタスクに対してコールドである(移行されたタスクのデータをキャッシュに入れる必要がある) ことが挙げられます。

CPU のキャッシュはローカルな (つまりオンチップの) メモリーであり、システムのメモリーよりも高速のアクセスを実現することを思い出してください。あるタスクがCPU 上で実行され、そのタスクに関連したデータが CPU のローカル・キャッシュに持ち込まれた場合、そのキャッシュはホットであると見なされます。CPUのローカル・キャッシュにタスク用のデータが何もない場合には、このタスクに対してキャッシュはコールドであると見なされます。

移行されたタスクに対してCPU キャッシュがコールドなことは残念ですが、これはCPU をビジー状態に維持することでカバーすることができるのです。


まだまだ他にも・・・

2.6 スケジューラーのソースは、/usr/src/linux/kernel/sched.c というファイルの中にうまくカプセル化されています。このファイルの中にある、他の興味深い機能を表1 にあげておきます。

表 1. Linux 2.6 スケジューラーの機能
機能名機能の説明
scheduleメインのスケジューラー機能。最高の優先度を持つタスクの実行をスケジュールします。
load_balanceCPU をチェックしてアンバランスが生じていないかを調べ、アンバランスな場合にはタスクの移動を試みます。
effective_prio実質的なタスクの優先度を返します (静的な優先度に基づきますが、リワードやペナルティーも含みます)。
recalc_task_prioタスクのボーナスやペナルティーを、タスクのアイドル時間に基づいて決定します。
source_load(タスクの移行元となる) ソース CPU の負荷を、控えめに計算します。
target_load(タスクの移行先となり得る) ターゲット CPU の負荷を、大きめに計算します。
migration_threadCPU 間でタスクの移行を行う、優先度の高いシステム・スレッドです。

ランキューの構造も、/usr/src/linux/kernel/sched.c ファイルの中にあります。2.6スケジューラーはオプションとして、(CONFIG_SCHEDSTATS を使って有効にすれば)統計機能を提供することもできます。この統計機能は /proc/schedstat にある/proc ファイルシステムから利用でき、ロード・バランシングやプロセス移行の統計を含めて、システム中の各CPU に関する様々なデータを表現することができます。


これから先は

Linux 2.6 スケジューラーは、これまでの Linux スケジューラーから大きく進歩しました。CPU利用率を高めるために大きな改善が行われた一方、ユーザーに対する応答性も良くなっています。プリエンプションが可能となり、またマルチプロセッサー・アーキテクチャーのサポートが改善された結果、デスクトップにもリアルタイム・システムにも最適なオペレーティング・システムに、さらに近づきました。Linux2.8 カーネルはまだ遠い先ですが、2.6 で行われた変更を見ると、これからも良いものがいろいろと期待できそうです。

参考文献

学ぶために

製品や技術を入手するために

  • Linux Kernel Archives には、最新の Linux カーネルが置かれています。
  • developerWorks から直接ダウンロードできる IIBM trial software を使って、皆さんの次期 Linux 開発プロジェクトを構築してください。

議論するために

コメント

developerWorks: サイン・イン

必須フィールドは(*)で示されます。


IBM ID が必要ですか?
IBM IDをお忘れですか?


パスワードをお忘れですか?
パスワードの変更

「送信する」をクリックすることにより、お客様は developerWorks のご使用条件に同意したことになります。 ご使用条件を読む

 


お客様が developerWorks に初めてサインインすると、お客様のプロフィールが作成されます。会社名を非表示とする選択を行わない限り、プロフィール内の情報(名前、国/地域や会社名)は公開され、投稿するコンテンツと一緒に表示されますが、いつでもこれらの情報を更新できます。

送信されたすべての情報は安全です。

ディスプレイ・ネームを選択してください



developerWorks に初めてサインインするとプロフィールが作成されますので、その際にディスプレイ・ネームを選択する必要があります。ディスプレイ・ネームは、お客様が developerWorks に投稿するコンテンツと一緒に表示されます。

ディスプレイ・ネームは、3文字から31文字の範囲で指定し、かつ developerWorks コミュニティーでユニークである必要があります。また、プライバシー上の理由でお客様の電子メール・アドレスは使用しないでください。

必須フィールドは(*)で示されます。

3文字から31文字の範囲で指定し

「送信する」をクリックすることにより、お客様は developerWorks のご使用条件に同意したことになります。 ご使用条件を読む

 


送信されたすべての情報は安全です。


static.content.url=http://www.ibm.com/developerworks/js/artrating/
SITE_ID=60
Zone=Linux
ArticleID=230697
ArticleTitle=Linux スケジューラーの内側
publish-date=06302006