- O(1)スケジューラの実装は、shceduler()関数をコアとしている
- scheduler()関数は200行程度の小さなプログラム
- ソースコードは"kernel/sched.c"
実行queue
- runqueue構造体は、CPUの数の分だけ用意される
- runqueue構造体において、prio_array構造体のメンバーとしてactiveとexpiredが定義されており、それがactive queueとexpired queueとなる
- active queueとexpired queueに対してprocessが登録されており、process情報を格納するtask_struct構造体がひもづけられている
- activeとexpiredをメンバーとして持つprio_array構造体では、実行待ち状態のprocessが登録されるqueueと、queueに登録されているprocess数についてもメンバーとして管理される
- active queueとexpired queueには、それぞれ優先度別に140個のqueueを持っている
- 非常に多くのqueueを持ちながらも、processの確認処理に時間を要することを防ぐために、各queueにおける実行待ちprocessの有無を示すbitmapが定義されている
優先度の算出
- O(1)スケジューラでの優先度の定義は"nice値"と"ボーナス"により設定される
- 待ち時間の長いI/Oバウンド型processや、優先度が低く設定されているために実行間隔が長くなっているprocessなどの処理の優先度をボーナスによって次第に上げることによって、システム全体のprocessの処理の最適化を図る
schedule()関数における処理の流れ
- [this_rqマクロ]操作するrunqueueを選択する
- [task構造体／sleep_avgメンバー]実行時間runtimeを計算する(runtimeはsleep_avg計算のために使用され、sleep_avgが高いほどruntimeは短くなるように補正される)
- [task構造体／static_prioメンバー]現在実行されているcurrent processがイベント待ちによってCPUの割り当てを明け渡す場合、processのステータスを確認し、runqueueを操作する
- [deactivate_task関数]current processがシグナル受信のために待ち状態になろうとしているものの、シグナルが到着もしくはすぐに到着することが確実である場合には、processのステータスを実行状態に戻す
- [deactivate_task関数]current_processが割り込み不可でイベント待ちとなる場合には、イベント発生までprocessの処理を実施しないようactive queueから対象のprocessを削除する
- [idle_balance関数]runqueueに実行可能なprocessがない場合、他のCPUのrunqueueからprocessを移動させる
- [runqueue構造体／activeメンバー、expiredメンバー]active queueに実行可能なprocessがエントリーしていない場合、active queueとexpired queueを入れ替える
- [recalc_task_prio関数]次に実行するprocessの選択を行う(イベント待ち状態から実行待ち状態に移行する"起床"ステータス直後は通常に比べて優先度が高く設定されている場合があるため、優先度の再計算を行う)
- [task構造体／sleep_avgメンバー、static_prioメンバー]sleep_avgを計算する
- [context_switch関数]選択されたprocessに処理を移す
- [preempt_disable関数]実行processの選択／処理を行っている間に他のprocessの処理がスケジューリング要求され、同時にスケジューリングされないように、schedule()関数ではプリエンプトが抑止される
- [preempt_disable関数]実行している／しようとしているprocessよりも優先度の高いprocessのスケジューリングが要求された場合には、現在実行しているprocessのスケジューリングを完了させてから再度runtimeの選択から処理を行う
