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)

なのかな?
だとしても、何を意図しているのか結局良くわからないや。