netbsdのスケジューリング(覚書)

netbsdのスケジューリングの流れを忘れてしまったので、ソースを読み直した。
この記録は、次に忘れないようにするための備忘録である。

1.スケジューリングが行われる流れ(sleepなどで自発的に実行権を手放す場合は除く。
hardclock()から、100msに1回sched_tick()をコール。
lwpのスケジューリングポリシがSCHED_FIFOでない場合、cpu_need_resched()を呼び出す。

mipsの場合、cpu_need_resched()は

aston(ci->ci_data.cpu_onproc);
ci->ci_want_resched = 1;

でaston(ci->ci_data.cpu_onproc);は
((l)->l_md.md_astpending = 1)
となっている。

例外やシステムコールの戻り時にmd_astpendingを見て、非ゼロの場合、ast()をコールする。

ast()ではci->ci_want_reschedの値をチェックし、非ゼロな場合、preempt()をコールする。
preempt()の中ではmi_switch()がコールされるため、スケジューリングが行われる。

2.runqueueと優先度
runqueue_t構造体で定義。
キューは2種類ある。
1.r_rt_queue
2.r_ts_queue
r_rt_queueの方が優先度が高いものらしい。
優先度がPRI_HIGHEST_TS以下であればr_ts_queueを使う。

キューはcpu_infoごとに存在する。
cpu_info中のschedstate_percpu構造体内のspc_sched_infoがrunqueue_t構造体である。
この中からもっとも優先度が高い（spc_maxpriority）キューの先頭のlwpを取得する。

3.優先度の計算
lwp_eprio()で計算する。
l_priorityの値をベースに優先度を決定する。

1.l_kpriorityがtrueでありながらl_priorityの値がPRI_KERNELより小さければ「l_krpbase + l_priority / 2」を優先度とする。
2.1以外の場合はl_priorityの値を優先度とする。
3.1もしくは2で得られた値とl_inheritedprioを比較し、大きな値を最終的に優先度とする。

4.どうやって優先度を変動しているの
(以下の文章は、スケジューラが4bsdの場合を想定する。)
l_priorityに値を設定している人がsched_changepri()くらいである。
この関数は、sched_syncobjというsyncobj_t型の構造体メンバになっている。
メンバ名はsobj_changepri。

sobj_changepriを使っているのは、lwp.h内のlwp_changepri()のみである。
sched_4bsdな場合、lwp_changepri()をresetpriority()の中で呼び出す。
resetpriority()は優先度の再計算をしたのち、lwp_changepriをコール。

resetpriority()がコールされるのは以下の4箇所である。
1.sched_schedclock()
2.sched_pstats_hook()
3.updatepri()
4.sched_nice()

1.はhardclock()から定期的にコール。現在動いているlwpの優先度の再計算をする。
「定期的に」とは1秒間に16回を想定している。

schedhzというグローバル変数が0の場合、ci->ci_schedstate.spc_schedticks = hardscheddivな粒度で呼ばれる。
schedhzはalphaもしくはsparc64以外は0なので、mipsでは0となる。
なお、hardscheddivの値は、hz / 16　となっている。
よって、1秒間に約16回実効状態のlwpの優先度を再計算することになる。

2.はsched_lwp_stats()からコール。
sched_lwp_stats()は、kern_synch.c内のsched_pstats()からコールされている。
sched_pstats()は全プロセスのlwpをたどり、優先度の再計算をしている。
sched_pstats()はuvm_schedulerからコールされる。kpause()で1秒おきに起きてsched_pstatsをコールするようだ。
よって、1秒ごとにすべてのlwpの優先度が再計算されることになる。

3.はsched_4bsdなソースのsched_setrunnable()からコールされている。
sched_setrunnable()では、対象とするlwpのl_slptimeが1を上回る場合にのみupdatepri()を呼び出す。

sched_setrunnable()は以下2通りのケースで呼び出す。
3-1.sleepq_removeでlwpを起こすとき、起こそうとするlwpに対してsched_setrunnable()を呼び出す。
3-2.setrunnableでlwpを実行可能状態にするとき、該当lwpに対してsched_setrunnable()を呼び出す。

また、l_slptimeについては、該当lwpのsleep状態(LSSLEEP/LSSTOP/LSSUSPENDED)に遷移してから最初にsched_lwp_stats()がコールされるまでsleep状態が続いたときにl_slptimeが++される。

4はdonice()でコールされる。
donice()はsys_setpriorityからコールされる。つまり、setpriority()による優先度の変更があった場合にも優先度の再計算がされる。