読者です 読者をやめる 読者になる 読者になる

NetBSDのスケジューラを読んでみるめも1

kernel netbsd

(´-`).。oO(なんとなくNetBSDのスケジューラを読んでみようと思ったので
見ているのはsched_4bsd.cですが、これはBSDカーネルの設計と実装の4.4.1で説明されている4.4BSDのスケジューラと基本的な考え方は変わってないよなーという想いもありこれにしてます。

sys/sched.hにsched_XXXな関数はいくつか定義されているけどそのうちsched_4bsd.csched_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_FIFOFIFOの場合は何もしない。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()とそこから呼ばれる関数を見てみたので続きは次回ということで( ´Д`)ノ~