请问一个看不懂的函数

peimichael

在CFS的sched_fair.c中有这么一个函数
根据注释和网上的讲解，它计算的应该是delta_exec * weight / lw->weight，可能只是近似计算
但是我数学不好，怎么都看不懂这个简单的函数，不知道哪位能帮忙解释一下
我把该函数和里面用到的定义一并贴出来了，假设是32位机器

# define WMULT_CONST&nbsp;&nbsp;&nbsp;&nbsp;(~0UL) #define WMULT_SHIFT&nbsp;&nbsp;&nbsp;&nbsp;32 #define SRR(x, y) (((x) + (1UL << ((y) - 1))) >> (y)) /* &nbsp;* delta *= weight / lw &nbsp;*/ static unsigned long calc_delta_mine(unsigned long delta_exec, unsigned long weight, &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;struct load_weight *lw) { &nbsp;&nbsp;&nbsp;&nbsp;u64 tmp; &nbsp;&nbsp;&nbsp;&nbsp;if (!lw->inv_weight) { &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if (BITS_PER_LONG > 32 && unlikely(lw->weight >= WMULT_CONST)) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;lw->inv_weight = 1; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;else &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;lw->inv_weight = 1 + (WMULT_CONST-lw->weight/2) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;/ (lw->weight+1); &nbsp;&nbsp;&nbsp;&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp;tmp = (u64)delta_exec * weight; &nbsp;&nbsp;&nbsp;&nbsp;/* &nbsp;&nbsp;&nbsp;&nbsp; * Check whether we'd overflow the 64-bit multiplication: &nbsp;&nbsp;&nbsp;&nbsp; */ &nbsp;&nbsp;&nbsp;&nbsp;if (unlikely(tmp > WMULT_CONST)) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;tmp = SRR(SRR(tmp, WMULT_SHIFT/2) * lw->inv_weight, &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;WMULT_SHIFT/2); &nbsp;&nbsp;&nbsp;&nbsp;else &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;tmp = SRR(tmp * lw->inv_weight, WMULT_SHIFT); &nbsp;&nbsp;&nbsp;&nbsp;return (unsigned long)min(tmp, (u64)(unsigned long)LONG_MAX); }

emmoblin

太深奥了,看不懂,应该都是为了防止相乘之后越界,再一个就是用移位来近似代替除法.

peimichael

原帖由 emmoblin 于 2010-1-21 14:43 发表
太深奥了,看不懂,应该都是为了防止相乘之后越界,再一个就是用移位来近似代替除法.

看来看去，觉得好像就这么两句话是关键
tmp = (u64)delta_exec * weight;
tmp = SRR(tmp * lw->inv_weight, WMULT_SHIFT);
上面的inv_weight好像是2^32/lw->weight的近似值，
但是又不明白为什么这个近似值要用下面这个式子来算，
1 + (WMULT_CONST-lw->weight/2)/ (lw->weight+1)
这个式子也没有避免除法啊。

其他代码好像确实向楼上所说都是在避免溢出