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

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

netbsd kernel

φ(^∇^ ) メモナノラ まずはsched_pstats_hook()から。

コメントからこの関数はsched_pstats()から定期的に呼ばれてプライオリティを再計算するとなってますね。

    281 /*
    282  * sched_pstats_hook:
    283  *
    284  * Periodically called from sched_pstats(); used to recalculate priorities.
    285  */
    286 void
    287 sched_pstats_hook(struct lwp *l, int batch)
    288 {
    289 	fixpt_t loadfac;
    290 
    291 	/*
    292 	 * If the LWP has slept an entire second, stop recalculating
    293 	 * its priority until it wakes up.
    294 	 */
    295 	KASSERT(lwp_locked(l, NULL));
    296 	if (l->l_stat == LSSLEEP || l->l_stat == LSSTOP ||
    297 	    l->l_stat == LSSUSPENDED) {
    298 		if (l->l_slptime > 1) {
    299 			return;
    300 		}
    301 	}

最初のほうはコメントにもある通りでプロセスが1秒以上寝ているような場合は再計算せずに終了です。

    302 	loadfac = 2 * (averunnable.ldavg[0]);

ここでaverunnableは何かと言うとsys/sys/resource.hで定義されています。

   116 #if defined(_NETBSD_SOURCE)
    117 /* Load average structure. */
    118 struct loadavg {
    119 	fixpt_t	ldavg[3];
    120 	long	fscale;
    121 };
    122 #endif
    123 
    124 #ifdef _KERNEL
    125 extern struct loadavg averunnable;

ldavgは要素3個の配列なので1分、5分、15分単位とかのロードアベレージってことですよね。そうするとここで使うのは直近1分のロードアベレージ

    303 	l->l_estcpu = decay_cpu(loadfac, l->l_estcpu);

このdecay_cpu()が割とキモになる部分でしょうか。この関数でスケジュール優先度が変更されるわけですね。
decay_cpu()はコメントでロジックを説明しているのでそっちを読んだほうが良いかと思いますが(;´∀`)

    239 static fixpt_t
    240 decay_cpu(fixpt_t loadfac, fixpt_t estcpu)
    241 {
    242 
    243 	if (estcpu == 0) {
    244 		return 0;
    245 	}
    246 

最初のif文ですが、これはlwp構造体のl_espcpuに入ってた値です。黒の悪魔本だとkg_estcpuのことだと思います。この本によるとkg_estcpuはスレッドの最近のcpu利用度を評価したものとなってますので、利用度が0ならcpuを全く使って無いので以降の再計算が不要ということですね。

    247 #if !defined(_LP64)
    248 	/* avoid 64bit arithmetics. */
    249 #define	FIXPT_MAX ((fixpt_t)((UINTMAX_C(1) << sizeof(fixpt_t) * CHAR_BIT) - 1))
    250 	if (__predict_true(loadfac <= FIXPT_MAX / ESTCPU_MAX)) {
    251 		return estcpu * loadfac / (loadfac + FSCALE);
    252 	}
    253 #endif /* !defined(_LP64) */
    254 
    255 	return (uint64_t)estcpu * loadfac / (loadfac + FSCALE);
    256 }
    257 

_LP64が定義されていかった場合は無視して最後のreturn文に目を向けましょう。
FSCALLはsrc/sys/sys/param.hにいます。

    402 /*
    403  * Scale factor for scaled integers used to count %cpu time and load avgs.
    404  *
    405  * The number of CPU `tick's that map to a unique `%age' can be expressed
    406  * by the formula (1 / (2 ^ (FSHIFT - 11))).  The maximum load average that
    407  * can be calculated (assuming 32 bits) can be closely approximated using
    408  * the formula (2 ^ (2 * (16 - FSHIFT))) for (FSHIFT < 15).
    409  *
    410  * For the scheduler to maintain a 1:1 mapping of CPU `tick' to `%age',
    411  * FSHIFT must be at least 11; this gives us a maximum load avg of ~1024.
    412  */
    413 #define	FSHIFT	11		/* bits to right of fixed binary point */
    414 #define	FSCALE	(1<<FSHIFT)

そうすると各変数の値は以下のようになります。

loadfac 1分間のロードアベレージに2を掛けたもの
estcpu lwpの最新のcpu利用度(前回計算した値)
FSCALL 0x800==2048

これで計算した結果が再計算対象のlwpのcpu利用度になりました。

    304 	resetpriority(l);
    305 }
    306 

最後にresetpriority()を呼びます。

    354 /*
    355  * Recompute the priority of an LWP.  Arrange to reschedule if
    356  * the resulting priority is better than that of the current LWP.
    357  */
    358 static void
    359 resetpriority(struct lwp *l)
    360 {
    361 	pri_t pri;
    362 	struct proc *p = l->l_proc;
    363 
    364 	KASSERT(lwp_locked(l, NULL));
    365 
    366 	if (l->l_class != SCHED_OTHER)
    367 		return;
    368

最初にスケジューリングポリシーのチェックをしてSCHED_OTHER以外の場合はreturnします。
SCHED_OTHERはどんなポリシーか調べてみると、sched(3)のmanに説明がありました。これはタイムシェアリングなポリシーでNetBSDのプロセスのデフォルトのポリシーらしいです。

    369 	/* See comments above ESTCPU_SHIFT definition. */
    370 	pri = (PRI_KERNEL - 1) - (l->l_estcpu >> ESTCPU_SHIFT) - p->p_nice;
    371 	pri = imax(pri, 0);

ここからがプライオリティの再計算部分ですね。定数の細かいところは無視して計算した優先度は0~priの範囲になるようにする。ここだけ見ると下限だけをチェックですね。

    372 	if (pri != l->l_priority)
    373 		lwp_changepri(l, pri);
    374 }

再計算したプライオリティとlwpに現在設定されているプライオリティが違ったらlwp_changepri()を呼んで値の更新を実施。
そんなにたいした処理じゃないだろと思って見てみたらそんなことはなかった\(^o^)/ まあ、よくよく考えるとプロセスのプライオリティが変わるんだからなそうだよなって感じなのですが。

   386 static inline void
    387 lwp_changepri(lwp_t *l, pri_t pri)
    388 {
    389 	KASSERT(mutex_owned(l->l_mutex));
    390 
    391 	if (l->l_priority == pri)
    392 		return;
    393 
    394 	(*l->l_syncobj->sobj_changepri)(l, pri);
    395 	KASSERT(l->l_priority == pri);
    396 }

sys/sys/syncobj.hによると同期的に処理を行う仕組みがあるようですね。

     41 /*
     42  * Synchronisation object operations set.
     43  */
     44 typedef struct syncobj {
     45 	u_int	sobj_flag;
     46 	void	(*sobj_unsleep)(struct lwp *, bool);
     47 	void	(*sobj_changepri)(struct lwp *, pri_t);
     48 	void	(*sobj_lendpri)(struct lwp *, pri_t);
     49 	struct lwp *(*sobj_owner)(wchan_t);
     50 } syncobj_t;

じゃあ実体は?というと下のほうでいくつか定義があってスケジューラ、ミューテックスなど用途別にオブジェクトがいそうですね。。今調べているのはスケジューラだからsched_syncobjを見てみましょう。

     58 extern syncobj_t	sched_syncobj;
     59 extern syncobj_t	mutex_syncobj;
     60 extern syncobj_t	rw_syncobj;
     61 extern syncobj_t	sleep_syncobj;

定義はsys/kern/kern_synch.cにありました。

    122 syncobj_t sched_syncobj = {
    123 	SOBJ_SLEEPQ_SORTED,
    124 	sched_unsleep,
    125 	sched_changepri,
    126 	sched_lendpri,
    127 	syncobj_noowner,
    128 };

lwp_changepri()が関数ポインタを経由して呼び出すのはsched_changepri()っぽいですね。
関数の実体はsys/kern/kern_synch.cにあります。

   1057 sched_changepri(struct lwp *l, pri_t pri)
   1058 {
   1059 
   1060 	KASSERT(lwp_locked(l, NULL));
   1061 
   1062 	if (l->l_stat == LSRUN) {
   1063 		KASSERT(lwp_locked(l, l->l_cpu->ci_schedstate.spc_mutex));
   1064 		sched_dequeue(l);
   1065 		l->l_priority = pri;
   1066 		sched_enqueue(l, false);

まずはプロセスが走っている場合、lwpをキューから外した後に新しいプライオリティを設定してからlwpをキューにいれます。

   1067 	} else {
   1068 		l->l_priority = pri;
   1069 	}

プロセスが走っていなら単にプライオリティを設定しなおすだけです。

   1070 	resched_cpu(l);
   1071 }

最後にresched_cpu()を使ってcpuに対してリスケジュールを依頼します。

   1046 static void
   1047 resched_cpu(struct lwp *l)
   1048 {
   1049 	struct cpu_info *ci = l->l_cpu;
   1050 
   1051 	KASSERT(lwp_locked(l, NULL));
   1052 	if (lwp_eprio(l) > ci->ci_schedstate.spc_curpriority)
   1053 		cpu_need_resched(ci, 0);
   1054 }

これは新しく設定したプライオリティが元のプライオリティよりも優先度が上がった時にリスケをするわけですね。cpu_need_resched()は昨日調べた関数です。
(ー。ー)フゥ sched_pstats_hook()一つ調べるだけでも色々ありますねぇ。続きはまた次回 moimoi(・x・)

φ(.. )メモシテオコウ 昨日分からなかったastって略語はFreeBSDカーネルの設計と実装のP143によるとAsynchronous System Trapっぽい。