![閉じる [x]](http://dw1.s81c.com/i/c.gif){kind=small}
2.6.23 カーネルのスケジューラーは、他のスケジューリング・モジュールがモジュール構成のスケジューラー・コアと並行動作するための手段を提供しています。(この場合の「モジュール構成」とは、このスケジューラーがローダブル・モジュールに分解できるという意味ではなく、コード自体がモジュール構成になっているという意味です。) スケジューラーがどのように動作するかに関しては、developerWorks の記事「Linux スケジューラーの内側」を読んでください (この記事の最後の「参考文献」にリンクがあります。)
この最新のスケジューラーに導入された主な特徴としては、以下のものを挙げることができます。
- モジュール構成のスケジューラー
- CFS (Completely Fair Scheduler)
- CFS グループ・スケジューリング
スケジューリング・クラスの導入によって、コア・スケジューラーは非常に拡張性に富んだものになっています。これらのスケジューリング・クラス (スケジューラー・モジュール) はスケジューリング・ポリシーをカプセル化します。そのスケジューリング・ポリシーは、このコア・スケジューラーによってモジュール化されますが、(プラグ可能 CPU スケジューラー・フレームワークのように) スケジューラー自体がモジュール化されているわけではありません (プラグ可能 CPU スケジューラー・フレームワークでは、カーネルのビルド時にデフォルトのスケジューラーを選択することができ、またブート時にカーネルに引数を渡すことで他の CPU スケジューラーを使うことができます)。
Completely Fair Scheduler は、CPU 時間を「最も深刻に必要とする」タスクを実行しようとします。これによって、すべてのプロセスが公平に CPU を使用するように保証することができます。CFS は、あるタスクが「非常に」短時間しかスリープしない場合には、そのタスクをスリープ中とは見なしません。短時間しかスリープしないタスクは少し余分に CPU 時間を利用できるかもしれませんが、スリープしなかった場合の時間以上には利用することはできません。
あるマシン上でジョブを実行している 2 人のユーザー A と B がいる場合の例を考えてみてください。ユーザー A は 2 つのジョブしか実行していませんが、ユーザー B は 48 のジョブを実行しています。CFS はグループ・スケジューリングによって、そのシステムで実行中の 50 のジョブすべてを公平に扱うのではなく、ユーザー A と B を公平に扱うことができます。どちらのユーザーも、それぞれ 50% ずつの割合で CPU 時間を利用することができます。B は 50% の CPU 時間を使って 48 のジョブを実行しますが、A に与えられる 50% の CPU 時間を奪うことはできません。
CFS スケジューリング・モジュール (kernel/sched_fair.c に実装されています) は、SCHED_NORMAL と SCHED_BATCH、そして SCHED_IDLE というスケジューリング・ポリシーに対して使われます。SCHED_RR ポリシーと SCHED_FIFO ポリシーには、(kernel/sched_rt.c に実装されている) リアルタイム・スケジューリング・モジュールが使われます。
こうした変更は、以下のような理由から行われました。
- サーバーに対してもデスクトップに対しても適切なスケジューリングを実現するため。
- 要求されていた新しい機能を提供するため。
- ヒューリスティックを改善するため。標準的なスケジューラーに使われていたヒューリスティックの場合には、ある種の攻撃が容易に実行できてしまいました。また、ヒューリスティックがシナリオの判断を誤った場合に、望ましくない動作が起こる可能性がありました。
対話動作における待ち時間の目標を犠牲にせずに「公平なスケジューリング」を実現できることを実証できたのは、Con Kolivas のおかげです。彼は、プロセスの対話動作の予測に使われる複雑なヒューリスティックをまったく使わずに公平性が実現できることを、RSDL/SD スケジューラーによって実証したのです。
CFS は優先度の配列も、標準的なスケジューラーにある、配列切り替え用の成果物も使用していません。RSDL と CFS との間には、以下のようないくつかの重要な違いがあります。
- RSDL は「厳密な公平性」を基に動作しますが、CFS は対話型プロセスにおけるスリープ時間の長さを考慮します。そのため、短時間しかスリープしないプロセスは、CPU 時間を少し長めに使うことができます。
- RSDL は標準的なスケジューラーと同じように優先度キューを使いますが、CFS は優先度キューを使いません。
- RSDL と標準的なスケジューラーは配列切り替え用の成果物の影響を受けますが、CFS は影響されません。
CFS はスリープ時間を追跡せず、またヒューリスティックを使って対話型タスクを識別することはありません。CFS が行うのは、CPU 上で実行可能なプロセス数によって決まる一定の時間内に、確実にすべてのプロセスが CPU を公平に共有できるようにすることだけです。
CFS は各 CPU に対して、時間で順位付けされた赤黒木を使います。
木による方法が適切な理由は下記のとおりです。
- 赤黒木は常に平衡しています。
- 赤黒木は二分木であるため、参照操作の時間計算量は対数関数で表されます。しかし左端以外の参照はまず行われることはなく、また左端のノード・ポインターは常にキャッシュされます。
- 赤黒木では、操作にかかる時間は大部分の操作で O(log n) ですが、これまでのスケジューラーは O(1) を採用し、優先度の数を固定して優先度の配列を使っていました。O(log n) の振る舞いは O(1) と比べるとある程度低速ですが、タスクの数が非常に多くなると、その違いはごくわずかになります。Molnar が木による方法を採用してから最初にテストしたのは、この点です。
- 赤黒木は内部ストレージを使って実装することができます。つまりデータ構造を維持するために外部ストレージを割り当てる必要がまったくありません。
では、この新しいスケジューラーを実装するための鍵となるデータ構造をいくつか見てみましょう。
CFS は struct prio_array を廃止し、スケジューリング・エンティティーとスケジューリング・クラスを導入しています (それぞれ struct sched_entity と struct sched_class として定義されています)。従って、task_struct は他の 2 つの構造体、sched_entity と sched_class に関する情報を含んでいます。
リスト 1. 構造体 task_struct
struct task_struct { /* Defined in 2.6.23:/usr/include/linux/sched.h */
....
- struct prio_array *array;
+ struct sched_entity se;
+ struct sched_class *sched_class;
....
....
};
|
この構造体は、ある 1 つのタスク、あるいはタスク・グループのスケジューリング・ジョブを実際に行う上で十分な情報を保持しており、グループ・スケジューリングを実装するために使われます。スケジューリング・エンティティーはプロセスと関連付けられていない場合があります。
リスト 2. 構造体 sched_entity
struct sched_entity { /* Defined in 2.6.23:/usr/include/linux/sched.h */
long wait_runtime; /* Amount of time the entity must run to become completely */
/* fair and balanced.*/
s64 fair_key;
struct load_weight load; /* for load-balancing */
struct rb_node run_node; /* To be part of Red-black tree data structure */
unsigned int on_rq;
....
};
|
このスケジューリング・クラスは、コア・スケジューラーを補助する一連のモジュールのようなものです。各スケジューラー・モジュールは struct sched_class の指示に従って一連の関数を実装する必要があります。
リスト 3. 構造体 sched_class
struct sched_class { /* Defined in 2.6.23:/usr/include/linux/sched.h */
struct sched_class *next;
void (*enqueue_task) (struct rq *rq, struct task_struct *p, int wakeup);
void (*dequeue_task) (struct rq *rq, struct task_struct *p, int sleep);
void (*yield_task) (struct rq *rq, struct task_struct *p);
void (*check_preempt_curr) (struct rq *rq, struct task_struct *p);
struct task_struct * (*pick_next_task) (struct rq *rq);
void (*put_prev_task) (struct rq *rq, struct task_struct *p);
unsigned long (*load_balance) (struct rq *this_rq, int this_cpu,
struct rq *busiest,
unsigned long max_nr_move, unsigned long max_load_move,
struct sched_domain *sd, enum cpu_idle_type idle,
int *all_pinned, int *this_best_prio);
void (*set_curr_task) (struct rq *rq);
void (*task_tick) (struct rq *rq, struct task_struct *p);
void (*task_new) (struct rq *rq, struct task_struct *p);
};
|
リスト 3 の中にある関数をいくつか調べてみましょう。
-
enqueue_task: あるタスクが実行可能状態に入ると、この関数が呼び出されます。この関数はスケジューリング・エンティティー (プロセス) を赤黒木に入れ、nr_running 変数をインクリメントします。 -
dequeue_task: あるタスクがもはや実行可能ではなくなると、対応するスケジューリング・エンティティーを赤黒木から除くために、この関数が呼び出されます。この関数は nr_running 変数をデクリメントします。 -
yield_task: この関数は、compat_yield sysctl がオンでない限り、基本的に単なるデキューであり、後にエンキューが続きます。compat_yield sysctl がオンの場合には、この関数はスケジューリング・エンティティーを赤黒木の右側の端に置きます。 -
check_preempt_curr: この関数は、現在実行中のタスクをプリエンプトできるかどうかをチェックします。CFS スケジューラー・モジュールは、実行中のタスクを実際にプリエンプトする前に公平性に関するテストを行います。この結果を基にウェイクアップ・プリエンプションが行われます。 -
pick_next_task: この関数は、次に実行する候補として最も適切なプロセスを選択します。 -
load_balance: 各スケジューラー・モジュールは、そのモジュールの load_balance ルーチンの中で呼び出されるイテレーターを実装するために、load_balance_start() と load_balance_next() という 1 対の関数を実装します。コア・スケジューラーはこの方法を使って、スケジューラー・モジュールによって管理されるプロセスのロード・バランシングを行います。 -
set_curr_task: この関数は、あるタスクがそのタスクのスケジューリング・クラスを変更したり、タスク・グループを変更したりする場合に呼び出されます。 -
task_tick: この関数はほとんどの場合、タイムティック関数から呼び出されます。その呼び出しによってプロセスの切り替えが行われることもあります。これにより、プリエンプションの実行が推進されます。 -
task_new: コア・スケジューラーはスケジューリング・モジュールに対して、新しいタスクを起動するための機会を与えます。CFS スケジューリング・モジュールはその機会を利用してグループ・スケジューリングを行いますが、リアルタイム・タスク用のスケジューリング・モジュールはその機会を利用しません。
各ランキューには、そのランキューに関連する赤黒木についての情報を保持する構造体があります。
リスト 4. 構造体 cfs_rq
struct cfs_rq {/* Defined in 2.6.23:kernel/sched.c */
struct load_weight load;
unsigned long nr_running;
s64 fair_clock; /* runqueue wide global clock */
u64 exec_clock;
s64 wait_runtime;
u64 sleeper_bonus;
unsigned long wait_runtime_overruns, wait_runtime_underruns;
struct rb_root tasks_timeline; /* Points to the root of the rb-tree*/
struct rb_node *rb_leftmost; /* Points to most eligible task to give the CPU */
struct rb_node *rb_load_balance_curr;
#ifdef CONFIG_FAIR_GROUP_SCHED
struct sched_entity *curr; /* Currently running entity */
struct rq *rq; /* cpu runqueue to which this cfs_rq is attached */
...
...
#endif
};
|
CFS スケジューラーは、公平性を保証するための融和策を使用しています。あるタスクがランキューに入ると、現在の時刻が記録され、そのプロセスが CPU にスケジューリングされるのを待つ間、そのタスクの wait_runtime 値は現在ランキューの中にあるプロセスの数によって決まる量だけインクリメントされます。これらの計算を行う間、さまざまなタスクの優先度の値も考慮されます。このタスクが CPU にスケジューリングされると、そのタスクの wait_runtime 値はデクリメントを開始し、この値が、他のタスクが赤黒木において新たに最も左側のタスクとなるレベルにまで低下すると、新しいタスクがプリエンプトされます。こうすることで、CFS は、wait_runtime がゼロである理想的な状態にしようとするのです。
CFS はタスクの実行時間の管理を、ランキュー全体にまたがるクロック (fair_clock (cfs_rq->fair_clock) と呼ばれます) を基準に行います。このクロックは、1 つのタスクに対して理想的なタイミングで動作するように、リアルタイム・クロック (壁時計時刻) の何分の 1 かで実行されます。
例えば実行可能なタスクが 4 つある場合、fair_clock は壁時計時刻の 4 分の 1 の時間ごとに増加します。すると各タスクは、この理想的なタイミングを基準に動作します。これは、時分割によるマルチタスクが量子化の性質を持つ結果です。つまり、ある任意の時刻に実行できるのは 1 つのタスクのみであり、従って他のプロセスは wait_runtime という「借り」を積み上げます。そして、いったんあるタスクがスケジューリングされると、そのタスクはそのタスクの「借り」に追いつきます (そして少し余分に「借り」を返します。なぜなら fair_clock は追いつくための期間中もティックを止めないからです)。
タスクを重みづけすることで、優先度が導入されています。例えば、2 つのタスクがあるとします。一方は他方の 2 倍の CPU 時間を消費するとすると、2:1 という比になります。この数式が変更され、0.5 の重みを持つタスクには 2 倍の速さで時間が経過するように見えるようになります。
タスクは fair_clock を基準にして木にエンキューされます。
タイム・スライスに関しては、CFS ではタイム・スライスを使わないこと、使うとしてもこれまでの使い方とは異なることを覚えておいてください。CFS でのタイム・スライスは可変長であり、動的に決定されます。
ロード・バランサーに関しては、スケジューリング・モジュールがイテレーターを実装し、そのスケジューリング・モジュールが管理するすべてのタスクを、そのイテレーターを使ってウォークスルーして、ロード・バランシングを行います。
実行時にスケジューラーを調整するために導入された重要な sysctls は以下のとおりです (名前の終わりに ns が付いているのは単位がナノ秒であることを表しています)。
-
sched_latency_ns: CPU バウンドのタスクにとってターゲットとなるプリエンプションまでの待ち時間です。 -
sched_batch_wakeup_granularity_ns:SCHED_BATCHに対するウェイクアップの粒度です。 -
sched_wakeup_granularity_ns: SCHED_OTHER に対するウェイクアップの粒度です。 -
sched_compat_yield: CFS がこれをどのように変化させるかによって、sched_yield() の動作に大きく依存するアプリケーションはパフォーマンスが変化する可能性があります。そのため、sysctl をオンするようにお勧めします。 -
sched_child_runs_first: fork により生成される子プロセスが fork の次にスケジューリングされます。これはデフォルトです。0 に設定されている場合、その親プロセスが fork の次にスケジューリングされます。 -
sched_min_granularity_ns: CPU バウンドのタスクに対するプリエンプションの最小粒度です。 -
sched_features: デバッグに関連するさまざまな機能の情報を含んでいます。 -
sched_stat_granularity_ns: スケジューラーの統計を収集するための粒度です。
システムのランタイム・パラメーターの標準的な値は以下のとおりです。
リスト 5: ランタイム・パラメーターの標準的な値
[root@dodge ~]# sysctl -A|grep "sched" | grep -v "domain" kernel.sched_min_granularity_ns = 4000000 kernel.sched_latency_ns = 40000000 kernel.sched_wakeup_granularity_ns = 2000000 kernel.sched_batch_wakeup_granularity_ns = 25000000 kernel.sched_stat_granularity_ns = 0 kernel.sched_runtime_limit_ns = 40000000 kernel.sched_child_runs_first = 1 kernel.sched_features = 29 kernel.sched_compat_yield = 0 [root@dodge ~]# |
新しいスケジューラーには非常に良いデバッグ・インターフェースが用意されており、またランタイム統計情報も提供されています (それぞれ kernel/sched_debug.c と kernel/sched_stats.h に実装されています)。スケジューラーに対するランタイム統計とデバッグ情報を提供するために、以下のようないくつかのファイルが proc 疑似ファイルシステムに追加されています。
-
/proc/sched_debug: 利用可能な CPU すべてに関するランタイム・スケジューラーのパラメーターや CFS 統計、ランキュー情報の現在の値を表示します。この proc ファイルが読み取られると、sched_debug.c の中に定義されている関数 sched_debug_show() が呼び出されます。 -
/proc/schedstat: あるランキューに限定した統計を表示し、また接続されているすべての CPU に対する SMP システムのドメインに限定した統計も表示します。kernel/sched_stats.h の中で定義される関数 show_schedstat() は、この proc エントリーに対する読み取り動作を扱います。 -
/proc/[PID]/sched: 関連するスケジューリング・エンティティーの情報を表示します。kernel/sched_debug.c の中で定義される関数 proc_sched_show_task() は、このファイルが読み取られると呼び出されます。
2.6.24 リリースで予定されている変更としては、どんなものがあるでしょう。例えば、グローバル・クロック (fair_clock) を追跡する代わりに、タスク同士がお互いを追跡します。タスク (スケジューリング・エンティティー) ごとのクロックである vruntime (つまり、wall_time/task_weight)が導入される予定であり、概算平均によって新しいタスクのクロックが初期化されます。
他の重要な変更によって、主要なデータ構造体が影響を受けます。以下に示すのは struct sched_entity に予定されている変更です。
リスト 6. 2.6.24 で構造体 sched_entity に予定されている変更
struct sched_entity { /* Defined in /usr/include/linux/sched.h */
- long wait_runtime;
- s64 fair_key;
+ u64 vruntime;
- u64 wait_start_fair;
- u64 sleep_start_fair;
...
...
}
|
以下に示すのは struct cfs_rq に予定されている変更です。
リスト 7. 2.6.24 で構造体 cfs_rq に予定されている変更
struct cfs_rq { /* Defined in kernel/sched.c */
- s64 fair_clock;
- s64 wait_runtime;
- u64 sleeper_bonus;
- unsigned long wait_runtime_overruns, wait_runtime_underruns;
+ u64 min_vruntime;
+ struct sched_entity *curr;
+#ifdef CONFIG_FAIR_GROUP_SCHED
...
+ struct task_group *tg; /* group that "owns" this runqueue */
...
#endif
};
|
タスクをグループ化するために、以下に示す新しい構造体が導入されています。
リスト 8. 新しく追加された構造体 task_group
struct task_group { /* Defined in kernel/sched.c */
#ifdef CONFIG_FAIR_CGROUP_SCHED
struct cgroup_subsys_state css;
#endif
/* schedulable entities of this group on each cpu */
struct sched_entity **se;
/* runqueue "owned" by this group on each cpu */
struct cfs_rq **cfs_rq;
unsigned long shares;
/* spinlock to serialize modification to shares */
spinlock_t lock;
struct rcu_head rcu;
};
|
各タスクはそのタスクの実行時間を追跡し、その値に基づいてタスクがエンキューされます。つまり、最も実行時間の短いタスクが最も左側のタスクになるということです。この場合も、時間を重みづけすることで優先度が実現されています。各タスクは以下の期間中に、正確に 1 度だけスケジューリングされるようになります。
sched_period = (nr_running > sched_nr_latency) ? sysctl_sched_latency : ((nr_running * sysctl_sched_latency) / sched_nr_latency)
ここで sched_nr_latency =
(sysctl_sched_latency / sysctl_sched_min_granularity) です。つまり、latency_nr を超える実行可能タスクがあると、その数に合わせてリニアにスケジューリング期間が拡張されます。sched_fair.c の中で定義されている sched_slice() で、こうした計算を行います。
そのため、実行可能な各タスクが sched_slice() で計算された時間だけ実行されると、合計で sched_period 時間が使われたことになり、それぞれのタスクは、そのタスクの重みに比例した時間だけ実行したことになります。さらに、どの時点でも、CFS はあらかじめ sched_period の期間だけ実行すると約束します。これは、最後にスケジューリングされたタスクも、やはり sched_period のウィンドウ内で実行されるからです。
そのため、新しいタスクが実行可能になると、そのタスクが実行されるタイミングに関して厳密な要求がなされます。このタスクは、他のすべてのタスクが実行を終えるまで実行することができません。そうでないと、他のタスクに対する約束が破られてしまいます。しかしこのタスクは実際にエンキューされるため、ランキューに対する追加の重みによって他のすべてのタスクのタイム・スライスは短縮され、sched_priod の最後に、この新しいタスクが必要とするサイズとまったく同じサイズでタイム・スロットが開放されます。そしてこの新しいタスクはそこに置かれます。
2.6.24 では、タスクに対してのみならず、ユーザーあるいはグループに対しても公平にスケジューリングされるよう、スケジューラーを調整できるようになります。また、タスクをグループにまとめ、エンティティーを構成することができます。するとスケジューラーは、これらのエンティティーを公平に扱い、エンティティーの中にあるタスクを公平に扱います。この機能を有効するには、カーネルをビルドする際に CONFIG_FAIR_GROUP_SCHED を選択する必要があります。現時点では、SCHED_NORMAL タスクと SCHED_BATCH タスクのみをグループ化することができます。
タスクをグループ化する方法として、以下の情報に基づいてグループ化を行う相互排他的な 2 つの方法があります。
- ユーザー ID による方法
- cgroup 疑似ファイルシステムによる方法。この方法では、管理者が必要に応じてグループを作成することができます。詳細に関しては、カーネルのソース・ドキュメンテーションのディレクトリーにあるファイル cgroups.txt を読んでください。
カーネル構成パラメーター CONFIG_FAIR_USER_SCHED と CONFIG_FAIR_CGROUP_SCHED によって、このグループ化の方法を選択することができます。
新しいスケジューラーは、スケジューリング・クラスを導入することによってスケジューリング機能を拡張しており、またスケジュール統計を改善することでデバッグを単純化しています。CFS は、3D ゲームなどを始めとする、スレッドを多用するアプリケーションのテストで高い評価を受けています。
CFS スケジューラーの開発に大きく貢献し、また忙しいスケジュールの中、この記事を改善するためのコメントや助言に時間を割いていただいた Peter Zijlstra 氏に感謝いたします。そして、CFS のグループ・スケジューリングに関して素晴らしい仕事をしてくださった Srivatsa Vaddagiri 氏と、RSDL の作成者 Con Kolivas 氏に感謝いたします。また、この記事に関心を示してくださった Linux スケジューラーのメンテナー、Ingo Molnar 氏にも感謝いたします。
学ぶために
- 「Linux スケジューラーの内側」(developerWorks、2006年6月) は Linux 2.6 のスケジューラーの動作を解説しています。
- 「Linux 2.6へ: 次期新カーネルの動作を見る」(developerWorks、2003年9月) は、Linux 2.6 とそのスケジューラーを、技術的な観点と歴史的な観点から解説しています。
- 「Linux と対称型マルチプロセッシング」(developerWorks、2007年3月) は 2.6 カーネルと対称型マルチプロセッシングの話題を紹介しています。
- 「プロセッサー・アフィニティーの管理」(developerWorks、2005年9月) は、Linux 2.6 のスケジューラーが、(厳密なものであれ緩やかなものであれ) CPU アフィニティーをどう扱うかを少し知っていると、より良いユーザー空間アプリケーションの設計に役立つことを解説しています。
-
Ingo Molnar による git tree は 2.6.24 で計画されている変更のタイムラインを示しています。
-
developerWorks の Linux ゾーンには他にも Linux 開発者に役立つリソースが豊富に用意されています。最も人気のあった記事やチュートリアルのリストもご覧ください。
- developerWorks には Linux に関するヒントやチュートリアルが豊富に用意されています。
-
developerWorks technical events and Webcasts で最新情報を入手してください。
製品や技術を入手するために
- 2枚組 DVD セット、SEK for Linux をご注文ください。DB2® や Lotus®、Rational®、Tivoli®、WebSphere® など、Linux 用の最新 IBM ソフトウェアの試用版が含まれています。
- developerWorks から直接ダウンロードできる IBM trial software を利用して皆さんの次期 Linux プロジェクトを構築してください。
議論するために
- 開発者用のブログやフォーラム、ポッドキャスト、そして新しい developerWorks spaces でのコミュニティーの話題などを通して、developerWorks のコミュニティーに加わってください。
Avinesh Kumar は、インドの Pune にある IBM Software Labs のAndrew File System Team で働くシステム・ソフトウェア・エンジニアです。Avinesh は、ダンプやクラッシュのほか、Linux、AIX、および Solaris プラットフォームで報告されたバグをカーネル・レベルおよびユーザー・レベルでデバッグしています。彼は、University of Pune のコンピューター・サイエンス学部で MCA を取得しています。Linux の熱狂的な支持者である Avinesh は、自分の Fedora Core 6 コンピューターに入っている Linux カーネルを研究しながら余暇を過ごしています。
