sched-design-CFS.txtの和訳

linux OS

ぼーっと読んでいてもわかるようなわからんような、なので訳してみれば全部読まざるを得ないだろうと思ったんだけどやっぱり面倒で、結局Excite翻訳したものを手直ししただけ。
しかも、機械語翻訳がかなり残ったままの超適当訳です。クオリティはかなり低いです。
ところどころ訳してないところあったりもします。
直すべし！が有ったら突っ込んでください。いや全部か。

原文：http://lxr.linux.no/linux+v2.6.31/Documentation/scheduler/sched-design-CFS.txt


※追記：この文章よりもkosaki先生による記事の方が正確であるとの事ですので、そちらをまずは読んだ方が良さそうです↓
帰ってきたCon Kolivas、大論争を呼ぶの巻（3/3） − ＠IT

※追記２：takeokaさんより修正の指摘をいただいたので少し直しました。

=============
CFSスケジューラ
=============

1. 概観

CFSは、「Completely Fair Scheduler（完全に公平なスケジューラ）」という意味で、インゴ・モルナーによって実装され、リナックス2.6.23でマージされた新しいプロセススケジューラです。 これは前のバニラスケジューラのSCHED_OTHERインタラクティブ性コードを置き換えます。

ただ一行の文にCFSのデザインの80%をまとめることができます: CFSは実際のハードウェアの上で基本的に「理想的で、精密なマルチタスキングCPU」をモデル化します。

「理想的なマルチタスキングCPU」は１００％のCPU実行時間を正確に各タスクに等しく配分して平行に走らせることの出来るCPUです(実在しません)。
それぞれのプロセスは1/nr_runningの速度で動作します。
例えば、動作中の2つのタスクがあれば、50%のCPU実行時間でそれぞれを同時に走らせる事が出来ます。

実際のハードウェアの上では一度に一つのタスクしか走らせることができないので、私たちは「バーチャルランタイム」の概念を紹介しなければなりません。
タスクのバーチャルランタイムは、次のタイムスライスが上述の「理想的なマルチタスキングCPU」上でいつ実行を開始するのかを指定します。
実際には、タスクのバーチャルランタイムは、走行中のタスクの総数で正規化された実際の実行時間です。

2. わずかな実現の詳細

CFSでは、バーチャルランタイムは、1タスクあたりのp->se.vruntime(nanosec-ユニット)値で表現されて、追跡されます。 これにより、タイムスタンプ、そして、タスクが得るべきであった「予想されたCPU時間」を測定する事が可能になります。

（詳細: 「理想的な」ハードウェアの上では、すべてのタスクが、いつでも同じp->se.vruntime値を持っているでしょう。
つまり、全てのタスクは平行に実行可能であり、決して理想的なCPU時間分配からバランスが崩れる事はないでしょう。）

CFSのタスク選択論理はこのp->se.vruntime値に基づいています。
そして、その結果、それは非常にシンプルです:
それは最も小さいp->se.vruntime値(すなわち、今までのところの最少の時間しか実行されていないタスク)を持ったタスクをいつも走らせようとします。
CFSは可能な限り常にCPU時間の分配を「理想的なマルチタスキングCPU」に近づけようとします。

CFSのデザインの残りの部分、例えばniceレベルやマルチプロセッシング、改良されたアルゴリズム、などはこのシンプルなコンセプトから抜け落ちた部分を補っているに過ぎません。

3. RBTREE

CFSのデザインはかなり急進的です:
runqueuesに古いデータ構造を使用せず、CPU時間でソートされたrbtreeで今後のタスク実行のタイムラインを構成します。
その結果、"array switch"構造を全く持っていません(前のバニラスケジューラとRSDL/SDの両方が利用していた仕組み)。

また、CFSはrq->cfs.min_vruntimeの値も管理します。
これは、runqueueのすべてのタスクの中から最も小さいvruntimeを追跡する値で、単調に増加します。
システムによって行われた仕事の総量は、min_vruntimeを使用することで追跡されます。
その値は、新たにアクティベートされたentityをできるだけツリーの左側に置くのに使用されます。

runqueue上で走っているタスクの総数はrq->cfs.loadの値を通して説明されます。
(その値は、runqueueにキューされているタスクのweightの合計です)。

CFSは時間でソートされたrbtreeを維持します。
そこでは、全ての実行可能なタスクがp->se.vruntimeをキーにしてソートされています（there is a subtraction using rq->cfs.min_vruntime to account for possible wraparounds）。
CFSはこのtreeから「一番左」のタスクを選んで、がんばります(sticks to it)。

システムが前方に進歩をするとき、treeの右へ右へと実行されたタスクを入れます。
ゆっくり、しかし、確実に、あらゆるタスクが「一番左のタスク」になって、その結果、決定論的な時間以内にCPUに乗る機会を与えます。

