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

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

プロセスがなるべく同じCPU上で実行が繰り返された方が効率がよい。(そのプロセスが利用した情報がキャッシュメモリ上に残っているなど)最も高いプライオリティのプロセスを探すgoodness関数においては、スケジューラが動作しているCPU上で、以前動作していたプロセスであれば、プライオリティ計算に下駄を履かせ、なるべく同じCPU上で実行できるよう配慮している。

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

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

起床したプロセスがWAITする前に動作していたCPUが、idle状態であれば、そのCPUに対しプリエンプト要求を出す。
- 起床処理が動作したCPU(reschedule_idleを実行しているCPU)と異なる場合は、プロセッサ間通信を利用してCPUへ通知を行う (smp_send_reschedule関数)。非常に重い。

起床したプロセスがWAITする前に動作していたCPU上で現在動作しているプロセスとプライオリティを比較 (preemption_goodness関数)し、起床したほうのプロセスがプライオリティが高ければ、そのCPUへプリエンプト要求を出す。
それ以外でidle状態のCPUを探し、そのCPUに対してプリエンプト要求を出す
他CPU上dで動いているプロセスのプライオリティが低ければ、プロセスマイグレーションを試みる。ただし、他CPU上で動作しているプロセスからCPUを奪い取るためには、今起床したプロセスの方が遥かに高いプライオリティを持っている必要がある(preemption_goodness関数)。
一般には、現在起床したプロセスのプラオイリティより他CPU上により低いプライオリティのプロセスが存在しても、プロセスマイグレーションまで行なわず、いずれ再スケジューリングされるのを待つ。 (プロセスマイグレーション処理は非常に重く、スループットの面で逆に効率が悪くなる)

v2.2では、「今起床されたプロセスが、現在このCPUのカレントプロセスから起床されたものであった場合、他のCPU上へ実行権を与えられてもカーネルロック(後述lock_kernel関数)処理でビジーウェイトするだけで無駄なのでこのままにしておく」という処理が行われていたが、v2.4では原則Linxuカーネル内をカーネルロック(後述lock_kernel関数)を行わずに走行できるようになったため、この処理は外された。

(NIS)HirokazuTakahashi
2000年12月09日 (土) 23時55分06秒 JST1

Up: スケジューリング

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

Next: ハードウェア割り込み