昨年10月にリリースされたLinuxカーネル2.6.23では、従来のO(1)スケジューラ(Order One Scheduler)を置き換え、新しいスケジューラ「CFS (Completely Fair Scheduler) 」が組み込まれた。9日に行われた「第8回 The Linux Foundation Japan Symposium」ではカーネル開発者の一人であるThomas Gleixner氏が来日し、CFSの基本概念や最新動向の説明を行った。

Thomas Gleixner氏

従来のLinuxカーネルではIngo Molna氏が開発したO(1)と呼ばれるスケジューラが使われてきた。O(1)スケジューラでは、実行可能なプロセスが優先度別に用意されたアクティブ・キューに登録され、優先度の高いキューのプロセスから順番に実行されていく。そのため実行するべきプロセスが必ず1つに決まるという点が大きな特徴であり、名前の由来にもなっている。

O(1)スケジューラでは優先度を-20～+19のナイス値 (Nice Value) によって決定しており、ナイス値が小さいほど優先度は高くなる。それに加えてリアルタイムプロセスに対しては、ナイス値-20よりも優先度の高いリアルタイム優先度が1～99 (大きい方が優先度が高い) の間で割り当てられる。このO(1)スケジューラにおける問題点をGleixner氏は次のように指摘する。

  • 優先度別にキューがあるため公平性の確保が難しい
  • 対話型タスクの扱いが経験則的な手法で行われている
  • より高いレベルのナイス値が枯渇しないよう、カーネルがナイス値の調整を行う
  • CPUのタイムシェアの計算が困難

上記の問題のうち、特に対話型タスクの扱いに関する問題にフォーカスしたスケジューラとしてCon Kolvias氏の開発したStaircase Schedulerがある。Staircase Schedulerでは経験則的なコードを廃止し、プロセスがCPUバウンドなのかI/Oバウンドなのかに関わらず"公平"に扱う。

2.6.23に取り込まれたCFSはこのStaircase Schedulerが持つ公平なスケジューリングのための基本設計要素を元にして、O(1)の作者であるIngo Molna氏が開発したもの。O(1)をベースとしてはおらず、完全に新しくデザインされたものである。

CFSではリアルタイムタスクと通常のタスク、そしてアイドルをそれぞれ異なるアルゴリズムでスケジューリングする。それぞれ「rt-sched-class」「fair-sched-class」「idle-sched-class」というスケジューラ・クラスとして実装されており、rt-sched-classでは優先度をO(1)に基づいて管理するのに対し、fair-sched-classではCPU時間で重み付けされた赤黒木によって優先度を管理するという。

使用するスケジューラ・クラスの決定アルゴリズムは非常に単純で、現在のクラスに実行可能なタスクがあればそれを処理し、無くなれば次のクラスに移動するというもの。これをrt→fair→idleの順番で繰り返す。したがってスケジューラ・クラスの決定はO(1)時間で行われる。

CFSの肝となるのはfair-sched-classにおけるスケジューリングである。Gleixner氏によれば、これはネットワーク・パケットを扱うためのキュー・アルゴリズムに似たものだという。前述のように、タスクはCPU時間で重み付けされた赤黒木によって管理される。fair-sched-classではCPU時間を多く必要とするタスクに優先的にリソースを割り当てる。また、待ち時間が長くなるほど優先的に選択されるようになる。CFSではこれによって公平性を確保しているという。また、タスクの実行時間管理はナノ秒ベースのアカウンティングによって行われ、カーネルのtickには依存しないという。

fair-sched-classの場合、タスクのインサーションに要する時間は赤黒木の操作に要する時間なのでO(log(N))である。これはO(1)に比べると低速だが、タスクの数が非常に多い場合にはその差は極めて小さくなる。

O(1)スケジューラではナイス値はタイムスライスに依存していたが、fair-sched-classではタイムスライスとは独立して決定される。CFSにおけるタイムスライスは従来のものとは異なり、動的に決定されるという。ナイス値は実行時間の重み付けに影響し、ナイス値が1下がるごとに重みが10%加算されるようになっているという。

対話型タスクに関する公平性については、スリープ時間を考慮することで解決しているとのこと。タスクはスリープ時間が長くなるほど優先的に実行される。したがって入力待ちを必要とするタスクなどは、その時間が長ければ長いほどウェイクアップ・イベントに対して素早く反応できるようになるという仕組みだそうだ。

その他、Gleixner氏からはカーネル2.6.25でマージされたリアルタイム・グループ・スケジューリングに関する説明も行われた。リアルタイム・グループ・スケジューリングでは、タスクはUIDかまたはユーザ定義(cgroup)のグループ単位で管理される。CPU時間の割り当てはグループ毎に管理されるため、この仕組みによってユーザ間での公平性を保つことができるようになるという。またリアルタイム・タスクがCPUを占有し続けてしまうようなことが無いよう、割り当てるCPU時間に上限を設定できるようになったとのことだ。

上記以外に、現在はCFSとは別にEDF (Early Deadline First) に基づくスケジューラの開発も進められているという。これは最も実行期限(デッドライン)の早いタスクから優先的に実行するという考え方に基づくもの。基本的な実装は完了しているが、優先度の継承などに関してはまだ解決できておらず、アイデアを募集しているとの話だ。