まとめて、CFSはこのように働いています:
それはタスクをちょっとだけ走らせ、そして、タスクスケジュールの時に（またはスケジューラティックが発生した時に）タスクのCPU使用量は「計算されます」：
物理CPUで費やした（短い）時間をp->se.vruntimeに加えます。

p->se.vruntimeが十分に大きくなると他のタスクがCFSが管理する時間でソートされたrbtree上で「一番左のタスク」になり(タスクをオーバースケジュールせず、そしてキャッシュをゴミにしないために、最左タスクから相対的に"粒度"距離だけの、小さな量を加える)、新しい一番左のタスクがpickされてカレントタスクはプリエンプトされます。

4. CFSのいくつかの特徴

CFSはナノ秒粒度での計測を利用しており、jiffiesやHZなどの情報を当てにしません。
したがって、CFSスケジューラは以前のスケジューラが持っていたようなタイムスライスの概念は持っておらず、またヒューリスティックスも全く用いません。

1つだけの調整可能な値があります(CONFIG_SCHED_DEBUGを有効にしなければならない):

/proc/sys/kernel/sched_min_granularity_ns

これは「デスクトップ」(すなわち、低いレイテンシ)から「サーバ」(すなわち、よいバッチ処理)ワークロードまでスケジューラを調整するのに使用できます。
デスクトップワークロードに適当な設定をデフォルトになっています。 SCHED_BATCHはCFSスケジューラモジュールでも扱われます。

このデザインのため、CFSスケジューラはスケジューラのヒューリスティックに対して存在するいずれの「攻撃」にも影響がありません: fiftyp.c、thud.c、chew.c、ring-test.c、massive_intr.cはきめ細かにすべて働いて、対話性に影響を与えないで、期待される振舞いを起こします。

CFSスケジューラには、niceレベルとSCHED_BATCHのはるかに強い取り扱いが前のバニラスケジューラよりあります: 両方のタイプのワークロードははるかに積極的に隔離されます。

SMPロードバランシングは、作りなおされ不要な部分は削除されました: runqueue-walking仮定は現在ロードバランシングコードから取り除かれ、一方、スケジューリングモジュールのイテレータは使用されています。
ロードバランシングのコードはこの結果たいへん簡単になりました。

5. スケジューリングポリシー

CFSには3つのスケジューリングポリシーが実装されています:

  • SCHED_NORMAL(伝統的にはSCHED_OTHERと呼ばれます):

通常のタスクに使用されるスケジューリングポリシー。

  • SCHED_BATCH:

通常のタスクよりもプリエンプト頻度を低くし、インタラクティビティ低下の代償を払う代わりに長く走り結果としてキャッシュをうまく使えるようにします。これはバッチ・ジョブによく合っています。

  • SCHED_IDLE:

これはnice19より弱い。
しかし、マシンをデッドロックさせるかもしれない優先度逆転問題を避けるために、
本当のアイドル・タイマ・スケジューラではありません。


SCHED_FIFO/_RRは、sched_rt.cに実装されており、POSIXの規約に従っています。
util-linux-ng2.13.1.1のコマンドchrtはSCHED_IDLE以外のすべてを設定できます。

6. スケジューリングクラス

新しいCFSスケジューラは階層を拡張するスケジューラモジュールとして「スケジューリングクラス」を導入します。
このモジュールは、スケジューリングポリシーの詳細をカプセル化しスケジューラコアからポリシーを分離します。

sched_fair.cは上で説明されたCFSスケジューラの実装です。

sched_rt.cはSCHED_FIFO及びSCHED_RRのセマンティクスを以前のバニラスケジューラが行っていたよりもシンプルな方法で実装しています。
それは100個のrunqueues(100のRT priority levelのため。前のスケジューラでは140でした)を使用します、そして、expired arrayは必要としません。

スケジューリングのクラスはsched_class構造体を通して実装されます。
構造体は関連するイベントが発生したときに呼ばなければならないフックへの関数ポインタを含みます。

これはフックの(部分的)のリストです:

  • enqueue_task(...)


タスクが実行状態に入るときに呼ばれます。
それは、スケジューリングエンティティ(タスク)をrbtreeへ入れて、nr_running変数をインクリメントします。

  • dequeue_tree(...)


タスクが実行状態でなくなった時に、対応するスケジューリングエンティティをrbtreeからはずす為この関数は呼ばれます。nr_running変数をデクリメントします。

  • yield_task(...)


この関数は基本的には単にenqueueに続いてdequeueを行います、但しcompat_yield sysctlが有効なときを除く。
その場合は、スケジュールエンティティをrbtreeの一番右端に移動します。

  • check_preempt_curr(...)

この機能は、実行可能状態に入ったタスクが、現在走っているタスクをプリエンプトするべきであるかどうかチェックします。

  • pick_next_task(...)


この機能は次に実行される資格がある最も適切なタスクを選びます。

  • set_curr_task(...)


