Linux カーネル 2.6 Completely Fair Scheduler の内側

2.6.23 以降、CPU の利用に関して公平性をもたらしています

タスク・スケジューラーは、あらゆるオペレーティング・システムの中核です。この分野での進化と技術革新を続ける Linux® は、カーネル 2.6.23 で CFS (Completely Fair Scheduler) を導入しました。このスケジューラーはランキューに依存する代わりに、赤黒木の実装を使用してタスクを管理します。CFS の背後にある概念とその実装、そして以前の O(1) スケジューラーに勝る利点を学んでください。

M. Tim Jones, Independent author

M. Tim JonesM. Tim Jones は組み込みソフトウェアのエンジニアであり、『Artificial Intelligence: A Systems Approach』、『GNU/Linux Application Programming』現在、第 2 版です) や『AI Application Programming』(こちらも現在、第 2 版です)、それに『BSD Sockets Programming from a Multilanguage Perspective』などの著者でもあります。技術的な経歴は静止軌道衛星用のカーネル開発から、組み込みシステム・アーキテクチャーやネットワーク・プロトコル開発まで、広範にわたっています。また、コロラド州ロングモン所在のEmulex Corp. の顧問エンジニアでもあります。


developerWorks 貢献著者レベル

2009年 12月 15日

Linux スケジューラーは、2 つの競合する要素が決定に影響を及ぼす興味深い典型例です。一方の要素は、Linux が適用されている使用モデルです。Linux は、元々デスクトップ向けの新しいオペレーティング・システムとして開発されましたが、今ではサーバーや小型組み込み機器、メインフレーム、そしてスーパーコンピューターでも使われるようになっています。当然のことながら、それぞれの機器によってスケジューリングに課せられる負荷は異なります。もう一方の要素は、プラットフォームにおける技術の進歩です。これにはアーキテクチャー (マルチプロセッシング、対称型マルチスレッド化、NUMA (Non-Uniform Memory Access)) や仮想化も含まれます。さらにここに、対話性 (ユーザー応答性) と全体的な公平性とのバランスも関わってスケジュールが決定されます。このように考えると、Linux 内部ではスケジューリングがいかに難しい問題になり得るかが理解できるはずです。

Linux スケジューラー小史

初期の Linux スケジューラーで使用していたのは最小限の設計だけで、多数のプロセッサーからなる大規模なアーキテクチャーはもちろんのこと、ハイパースレッディングにさえも重点を置いていなかったのは明らかです。Linux 1.2 のスケジューラーは、ラウンドロビン・スケジューリング・ポリシーで動作する循環キューを使用して実行可能タスクを管理します。このスケジューラーは、(ロックによって構造体を保護して) プロセスを追加、削除するには効率的でした。要するに、1.2 のスケジューラーは複雑ではなく、単純で処理速度に優れたスケジューラーだったということです。

Linux バージョン 2.2 ではスケジューリング・クラスの概念が導入され、リアルタイム・タスク、プリエンプト不可タスク、そして非リアルタイム・タスクごとのスケジューリング・ポリシーを使えるようになりました。さらに、2.2 のスケジューラーには対称型マルチプロセッシング (SMP) のサポートも組み込まれました。

2.4 カーネルに統合されたのは、O(N) 時間で動作する比較的単純なスケジューラーです (比較的単純と言っている理由は、スケジューリング・イベントの間、すべてのタスクを繰り返し処理するからです)。2.4 カーネルのスケジューラーは時間をエポックに分割します。そしてエポックを単位に、すべてのタスクはそれぞれに割り当てられたタイム・スライスを使い切るまで実行を許可されます。タスクがそのタイム・スライスを使い切らなかった場合は、残りのタイム・スライスの半分が次のエポックでの新しいタイム・スライスに追加され、次のエポックで許可される実行時間がその分長くなります。このスケジューラーは goodness 関数 (メトリック) を適用して次に実行するタスクを決定しながら、単純にタスクを繰り返し処理します。この手法は比較的単純であるとは言え、それほど効率的ではなく、拡張性にも欠けるため、リアルタイム・システムには力不足です。また、マルチコア・プロセッサーなどの新しいハードウェア・アーキテクチャーを利用する機能もありませんでした。

