CFSの話 - sched_slice()で行われるタイムスライスの計算がさぱーり分からない
/* * Preempt the current task with a newly woken task if needed: */ static void check_preempt_tick(struct cfs_rq *cfs_rq, struct sched_entity *curr) { unsigned long ideal_runtime, delta_exec; ideal_runtime = sched_slice(cfs_rq, curr); delta_exec = curr->sum_exec_runtime - curr->prev_sum_exec_runtime; if (delta_exec > ideal_runtime) { /* ←ココの条件!*/ resched_task(rq_of(cfs_rq)->curr); /* * The current task ran long enough, ensure it doesn't get * re-elected due to buddy favours. */ clear_buddies(cfs_rq, curr); } }
ながーいコードで色々としているけど、究極的には←で示したif文の条件が切り替わる条件。
続くresched_task()でthread_infoにTIF_NEED_RESCHEDフラグを立て、ユーザモードへの復帰時にプリエンプトされる。
では、この条件はどういう意味だろう?
delta_execは単純に現在のプロセスがCPUを握っていた時間のはず。
これとideal_runtimeを比較してdelta_execが長くなってしまっていたら切り替え。
これはシンプルで分かりやすい。
けど、ideal_runtimeはどうやって算出してるんだろ?
/* * We calculate the wall-time slice from the period by taking a part * proportional to the weight. * * s = p*P[w/rw] */ static u64 sched_slice(struct cfs_rq *cfs_rq, struct sched_entity *se) { u64 slice = __sched_period(cfs_rq->nr_running + !se->on_rq); for_each_sched_entity(se) { struct load_weight *load; struct load_weight lw; cfs_rq = cfs_rq_of(se); load = &cfs_rq->load; if (unlikely(!se->on_rq)) { lw = cfs_rq->load; update_load_add(&lw, se->load.weight); load = &lw; } slice = calc_delta_mine(slice, se->load.weight, load); } return slice; }
この関数は要するに
calc_delta_mine(__sched_period(cfs_rq->nr_running + !se->on_rq), se->load.weight, load);
だと思う。
但し、sched_entityが複数の場合(これはどんな時に発生するのかな?グループスケジューリングの事?)は繰り返しcalc_data_mine()で計算を行うのだろう。
#if BITS_PER_LONG == 32 # define WMULT_CONST (~0UL) #else # define WMULT_CONST (1UL << 32) #endif #define WMULT_SHIFT 32 /* * Shift right and round: */ #define SRR(x, y) (((x) + (1UL << ((y) - 1))) >> (y)) /* * delta *= weight / lw */ static unsigned long calc_delta_mine(unsigned long delta_exec, unsigned long weight, struct load_weight *lw) { u64 tmp; if (!lw->inv_weight) { if (BITS_PER_LONG > 32 && unlikely(lw->weight >= WMULT_CONST)) lw->inv_weight = 1; else lw->inv_weight = 1 + (WMULT_CONST-lw->weight/2) / (lw->weight+1); } tmp = (u64)delta_exec * weight; /* * Check whether we'd overflow the 64-bit multiplication: */ if (unlikely(tmp > WMULT_CONST)) tmp = SRR(SRR(tmp, WMULT_SHIFT/2) * lw->inv_weight, WMULT_SHIFT/2); else tmp = SRR(tmp * lw->inv_weight, WMULT_SHIFT); return (unsigned long)min(tmp, (u64)(unsigned long)LONG_MAX); }
__sched_period()の返り値(delta_exec)とse->load.weightをかけてtmpに代入した所まではわかった。
が、その後がわからない。
オーバーフローが起きないようにしてるって言ってるけど、で、計算結果はどうなるんだ…?
マクロを展開すると、
if (tmp > (1UL << 32)) tmp = ((((((tmp) + (1UL << 15)) >> 16) * lw->inv_weight) + (1UL << 15) >> 16); else tmp = (((tmp * lw->inv_weight) + (1UL << 15)) >> 16);
になるみたいだけど。
このビットシフト演算がオーバーフローをケアする為だけのものだとして無視して良いとしたら、tmp = tmp * lw->inv_weightになるのか…?
そうすると結局、
slice = __sched_period(cfs_rq->nr_running + !se->on_rq) * se->load.weight * cfs_rq->load.inv_weight;
という事?
se->load.weightはプロセスの優先度からくる重み付けかなと思うけど、cfs_rq->load.inv_weightは何だろう。
最初のif(!lw->inv_weight)がtrueになると仮定して
cfs_rq->load.inv_weight == 1 + (WMULT_CONST-lw->weight/2) / (lw->weight+1) == 1 + ((1UL<<32)-lw->weight/2) / (lw->weight+1)
なのかな?
だとしても、何を意図しているのか結局良くわからないや。