3

私は現在、Robert Love の「Linux Kernel Development」を読んでいて、CFS についていくつか質問を受けました。私の質問は、 calc_delta_mine の計算方法です:

delta_exec_weighted= (delta_exec * 重量)/lw->重量

私はそれが2つのステップで行われると思います:

  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 (Shift right and round) マクロは次の方法で定義されます。

    #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_CONST32.32値としてw計算されます。1/w

2 つの 32.32 値を整数として乗算すると、結果が 2 32倍大きすぎることに注意してください。したがって、WMULT_SHIFT(=32) は、2 つの 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を計算できます。これは、フロアを で割った値を計算することによって SRR が行うことです。x + q/2qx + 2y-12y

于 2013-07-21T21:37:19.117 に答える