O(1) スケジューラーと呼ばれる初期の 2.6 スケジューラーは、2.4 スケジューラーでの問題の多くを解決するために設計されました。このスケジューラーはタスクのリスト全体を繰り返し処理しなくても、次にスケジューリングするタスクを特定することができます。これが O(1) という名前の由来で、2.4 スケジューラーに比べて遥かに効率的で拡張性があることを表しています。O(1) スケジューラーはランキューに入れられた実行可能タスクを追跡します (実際には、優先度ごとに 2 つのランキューがあります。1 つはアクティブなタスク用、もう 1 つは有効期限が切れたタスク用です)。したがって、スケジューラーが次に実行するタスクを特定するには、特定のアクティブな優先度別ランキューから次のタスクをデキューすればよいだけとなります。O(1) スケジューラーは以前のスケジューラーと比べ、遥かに拡張性が改善されています。さらにタスクが I/O バウンドなのか、プロセッサー・バウンドなのかを判断できるように、多数のヒューリスティックと対話性のメトリックを組み合わせています。しかし、そんな O(1) スケジューラーもカーネル内部で手に負えなくなってきました。ヒューリスティックの計算に必要な大量のコードが根本的に管理しにくかったこと、そして純粋主義者にとってはアルゴリズムに関する内容が欠けていたことが、その原因です。

プロセスとスレッドの違い

Linux ではプロセスとスレッドのスケジューリングを統合する手段として、この 2 つを同じものとして扱います。1 つのプロセスは 1 つのスレッドと見なすことができます。ただしプロセスには、リソース (コードやデータ) を共有する複数のスレッドを含めることができます。

O(1) スケジューラーや、スケジューリングに関与する他の外部要素が直面している問題を考えると、何らかの変化が必要なことは確かでした。その変化は、Con Kolivas が開発した RSDL (Rotating Staircase Deadline Scheduler) によるカーネル・パッチという形でやってきました。このカーネル・パッチには、Kolivas がその前に行った Staircase Scheduler での作業が組み込まれています。この作業によって生まれたのは、公平性と待ち時間の上限値とを組み合わせるという単純な設計のスケジューラーです。Kolivas のスケジューラーは (現行の2.6.21 メインライン・カーネルへの統合を求める声とともに) 多くの人々に強い印象を与えました。こうなれば、スケジューラーの変更がまもなく実現されることは明らかです。そして O(1) スケジューラーを作成した Ingo Molnar が、Kolivas の成果から得たヒントを基に CFS を開発したというわけです。ここからは CFS について詳しく調べ、その全体的な動作を見ていきます。


CFS の概要

CFS の背後にある主な概念は、タスクに与えるプロセッサー時間のバランス (公平性) を維持するためのものです。つまり、それぞれのプロセスには公平にプロセッサー時間が与えられるようにしなければなりません。タスクに与えられた時間のバランスが崩れると (つまり、1 つまたは複数のタスクに与えられた時間が他のタスクと比べて十分でない場合)、バランスの取れていないタスクに実行時間が与えられることになります。

バランス状態を判断するため、CFS は特定のタスクに割り当てられた時間を仮想実行時間と呼ばれるものに保持します。タスクの仮想実行時間が短ければ短いほど (つまり、タスクに許可されているプロセッサーへのアクセス時間が短いという意味)、タスクがプロセッサーを必要とする度合いは高くなります。CFS にはスリープ中のタスクに対する公平性の概念も採り入れられています。その目的は、現在実行可能でないタスク (例えば、入出力処理を待機中のタスク) でも、最終的にプロセッサーが必要となったときに同等のプロセッサー時間を確保できるようにするためです。

しかし CFS は以前の Linux スケジューラーのようにタスクをランキューに入れて保持するのではなく、時間で順序付けされた赤黒木で保持します (図 1 を参照)。赤黒木には、実用的で興味深い特性がいくつかあります。第一の特性は、赤黒木が平衡木であることです。つまり、この木のなかではどのパスの長さも、他のパスの 2 倍を超えることはありません。第二に、赤黒木での操作に要する時間は O(log n) 以下です (ここで、n は赤黒木のノード数です)。したがって短時間で効率的にタスクを挿入、削除することができます。

図 1. 赤黒木の例
Example of a red-black tree