タスクがスケジューリングクラスを変えるか、またはタスクグループを変えるときにこの関数は呼ばれます。

  • task_tick(...)


ほとんどの場合この機能はタイム・チック関数から呼ばれます。 それはプロセススイッチに通じるかもしれません。 これは走っているプリエンプションを追い立てます。

  • task_new(...)


コアスケジューラは新しいタスクスタートアップを管理する機会をスケジューリングモジュールに与えます。
CFSスケジューリングモジュールはグループスケジューリングにそれを使用します、リアルタイムのタスク向けのスケジューリングモジュールはそれを使用しませんが。

7. CFSへのグループスケジューラエクステンション

通常、スケジューラは、個々のタスクを作動させて、公正なCPU時間を各タスクに提供するように努力します。
場合によっては、タスクをグループ化して、それぞれのタスクグループに公正なCPU時間を提供するのは望ましいかもしれません。
例えば、システム上の各ユーザが持つプロセスに対してユーザ毎に公正なCPU時間を提供するのは、望ましいかもしれません。

CONFIG_GROUP_SCHEDは、ちょうどそれを達成するように努力します。 それはタスクをグループ化し、グループ単位でCPU時間を公正に分割します。

CONFIG_RT_GROUP_SCHEDは、リアルタイム(すなわち、SCHED_FIFOとSCHED_RR)のタスクをグループ化するのを可能にします。

CONFIG_FAIR_GROUP_SCHEDは、CFS(すなわち、SCHED_NORMALとSCHED_BATCH)タスクをグループ化するのを可能にします。

現在のところ、CPU帯域幅管理目的でタスクをグループ化するために、2つの(互いに排他的)のメカニズムがあります:

  • ユーザID(CONFIG_USER_SCHED)に基づくグループ化


このオプションではユーザIDによってタスクはグループ化されます。


このオプションには、CONFIG_CGROUPSが定義されている必要があり、管理者は"cgroup"疑似ファイルシステムを使用して任意のグループを創設できます。
このファイルシステムに関する詳しい情報に関しては Documentation/cgroups/cgroups.txtを見てください。

タスクをグループ化するこれらのオプションは1つしか選ぶことができません。

CONFIG_USER_SCHEDが定義されているとき、それぞれの新しいユーザのためにsysfs上にディレクトリが作成されます、そして、「cpu_share」ファイルはそのディレクトリへ加えられます。

# cd /sys/kernel/uids
# cat 512/cpu_share # Display user 512's CPU share
1024
# echo 2048 > 512/cpu_share # Modify user 512's CPU share
# cat 512/cpu_share # Display user 512's CPU share
2048
#

2人のユーザの間のCPU帯域幅は彼らのCPUシェアの比率で分割されます。
例えば: あなたが、ユーザ「root」にユーザ「guest」の2倍の帯域幅を得たかったら、「root」のcpu_shareを「guest」のcpu_share値の2倍に設定してください。

CONFIG_CGROUP_SCHEDが定義されている場合、"cpu.shares"ファイルは疑似ファイルシステムを使用することで創設された各グループのために作成されます。
"cgroups"疑似ファイルシステムを使用することで下での例のステップを見て、task groupを創設して、それらのCPUシェアを変更してください。

# mkdir /dev/cpuctl
# mount -t cgroup -ocpu none /dev/cpuctl
# cd /dev/cpuctl

# mkdir multimedia # create "multimedia" group of tasks
# mkdir browser # create "browser" group of tasks

# #Configure the multimedia group to receive twice the CPU bandwidth
# #that of browser group

# echo 2048 > multimedia/cpu.shares
# echo 1024 > browser/cpu.shares

# firefox & # Launch firefox and move it to "browser" group
# echo > browser/tasks

# #Launch gmplayer (or your favourite movie player)
# echo > multimedia/tasks

8. 実装メモ: ユーザネームスペース

ユーザネームスペースが階層的であることを意図します。
しかし、それらは現在、部分的に実装されているだけです。
それぞれのものには、CFSのための分岐があります。

まず最初に、ユーザネームスペースが階層的であるので、/sys/kernel/uidsプレゼンテーションは不十分です。
結局、各ユーザのネームスペースの中で/sys/kernel/uidsの私見を提供するのにおそらくsysfsタグ付けを使用したいと思うでしょう。

2番目に、階層的な仕組みはユーザネームスペースの完全にunprivilegedな使用をサポートすることを意図します。
それで、ユーザ・グループを使用するなら、私たちは、ユーザ名前空間におけるユーザにそれを作成したユーザの子供になって欲しいと思います。

それは現在、未実装です。
それで、代わりに、新しいユーザネームスペースにおけるすべてのユーザがまさしく初期のユーザ名前空間におけるどんなユーザのような1024のシェアも受けるでしょう。
現在、新しいユーザ名前空間の創造がそれぞれのCAP_SYS_ADMIN、CAP_SETUID、およびCAP_SETGIDを必要とすることに注意してください。