(´-`).。oO(なんとなくNetBSDのスケジューラを読んでみようと思ったので
見ているのはsched_4bsd.cですが、これはBSDカーネルの設計と実装の4.4.1で説明されている4.4BSDのスケジューラと基本的な考え方は変わってないよなーという想いもありこれにしてます。
sys/sched.hにsched_XXXな関数はいくつか定義されているけどそのうちsched_4bsd.cとsched_m2.cの両方に定義されているものをチェックしてみると以下の14関数に。といっても処理は空のものもあるので、処理が書かれているものに○を付けてみました。
Function | M2 | 4BSD |
sched_tick | ○ | ○ |
sched_pstats_hook | ○ | ○ |
sched_rqinit | ○ | |
sched_setrunnable | ○ | |
sched_nice | ○ | ○ |
sched_schedclock | ○ | |
sched_proc_fork | ○ | ○ |
sched_proc_exit | ○ | |
sched_lwp_fork | ○ | |
sched_lwp_collect | ○ | |
sched_oncpu | ○ | |
sched_newts | ○ | |
sched_wakeup | ○ | |
sched_slept | ○ |
それでは関数を見ていくとして、まずはsched_tick()から。
関数冒頭のコメントによるとこの関数ではデータにアクセスする際にロックは不要となってます。
109 sched_tick(struct cpu_info *ci) 110 { 111 struct schedstate_percpu *spc = &ci->ci_schedstate; 112 lwp_t *l; 113 114 spc->spc_ticks = rrticks;
最初にするの今動いているcpuにあるスケジューラの状態を取得してsched_tick()が呼ばれるまでのtickをセット。
116 if (CURCPU_IDLE_P()) { 117 cpu_need_resched(ci, 0); 118 return; 119 }
次は今動いているプロセスがアイドルプロセスならcpu依存なcpu_need_resched()を呼んでリスケジュールする。
cpu_need_resched()の2番目の引数で0を渡すのでこの関数内にあるRESCHED_KPREEMPTやRESCHED_IMMEDなどのフラグチェック部分は実行されないということ。
120 l = ci->ci_data.cpu_onproc; 121 if (l == NULL) { 122 return; 123 }
ここでlwpがNULLということがあるのかは不明なんですが、NULLだった場合は何もせずreturnする。
switch (l->l_class) { 125 case SCHED_FIFO: 126 /* No timeslicing for FIFO jobs. */ 127 break; 128 case SCHED_RR: 129 /* Force it into mi_switch() to look for other jobs to run. */ 130 cpu_need_resched(ci, RESCHED_KPREEMPT); 131 break; 132 default: 133 if (spc->spc_flags & SPCF_SHOULDYIELD) { 134 /* 135 * Process is stuck in kernel somewhere, probably 136 * due to buggy or inefficient code. Force a 137 * kernel preemption. 138 */ 139 cpu_need_resched(ci, RESCHED_KPREEMPT); 140 } else if (spc->spc_flags & SPCF_SEENRR) { 141 /* 142 * The process has already been through a roundrobin 143 * without switching and may be hogging the CPU. 144 * Indicate that the process should yield. 145 */ 146 spc->spc_flags |= SPCF_SHOULDYIELD; 147 cpu_need_resched(ci, 0); 148 } else { 149 spc->spc_flags |= SPCF_SEENRR; 150 } 151 break; 152 }
sched_tick()最後の処理部分はスケジューリングポリシーによってプロセスのリスケジュールをしたりフラグの値を変更したりです。
SCHED_FIFOなど、これら定数はsys/sched.hで定義されています。
84 /* 85 * Scheduling policies required by IEEE Std 1003.1-2001 86 */ 87 #define SCHED_NONE -1 88 #define SCHED_OTHER 0 89 #define SCHED_FIFO 1 90 #define SCHED_RR 2
このコメントに書かれているIEEE Std 1003.1ですがWikipediaに説明あるんですね。
それはさておき上から順に行くと、最初はSCHED_FIFOでFIFOの場合は何もしない。SCHED_RRの場合(RRはRound-robinということですね)はプリエンプト可と指定した上でプロセスのリスケジュール。
スケジューリングポリシーがSCHED_NONE、SCHED_OTHERの場合は立っているフラグによって処理が変わり、SPCF_SHOULDYIELDが立っている場合はコメントにある通りでSCHED_RRの場合と同じ処理になる。
SPCF_SEENRRが立っている場合は、SPCF_SHOULDYIELDもセットしてからリスケジュール実行。それ以外の場合はSPCF_SEENRRフラグを立てる。
これらのフラグはsys/sched.hで定義されてます。
174 /* spc_flags */ 175 #define SPCF_SEENRR 0x0001 /* process has seen roundrobin() */ 176 #define SPCF_SHOULDYIELD 0x0002 /* process should yield the CPU */ 177 #define SPCF_OFFLINE 0x0004 /* CPU marked offline */ 178 #define SPCF_RUNNING 0x0008 /* CPU is running */ 179 #define SPCF_NOINTR 0x0010 /* shielded from interrupts */
今日は最後にcpu_need_resched()を見てみます。
193 void 194 cpu_need_resched(struct cpu_info *ci, int flags) 195 { 196 struct cpu_info *cur; 197 lwp_t *l; 198 199 KASSERT(kpreempt_disabled()); 200 cur = curcpu(); 201 l = ci->ci_data.cpu_onproc; 202 ci->ci_want_resched |= flags;
この辺は見たままなので省略。
203 204 if (__predict_false((l->l_pflag & LP_INTR) != 0)) { 205 /* 206 * No point doing anything, it will switch soon. 207 * Also here to prevent an assertion failure in 208 * kpreempt() due to preemption being set on a 209 * soft interrupt LWP. 210 */ 211 return; 212 } 213
LP_INTRはsys/lwp.hによるとソフトウェア割り込み。ということでソフトウェア割り込み中だったらもうすぐプロセスが切り替わるのでここではこれ以上の処理は不要みたいですね。
248 #define LP_INTR 0x00000040 /* Soft interrupt handler */
425 #if __GNUC_PREREQ__(2, 96) 426 #define __predict_true(exp) __builtin_expect((exp) != 0, 1) 427 #define __predict_false(exp) __builtin_expect((exp) != 0, 0)
ちなみに__predict_false()はsys/cdefs.hで定義していてLinuxだとunlikely()的なもの。
214 if (l == ci->ci_data.cpu_idlelwp) { 215 if (ci == cur) 216 return; 217 if (x86_cpu_idle_ipi != false) { 218 cpu_kick(ci); 219 } 220 return; 221 } 222
lwpがアイドルプロセスのスレッドならどうするかで、cpuが同じならこれで終了して、違うcpuで動いている場合はcpu_kick()でIPIを使ってそcpuに割り込みをかける。
1310 void 1311 cpu_kick(struct cpu_info *ci) 1312 { 1313 x86_send_ipi(ci, 0); 1314 } 1315
この関数はx86_send_ipi()を呼ぶだけ。
ここまでで残ったのはソフトウェア割り込み中のプロセスでもアイドルプロセスでもないプロセスになりますと。
223 if ((flags & RESCHED_KPREEMPT) != 0) { 224 #ifdef __HAVE_PREEMPTION 225 atomic_or_uint(&l->l_dopreempt, DOPREEMPT_ACTIVE); 226 if (ci == cur) { 227 softint_trigger(1 << SIR_PREEMPT); 228 } else { 229 x86_send_ipi(ci, X86_IPI_KPREEMPT); 230 } 231 return; 232 #endif 233 } 234
sched_tick()からcpu_need_resched()を呼ぶときにプリエンプト可を指定した場合の処理がここ。よそのCPUに対して処理が必要な場合はIPIを使うというまあ当たり前な感じですね。
softint_triggerはアーキテクチャ依存な処理でamd64ならsys/arch/amd64/amd64/spl.Sにあります。
134 /* 135 * void softint_trigger(uintptr_t machdep); 136 * 137 * Software interrupt registration. 138 */ 139 NENTRY(softint_trigger) 140 orl %edi,CPUVAR(IPENDING) /* atomic on local cpu */ 141 ret 142
CPUVARは何者かというとこうなっています。
88 #ifdef __STDC__ 89 #define CPUVAR(off) %gs:CPU_INFO_ ## off 90 #else 91 #define CPUVAR(off) %gs:CPU_INFO_/**/off 92 #endif
ということでsys/arch/amd64/amd64/genassym.cfの下の定義が使われるんじゃないかと。
244 define CPU_INFO_IPENDING offsetof(struct cpu_info, ci_ipending)
「%gs:」があるからThread local storageですね。
そんなわけで、プリエンプト可となっていた場合の処理はここまでです。
235 aston(l, X86_AST_PREEMPT); 236 if (ci == cur) { 237 return; 238 } 239 if ((flags & RESCHED_IMMED) != 0) { 240 cpu_kick(ci); 241 } 242 }
aston()はsrc/sys/arch/x86/include/cpu.hで定義されていてbitを立てているのは分かるんですがastが何の略なのかはヽ('ー`) ノオテアゲ
315 #define aston(l, why) ((l)->l_md.md_astpending |= (why))
236行目のところは今までも出てきてますけど、cpuが同じなら何もしないと。
最後の239行目のところは今すぐにリスケが必要という場合はIPIで割り込みを送ります。236行目のif文でcpuが同じ場合をチェック済みなのでここはIPIを使うのが確定となっている訳ですね。
さて、今日はsched_tick()とそこから呼ばれる関数を見てみたので続きは次回ということで( ´Д`)ノ~