時間で順序付けされた赤黒木に保存されるタスク (sched_entity オブジェクトで表現) のうち、プロセッサーを最も必要としているタスク (仮想実行時間が最も短いタスク) は赤黒木の左端に保管され、プロセッサーの必要性が最も低いタスク (仮想実行時間が最も長いタスク) は右端に保管されます。CFS スケジューラーは公平性を保つために、次のスケジューリング対象として赤黒木の最左端に位置するノードを選択します。タスクはその実行時間を仮想実行時間に加算するという手段で CPU の使用時間を計上します。その後、タスクが実行可能であれば赤黒木に戻されます。このように、実行時間は赤黒木の左側にあるタスクに与えられるので、公平性を維持するために、赤黒木を構成するタスクは右から左へと移動されます。したがって、実行可能タスクのそれぞれが他の実行可能タスクを追跡することによって、一連の実行可能タスク全体で実行のバランスを保ちます。


CFS の構成要素

Linux 内部のすべてのタスクは、task_struct というタスク構造体によって表現されます。この構造体が (そしてこの構造体に関連付けられた他の構造体とともに) タスクを完全に記述し、タスクの現行の状態、スタック、プロセス・フラグ、優先度 (静的および動的優先度の両方) などを組み込みます。./linux/include/linux/sched.h を見ると、この構造体、そして関連する構造体の多くがあるはずです。しかし、すべてのタスクが実行可能であるわけではないので、task_struct には CFS 関連のフィールドがありません。その代わりとして、スケジューリング情報を追跡する sched_entity という新しい構造体が作成されています (図 2 を参照)。

図 2. タスクの構造体階層と赤黒木
Structure hierarchy for tasks and the red-black tree

図 2 には、さまざまな構造体の間の関係が示されています。赤黒木のルートは (./kernel/sched.c 内の) cfs_rq 構造体から rb_root 要素を介して参照されます。赤黒木の葉には情報は何も含まれませんが、内部ノードは実行可能な 1 つ以上のタスクを表します。赤黒木の各ノードを表す rb_node に含まれるのは、子の参照と親の色だけです。rb_node を包含する sched_entity 構造体には、rb_node 参照、ロードの重み、そして各種の統計データが組み込まれます。最も重要な点は、sched_entity には vruntime (64 ビットのフィールド) が含まれることです。これまでのタスクの実行時間が示されるこのフィールドは、赤黒木の索引としての役割を果たします。この sched_entity 構造体は、タスクを完全に記述する先頭の task_struct に組み込まれます。

スケジューリング関数は、CFS の部分に関しては至って単純です。./kernel/sched.c には、汎用 schedule() 関数があります。この関数は yield() によってこの schedule() 関数自体をプリエンプトする場合を除き、現在実行中のタスクをプリエンプトします。プリエンプションの時間は可変であるため、CFS にはプリエンプション用のタイム・スライスという概念は実際に存在しないことに注意してください。現在実行中の (そしてプリエンプトされている) タスクは、(スケジューリング・クラスを介した) put_prev_task の呼び出しによって赤黒木に戻されます。schedule 関数はスケジュール対象の次のタスクを特定する段階にくると、pick_next_task 関数を呼び出します。この関数も同じく汎用関数です (./kernel/sched.c に含まれます)。ただし、この関数はスケジューラー・クラスを介して CFS スケジューラーを呼び出します。CFS の pick_next_task 関数は ./kernel/sched_fair.c にあります (pick_next_task_fair() という名前)。この関数は単純に赤黒木の最左端にあるタスクを選択し、関連する sched_entity を返すだけにすぎません。この参照により、task_of() を単純に呼び出すだけで、返された task_struct 参照が特定されます。そして最終的に、汎用スケジューラーによってこのタスクにプロセッサーが割り当てられます。

優先度と CFS

CFS は優先度を直接使用することはしませんが、タスクに許可する実行時間の減衰係数として、優先度を使用します。優先度が低いタスクの減衰係数は高く、逆に優先度が高いタスクの減衰係数は低くなります。つまり、タスクに許可される実行時間は、優先度の高いタスクより、優先度の低いタスクのほうが短くなるということです。この賢いソリューションにより、優先度ごとにランキューを維持する必要がなくなります。

CFS のグループ・スケジューリング

