linux-kernel - calc_delta_mine 函数的解释

Question

我目前正在阅读 Robert Love 的“Linux Kernel Development”，我有几个关于 CFS 的问题。我的问题是 calc_delta_mine 如何计算:

delta_exec_weighted= (delta_exec * weight)/lw->weight

我想这是通过两个步骤完成的:

1. 计算 (delta_exec * 1024) :

    if (likely(weight > (1UL << SCHED_LOAD_RESOLUTION)))
    tmp = (u64)delta_exec * scale_load_down(weight);
      else
    tmp = (u64)delta_exec;
   

2. 计算/lw->权重(或 * lw->inv_weight):

     if (!lw->inv_weight) {
     unsigned long w = scale_load_down(lw->weight);
     if (BITS_PER_LONG > 32 && unlikely(w >= WMULT_CONST))
               lw->inv_weight = 1;
       else if (unlikely(!w))
               lw->inv_weight = WMULT_CONST;
       else
               lw->inv_weight = WMULT_CONST / w;
    }
   
    /*
     * 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);
   

SRR(右移和舍入)宏是通过以下方式定义的:

    #define SRR(x, y) (((x) + (1UL << ((y) - 1))) >> (y))

并且定义了其他宏:

    #if BITS_PER_LONG == 32
    # define WMULT_CONST    (~0UL)
    #else
    # define WMULT_CONST    (1UL << 32)
    #endif
    #define WMULT_SHIFT     32

谁能解释一下 SRR 的工作原理以及它如何检查 64 位乘法溢出？请解释一下这个函数中MACROS的定义((~0UL) ,(1UL << 32))?

Answer 1

您发布的代码基本上是使用 32.32 定点运算进行计算，其中单个 64 位数量在高 32 位中保存数字的整数部分，在低 32 位中保存数字的小数部分(因此，例如，1.5 在此系统中为 0x0000000180000000)。 WMULT_CONST因此是 1.0 的近似值(出于平台效率方面的考虑，使用可以适合 long 的值)，因此除以 WMULT_CONST。通过 w计算 1/w作为 32.32 值。

请注意，将两个 32.32 值相乘作为整数会产生 2³² 倍大的结果；因此，WMULT_SHIFT (=32) 是将两个 32.32 值相乘的结果归一化为 32.32 所需的右移值。

在 sched/sched.h 中的评论中解释了使用这种改进的精度进行调度的必要性。 :

/*
 * Increase resolution of nice-level calculations for 64-bit architectures.
 * The extra resolution improves shares distribution and load balancing of
 * low-weight task groups (eg. nice +19 on an autogroup), deeper taskgroup
 * hierarchies, especially on larger systems. This is not a user-visible change
 * and does not change the user-interface for setting shares/weights.
 *
 * We increase resolution only if we have enough bits to allow this increased
 * resolution (i.e. BITS_PER_LONG > 32). The costs for increasing resolution
 * when BITS_PER_LONG <= 32 are pretty high and the returns do not justify the
 * increased costs.
 */

至于SRR ，从数学上讲，它计算了 x / 2<sup>y</sup> 的四舍五入 结果.

舍入除法结果x/q你可以计算出x + q/2楼层-分q ;这就是 SRR 通过计算 x + 2<sup>y-1</sup> 所做的事情楼层-分2<sup>y</sup> .