Linux Kernel(2.6)の実装に関するメモ書き

スケジューラ



1.スケジュール処理

schedule()がスケジューラーのメイン処理。schedule()はRunQueueから(動的)優先度の高いプロセスを選択して実行する。

schedule()はプロセスがBlock,Wakeupさせる時に明示的に呼び出して、次に実行するプロセスを選択するが、その他にも以下の契機で呼ばれている。

1. 例外や割り込みから戻る時(戻り先がユーザモードの時)
2. 例外や割り込みから戻る時(戻り先がカーネルモードの時)(CONFIG_PREEMPTが有効の時のみ)
3. システムコールから戻る時



schedule()の処理の流れ
schedule()

rq = this_rq(); - 自CPUのRunQueueを取得
:
:
if (prev->state && !(preempt_count() &
PREEMPT_ACTIVE) {
/* prevがTASK_RUNNING以外の状態で
* 切り替えがプリエンプションでなく
* 通常の切り替えだった場合 (*1) */

if (prevがTASK_INTERRUPTIBLE状態 && シグナルがペンディングされている)
TASK_RUNNING状態に戻す
else
deactivate_task(prev, rq) - RunQueueから取り外す
}

if (!rq->nr_running) {
/* RunQueueにプロセスがない */

idle_balance(cpu, rq) - 他のCPUのRunQueueからプロセスを持って来る
if (
rq->nr_running) {
/* まだRunQueueにプロセスがない */
wake_sleeping_dependent(cpu, rq) - SMT用処理
同じ物理プロセッサ内の他の論理プロセッサ(Sibling)で
RunQueueにプロセスがあるのに
Idle状態になっている
ものがあればWakeupする。

dependent_sleeper()によりRunQueueにプロセスがあっても
Idleになっている可能性があるため。

if (!rq->nr_running)
goto switch_tasks
}
} else {
if (dependent_sleeper()) {
- SMT用処理 (*2)
/* Idle状態にする */
next = rq->idle;
goto switch_tasks;
}

if (unlikely(!array->nr_active)) {
/* RunQueueのActiveリストにプロセスがない場合 */

全RUNNINGプロセスがCPU時間を使い切った事になるので
rq->active <-> rq->expireを入れ換える
(次のQuantamが開始になる)
}

/* 次の実行プロセスを選択
* Activeリストから動的優先度の最も小さいプロセスを取得 */

idx = sched_find_first_bit(array->bitmap);
queue = array->queue + idx;
next = list_entry(queue->next, task_t, run_list);

if (!rt_task(next) && next->activated > 0) {
/* 選択したプロセスが非リアルタイムプロセスで
Wakeup後、初回実行の時 (*3) */


recalc_task_prio() - 動的優先順位再計算
sleepしていた時間に応じてsleep_avgを更新し
effective_prio(p)で優先順位を計算する

RunQueue内の優先度に対応するリストにつなぎ直す
}

switch_tasks:
:
prev->sleep_avgを使用したCPU時間分だけ減算
(この影響で動的優先度は下がっていく)

if (選択したプロセスが以前と異なる) {
prepare_task_switch(rq, next)
context_switch(rq, prev, next) - プロセス切替え

MMの切替え
if (next->mmがない) { - Kernel Process
アドレス空間を持たないので切替え不要

next->active_mm = prev->active_mm;
<-- 前のプロセスからActiveマップを引き継ぐ
enter_lazy_tlb(prev->active_mm, next)
} else {
switch_mm(prev->active_mm,next->mm,next)
:
load_cr3(next->mm->pgd) - PageTable切替え
}
:
switch_to(prev, next, prev) - レジスタ、スタックの切替え
barrier()
finish_task_switch(this_rq(), prev);
}

(*1)
Running状態でなくなったプロセスはここでRunQueueから取り外される。

PreemptされたプロセスにはPREEMPT_ACTIVEが設定されている。Preemptによりプロセスが切り替わった場合は、この処理を飛ばして、プロセスをRunqueueに残しておく。

(*2)
「Hyper Threadへの対応」のdependent_sleeper()参照。

(*3)
選択した実行プロセスが非リアルタイムプロセスで、activated > 0 つまり、TASK_INTERRUPTIBLE状態からWakeupされてまだ一度も実行されてない時にここに入る。ここでは、recalc_task_prio()を呼び出しsleep_avgの更新を行い、動的優先度を計算する。

Wakeup後、一度でも実行されたプロセスはactivatedが0になるので、この処理は通らない。

Hyper Threadへの対応

CONFIG_SCHED_SMT
SMT(Simultaneous Multi Threading)のシステムでは定義が必要。Hyper Thread対応のプロセッサも該当。cpu_sibling_map[NR_CPUS]が有効になる。

cpu_sibling_map[NR_CPUS]は各プロセッサ毎にエントリを持つ(カーネルに認識されている単位。Hyper Threadの論理的なプロセッサ毎に1エントリ存在する)。各エントリはビットマップになっており、該当プロセッサと同じ物理プロセッサに属するプロセッサのビットが立っている(自分自身も立つ)。

以下は、Hyper Thread対応のCPUが二つ動作しているSMP環境での例。物理プロセッサAにCPU0,1が所属し、物理プロセッサBにCPU2,3が属していると仮定。(参考:set_cpu_sibling_map())
cpu_sibling_map[]
+-----------+
CPU0 | ...0011B | ビットマップ右側がCPU0に対応とする
+-----------+
CPU1 | ...0011B |
+-----------+
CPU2 | ...1100B |
+-----------+
CPU3 | ...1100B |
+-----------+
:


dependent_sleeper()
同じ物理プロセッサ内の論理プロセッサ(以下Sibling)同士は、物理的なリソースの競合により、他のSibling上で実行されているプロセスの処理速度に影響を与える可能性がある。このため、Sibling上で実行されているプロセッサの優先度をチェックして、自分の方が低ければスリープさせるなどして高優先度プロセスの実行に影響がでないようにしている。

このため、RunQueueにプロセスがあるにもかかわらず、プロセッサがIdle状態になることがある。リアルタイムプロセスやカーネルスレッドはおかまいなしでそのまま実行している。

優先度が異なるものが複数実行されているとHyper Threadによる並列処理はあまり効かないということ?
<== loopしてCPUを使いまくるスクリプトを二つ実行して試して見ると、、、

同じ優先度で実行して、topで各プロセスのCPU利用率を見るとどちらもほぼ100%近く。HyperThreadで並列処理されている。

一方をnice 10にして優先度を下げるとnice 10のプロセスのCPU利用率が60%程度に低下(nice 0の方は相変わらず100%近く)。dependent_sleeper()の処理が効いて並列度が下がっているっぽい。

2. タイマ処理

タイマ処理ではプロセスのCPU時間の減算が行われる。CPU時間を使いきったプロセスはExpireリストに移動され、Activeリストの全プロセスがCPU時間を使いきるのを待つ。また、CPUを使いきったプロセスは動的優先度を再計算する。

タイマ周期は10ms(100Hz)。

scheduler_tick()
if (rt_task(p)) {
/* リアルタイムプロセスの処理 */
}
if (p->time_slice減算し0になった) {
/* プロセスがCPU時間を使いきった (*1) */
rq->activeから外す
set_tsk_need_resched(p) - TIF_NEED_RESCHEDをセットしてプロセスの切替え要求
(Linux2.4のp->need_reschedule = 1に相当)
p->prio設定 (effective_prio()参照)
p->time_slice設定 (CPU時間の割り当て)
設定値
nice値 -20 ... 0 ... 19
p->static_prio 100 ... 120 ... 139
p->time_slice 200ms ... 100ms ... 5ms
if (!TASK_INTERACTIVE(p) || EXPIRED_STARVING(rq)) {
プロセスがinteractiveで無ければ
(interactiveであってもEXPIRD_STARVINGなら)
rq->expireに追加
} else {
プロセスがinteractiveなら
rq->activeに戻す
}
} else {
/* time_sliceが0になっていなくても、ある程度使ったら
一旦CPUを手放す処理。(Expireさせるわけではない) */

if (1. TASK_INTERACTIVE(p) && (*2)
2. 使用したCPU時間がちょうどTIMESLICE_GRANULARITY()の倍数
&&
3. 残りのCPU時間がTIMESLICE_GRANULARITY()以上残っている) {
set_tsk_need_resched(p) - スケジュール要のフラグセット
p->prio = effective_prio(p) - 動的優先度再計算
rq->activeの対応するPrioのリストにつなぎなおす
}
}
rebalance_tick()
(*1)
CPU時間を使いきったプロセスはActiveリストからExpireリストに移動される。Expireリストのプロセスはスケジューリング対象から外れる。Activeリストの全プロセスがCPU時間を使いきってExpireに移動すると、Expire<->Activeのリストが入れ換えられて次のQuantumが開始する。なお、ここで次のQuantum用にCPU時間(time_slice)を設定している。

(*2)
この条件文の意味

条件1.
Interactiveでなければtime_sliceも小さいだろうしわざわざ切替えなくてもよいということ?
条件2.
使用したCPU時間のチェック。切替え粒度をTIMESLICE_GRANULARITY() msecにするため。
条件3.
残り時間がまだまとまった量残っているかのチェック。TIMESLICE_GRANULARITY()より小さかったらこのまま使い切る。

3. 'Interactive'なプロセスとは

LinuxのスケジューラではプロセスをユーザインタフェースなどのInteractiveな処理を行うものとそうでないものに分けている。Interactiveなプロセスに対しては即時に処理を行うようにしないと、動作が重く感じられてしまうからである。

しかし、プロセスに「このプロセスはInteractive型」であることを示すようなフラグがあるわけではなく、Interactiveかどうかはカーネルがプロセスの挙動を見て勝手に判断している。

InteractiveなプロセスはCPU時間を使いきってもExpireリストに移動されない。このため、Activeリストが空になるまで待ち状態になるのを防ぐことができ、ユーザーからの入力があればすぐに対応できる。


プロセスがInteractiveかどうかの判断はTASK_INTERACTIVE()マクロで行う。Interactiveなプロセスの特徴は、ユーザからの入力待ちが多いので基本的にSleepが多いだろうということを前提に判断している。

TASK_INTERACTIVE()の挙動を以下に示す(sched.cより)。プロセスのnice値により異なるが、動的優先度の値が小さいとInteractiveと見なされる。動的優先度はCPU使用量に応じて静的優先度をベースに±5の範囲で変動するが、Sleepが多いとマイナス方向に振れ、Interactiveと判断されやすくなる。逆にあまりSleepしないようなプロセスはプラス方向に振れ、非Interactive扱いになる。

             sleepが多い                    少ない
動的優先度の変動幅 -5 <------ 0 ------> +5
TASK_INTERACTIVE(-20): [1,1,1,1,1,1,1,1,1,0,0]
TASK_INTERACTIVE(-10): [1,1,1,1,1,1,1,0,0,0,0]
TASK_INTERACTIVE( 0): [1,1,1,1,0,0,0,0,0,0,0]
TASK_INTERACTIVE( 10): [1,1,0,0,0,0,0,0,0,0,0]
TASK_INTERACTIVE( 19): [0,0,0,0,0,0,0,0,0,0,0]

()の中の値はnice値。
'1'はInteractiveであることを示す。



[関連関数]
deactivate_task()
RunQueueからtask_structを外す。

effective_prio()
プロセスの動的優先度を計算する。

resched_task()
指定プロセスの再スケジュールさせる。

この関数を呼ぶと指定プロセスにTIF_NEED_RESCHEDフラグがセットされる。TIF_NEED_RESCHEDが立っているとプロセスが切り替えられる。(例外,割り込み,システムコールから戻る時にこのフラグをチェックして立っていたらschedule()を呼んでプロセスを切り替えている)

SMP環境だと、プロセスが割り当てられているCPUにIPI(Inter Processor Interrupt)を上げる。割り込みハンドラはreschedule_interrupt()(実体はsmp_reschedule_interrupt())だが、この割り込みハンドラでは何も行なっていない。これは、割り込みから返る時にTIF_NEED_RESCHEDがチェックされてスケジューリングされるため。IPIは単にCPUへスケジューリングの契機を与えるために使われているような感じ。

TASK_INTERACTIVEマクロ
プロセスがInteractiveかを判定するマクロ。

EXPIRED_STARVINGマクロ
最初にExpireにプロセスがつながれてからある程度時間がたつと真になる。(プロセス数に依存)

Interactive だと、CPUを使い切ってもActiveに再度チェーンされるためActiveが空にならず、CPUを使い切った(Expireにチェーンされた)プロセ スがいつまでもActiveに戻らず実行されない可能性がある。それを防ぐために本マクロで最初にExpireに移動させてからの時間をチェックし閾値を 越えていたら、InteractiveでもExpireにつなぐようにすることにより、Active<->Expireの切替えを定期的に発 生させる。

TIMESLICE_GRANULARITYマクロ
time_sileceがまだ残っているのに、一旦プロセスを切替える処理の切替え契機の粒度。これより短い間隔では切替えを発生させない。

10ms * (bonusにより決まる値)

bonusが大きい程、粒度が小さくなり切り替わりやすくなる。


[関連ページ]
プロセスの優先度
プロセス
RunQueue

http://www.samspublishing.com/articles/article.asp?p=101760&seqNum=2


最終更新 2006/07/01 21:03:36 - kztomita
(2006/03/27 12:43:53 作成)


リンク
最近更新したページ
検索