3

我目前正在阅读 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->weight （或 * 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 位乘法溢出吗？请解释一下这个函数中宏的定义((~0UL) ,(1UL << 32))？

4

1 回答 1

4

您发布的代码基本上是使用 32.32 定点算术进行计算，其中单个 64 位数量在高 32 位中保存数字的整数部分，在低 32 位中保存数字的小数部分（所以，例如，1.5 在这个系统中是 0x0000000180000000）。WMULT_CONST因此是 1.0 的近似值（使用一个适合long平台效率考虑的值），因此除以WMULT_CONST计算w为1/w32.32 值。

请注意，将两个 32.32 值作为整数相乘会产生 2 32倍大的结果；因此，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 / 2y

要舍入除法的结果，x/q您可以计算x + q/2除以q; 这就是 SRR 通过计算除以 的下限所做的。x + 2y-12y

于 2013-07-21T21:37:19.117 回答