CFS の興味深い特徴としては、2.6.24 カーネルで導入されたグループ・スケジューリングの概念も挙げられます。グループ・スケジューリングはスケジューリングに公平性をもたらすもう 1 つの手段であり、特に、タスクが他の多くのタスクを発生させる場合に効果を発揮します。例えば、多くのタスクを発生させて入接続を並列化するサーバーがあるとします (これは HTTP サーバーの典型的なアーキテクチャーです)。この場合、CFS はすべてのタスクを平等に扱うのではなく、グループ単位でタスクの実行時間を扱います。複数のタスクを発生させるサーバー・プロセスでは、(階層型) タスク・グループ全体で仮想実行時間を共有する一方、単一のタスクでは他のタスクとは関係なく独自の仮想実行時間を持つようになります。したがって、単一のタスクには、タスク・グループとほぼ同じ長さの実行時間がスケジューリングされます。どのようなグループを形成するかは、プロセスの階層を管理する /proc インターフェースによって完全に制御可能です。この構成を使用することで、公平なスケジューリングをユーザーやプロセス、あるいはその変形を対象に割り当てることができます。


スケジューリング・クラスおよびドメイン

CFS では、スケジューリング・クラスの概念も導入されました (図 2 を参照)。各タスクは、タスクのスケジューリング方法を決定するスケジューリング・クラスに属します。スケジューリング・クラスは、スケジューラーの振る舞いを定義する関数の共通セットを (sched_class によって) 定義します。例えば、スケジューリング対象のタスクを追加し、次に実行するタスクをプルしてスケジューラーに渡すなどの方法は、スケジューラーごとに決まっています。個々のリンク・リスト内にあるスケジューラー・クラスは互いにリンクされ、(特定プロセッサー上で無効化を有効にするなどの目的で) クラスを繰り返し処理できるようになっています。図 3 にスケジューリング・クラスの全体の構造を示します。注意する点として、エンキューおよびデキュー・タスクの関数は、特定のスケジューリング構造体に対して単純にタスクを追加、削除するだけです。pick_next_task 関数が、そのスケジューリング・クラスの特定ポリシーに基づいて、次に実行するタスクを選択します。

図 3. スケジューリング・クラスの全体図
Graphical view of scheduling classes

しかしここで思い出してほしいのは、スケジューリング・クラスはタスク構造体自体に含まれているということです (図 2 を参照)。そのため、タスクでの操作は、そのタスクのスケジューリング・クラスが何であろうと単純になっています。一例として、以下の関数は現在実行中のタスクをプリエンプトし、./kernel/sched.c にある新しいタスクに置き換えます (ここで、curr は現在実行中のタスクを定義し、rq は CFS の赤黒木を表します。p は次にスケジューリングするタスクです)。

static inline void check_preempt( struct rq *rq, struct task_struct *p )
{
  rq->curr->sched_class->check_preempt_curr( rq, p );
}

このタスクが fair スケジューリング・クラスを使用しているとしたら、check_preempt_curr() のところは check_preempt_wakeup() が実行されることになります。これらの関係については、./kernel/sched_rt.c、./kernel/sched_fair.c、および./kernel/sched_idle.c を見るとわかります。

スケジューリング・クラスもまた、スケジューリング変更に関する興味深い側面の 1 つですが、機能の拡張はスケジューリング・ドメインの追加によって実現します。スケジューリング・ドメインを使用することで、ロード・バランシングや分離を目的として 1 つ以上のプロセッサーを階層的にグループ化することができます。1 つ以上のプロセッサーがスケジューリング・ポリシーを共有 (およびプロセッサー間でのロード・バランシングを実行) することも、タスクを意図的に分離するために各プロセッサーが個別にスケジューリング・ポリシーを実装することも可能です。


その他のスケジューラー

スケジューリングに対する取り組みは現在も続いており、パフォーマンスおよび拡張性の限界を押し上げるスケジューラーの開発が進められています。Con Kolivas は Linux での苦い経験に思いとどまることなく、Linux 用の別のスケジューラーを開発しました。そのスケジューラーの頭字語は挑発的にも BFS です。NUMA システムならびにモバイル機器でのパフォーマンスに優れていることが報告されたこのスケジューラーは、Android オペレーティング・システムから派生したオペレーティング・システムに導入されることとなりました。


