internal22-215-スケジューリングポリシー - Linux Kernel Documents Wiki - Linux Kernel Documents

Up: スケジューリング

Prev: プロセススケジューラ

Next: 時計

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

マルチプロセッサ動作時のスケジューラの動きを以下に示す。★印が、シングルプロセッサから追加される機能である。

  schedule()
     タスクキューtq_schedulerの実行(run_task_queue関数) <詳しくは後述>
     BHハンドラ呼び出し(do_bottom_half関数) <詳しくは後述>
     プリエンプション要求をクリア
     if(スケジューラを呼び出したプロセスの状態がTASK_RUNNINGでない){
           プロセスをRUNキューから外す(del_from_runqueue関数)
     }
     while(RUNキューに継っている全てのプロセスに対して) {
           ★ただし、現在CPUが割り当てられている(has_cpuフラグが立っている)プロセスを除き、
           最も高いプライオリティのプロセスを探す(goodness関数)
     }
     while(システム上の全てのプロセスに対して) {
           プライオリティ再計算
     }
     ★選ばれたプロセスのtask_structにCPU番号を格納(processorメンバ)
     ★選ばれたプロセスをCPU割当て状態にする(has_cpuフラグを立てる)
     プロセスコンテキストの切替え(switch_to関数)
     ★if(まさに今WAITするためCPUを放棄したプロセスにwake_upが行われた)
           ★カレントプロセスに再スケジーリング要求を出す
       
     ★CPUを放棄したプロセスのCPU割り当て状態を解除(has_cpuフラグのクリア)

スケジューラに対し、再スケジューリング要求を出す関数(reschedule_idle関数)もマルチプロセッサを意識した動作になる。CPU間通信はヘビーな為、 ほどほどのところで妥協した作りとなっている。以下のような方針でプリエンプト要求を出すCPUを選んでいる。二つのCPUが存在する時、優先度でみて上から二つのプロセスにCPUが割り当てられるわけではない。

1. プロセスの起床処理の動いたこのCPU上のカレントプロセスと プライオリティを比較し、起床したプロセスの方がプライオリティが 高ければ、このCPUのスケジューラに対しプリエンプト要求を出す。 (ほんの少ししかプライオリティ差が無いときは、要求を出さない)
2. カレントプロセスの走行時間が残り少なそうなら、他のCPUへの マイグレーションは行わない。(計算はいい加減)
3. 今起床されたプロセスが、現在このCPUのカレントプロセスから起床 されたものであった場合、他のCPU上へ実行権を与えられても カーネルロック(後述lock_kernel関数)処理でビジーウェイトする だけで無駄なのでこのままにしておく。
4. WAITする前に動いていたCPU(task_structのprocessorメンバでチェック) がidle状態の場合、そのCPU上のスケジューラに対してプリエンプト 要求をだす。(プロセッサ間通信を利用するため、非常に重い)
5. それ以外でidle状態のCPUを探し、そのCPUに対してプリエンプト要求を出す。
6. idle状態のCPUが存在しない場合は、プロセスマイグレーションは諦める。

---

(NIS)HirokazuTakahashi
2000年06月11日 (日) 22時29分57秒 JST1

Up: スケジューリング

Prev: プロセススケジューラ

Next: 時計