Объяснение функции calc_delta_mine

Question

В настоящее время я читаю «Развитие ядра Linux» Роберта Лава, и у меня появилось несколько вопросов о CFS. Мой вопрос заключается в том, как calc_delta_mine вычисляет:

delta_exec_weighted = (delta_exec * вес) вес

/lw-> Я предполагаю, что это делается в два этапа:

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); 
   

СРР (Сдвиг вправо и раунд) макрос определяется с помощью:

#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/2y.

Чтобы развернуть результат деления x/q вы можете рассчитать x + q/2 с полом - на q; это то, что делает SRR, вычисляя x + 2y-1 поделенный на 2y.