さらに詳しく調べてください

Linux で常に変わらないものがあるとしたら、それは、変化は避けられないということです。現在、CFS は Linux カーネル 2.6 のスケジューラーとなっていますが、今後は別の新しいスケジューラーや、静的または動的に起動できるスケジューラー一式に置き換えられる可能性も考えられます。さらに CFS、RSDL、そしてカーネル内部のプロセスには不可解な部分もありますが、Kolivas と Molnar 両氏の取り組みにより、2.6 カーネルのタスク・スケジューリングでは今までにない公平性が実現されていることは確かです。

参考文献

学ぶために

  • 赤黒木 (symmetric binary B-tree) は、Rudolf Bayer によって発明された平衡木です。これは非常に便利なツリー表現で、挿入・検索・削除などの操作にかかる最大の時間を明確に表します。連想配列を含め、赤黒木は、さまざまなアプリケーションで使用されています。
  • デスクトップ・オペレーティング・システムのスケジューラーからリアルタイム・スケジューラー、そして組み込みオペレーティング・システム・スケジューラーに至るまで、タスク・スケジューリングはオペレーティング・システムの設計にとって重要な側面です。Martin C. Rinard のオペレーティング・システムに関する講義のノートに、プロセッサー・スケジューリングの要点が簡潔にまとめられています。
  • Big-O 記法は、関数の制限的な振る舞いをわかりやすく記述するのに便利です。このウィキペディアの記事には優れた情報と併せ、便利な関数クラスのリストも記載されています。
  • Linux スケジューラーの内側」(developerWorks、2006年6月) を読むと、Linux O(1) スケジューラーの詳細がわかります。
  • Con Kolivas はここしばらく、新しい実験的 Linux スケジューラーに取り組んでいます。Staircase Process SchedulerRotating Staircase Deadline Scheduler を含め、公平なスケジュールが可能であることを最終的に証明した彼のスケジューラーについて詳しく学んでください。
  • Avinesh Kumar が、CFS とその他の新しくリリースされた機能をわかりやすく説明している記事、「Completely Fair Scheduler によるマルチプロセッシング」(developerWorks、2008年1月) を読んでください。
  • 人生には常にドラマがあります。CFS 開発の舞台裏を知るには、Linux カーネル・メーリング・リストの一連の投稿に目をとおしてください。これらの投稿のなかには、Con Kolivas (CFS の中核的概念を実装する RSDL パッチを導入した人物) や Ingo Molnar (CFS のコード管理者で、最初にこのスケジューラーを背後で支える概念が却下されたのち、独自のスケジューラー・バージョンを導入した人物) から寄せられたものもあります。真実は中間あたりに存在するのが常ですが、Kerneltrap によるこの興味深い記事が、オープンソース開発の別の側面を明らかにします。
  • developerWorks Linux ゾーンに豊富に揃った Linux 開発者向けの資料を調べてください。記事とチュートリアルの人気ランキングも要チェックです。
  • developerWorks に掲載されているすべての「Linux のヒント」シリーズの記事と Linux チュートリアルを参照してください。
  • developerWorks の Technical events and webcasts で最新情報を入手してください。

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

  • 1 つの選択肢として、Con Kolivas による BFS スケジューラーを Linux デスクトップ・システムおよび小型モバイル機器のパッチとして使用することもできます。Kolivas が BFS という頭字語 (その名前を呼んではいけないあのスケジューラー) を選んだわけは、スケジューラーに莫大な数のタスクをサポートさせるのは素晴らしいことである一方、適度な能力のハードウェアに組み込まれたスケジュールを不利にするべきではないという事実に注目を集めたかったからです。
  • developerWorks から直接ダウンロードできる IBM 試用版ソフトウェアを使用して、Linux で次の開発プロジェクトを構築してください。

議論するために

  • My developerWorks コミュニティーに加わってください。自分個人のプロファイルとカスタム・ホーム・ページを作成して、自分の興味に合わせて developerWorks をカスタマイズしたり、他の developerWorks ユーザーと対話したりすることができます。

コメント

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=464020
ArticleTitle=Linux カーネル 2.6 Completely Fair Scheduler の内側
publish-date=12152009