Книга: Разработка ядра Linux

Балансировка нагрузки

Балансировка нагрузки

Как уже рассказывалось ранее, планировщик операционной системы Linux реализует отдельные очереди выполнения и блокировки для каждого процессора в симметричной многопроцессорной системе. Это означает, что каждый процессор поддерживает свой список процессов и выполняет алгоритм планирования только для заданий из этого списка. Система планирования, таким образом, является уникальной для каждого процессора. Тогда каким же образом планировщик обеспечивает какую-либо глобальную стратегию планирования для многопроцессорных систем? Что будет, если нарушится балансировка очередей выполнения, скажем, в очереди выполнения одного процессора будет находиться пять процессов, а в очереди другого — всего один? Решение этой проблемы выполняется системой балансировки нагрузки, которая работает с целью гарантировать, что все очереди выполнения будут сбалансированными. Система балансировки нагрузки сравнивает очередь выполнения текущего процессора с другими очередями выполнения в системе.

Если обнаруживается дисбаланс, то процессы из самой загруженной очереди выполнения выталкиваются в текущую очередь, В идеальном случае каждая очередь выполнения будет иметь одинаковое количество процессов. Такая ситуация, конечно, является высоким идеалом, к которому система балансировки может только приблизиться.

Система балансировки нагрузки реализована в файле kernel/sched.c в виде функции load_balance(). Эта функция вызывается в двух случаях. Она вызывается функцией schedule(), когда текущая очередь выполнения пуста. Она также вызывается по таймеру с периодом в 1 мс, когда система не загружена, и каждые 200 мс в другом случае. В однопроцессорной системе функция load_balance() не вызывается никогда, в действительности она даже не компилируется в исполняемый образ ядра, питому что в системе только одна очередь выполнения и никакой балансировки не нужно.

Функция балансировки нагрузки вызывается при заблокированной очереди выполнения текущего процессора, прерывания при этом также запрещены, чтобы защитить очередь выполнения от конкурирующего доступа. В том случае, когда функция load_balance() вызывается из функции schedule(), цель ее вызова вполне ясна, потому что текущая очередь выполнения пуста и нахождение процессов в других очередях с последующим их проталкиванием в текущую очередь позволяет получить преимущества. Когда система балансировки нагрузки активизируется посредством таймера, то ее задача может быть не так очевидна. В данном случае это необходимо для устранения любого дисбаланса между очередями выполнения, чтобы поддерживать их в почти одинаковом состоянии, как показано на рис. 4.4.

Рис. 4.4. Система балансировки нагрузки

Функция load_balance() и связанные с ней функции сравнительно большие и сложные, хотя шаги, которые они предпринимают, достаточно ясны.

• Функция load_balance() вызывает функцию find_busiest_queue() для определения наиболее загруженной очереди выполнения. Другими словами — очередь с наибольшим количеством процессов в ней. Если нет очереди выполнения, количество процессов в которой на 25% больше, чем в дайной очереди, то функция find_busiest_queue() возвращает значение NULL и происходит возврат из функции load_balance(). В другом случае возвращается указатель на самую загруженную очередь.

• Функция load_balance() принимает решение о том, из какого массива приоритетов самой загруженной очереди будут проталкиваться процессы. Истекший массив является более предпочтительным, так как содержащиеся в нем задачи не выполнялись достаточно долгое время и, скорее всего, не находятся в кэше процессора (т.е. не активны в кэше, not "cache hot"). Если истекший массив приоритетов пуст, то ничего не остается, как использовать активный массив.

• Функция load_balance() находит непустой список заданий, соответствующий самому высокому приоритету (с самым маленьким номером), так как важно более равномерно распределять задания с высоким приоритетом, чем с низким.

• Каждое задание с данным приоритетом анализируется для определения задания, которое не выполняется, не запрещено для миграции из-за процессорной привязки и не активно в кэше. Если найдена задача, которая удовлетворяет этому критерию, то вызывается функция pull_task() для проталкивания этой задачи из наиболее загруженной очереди в данную очередь.

• Пока очереди выполнения остаются разбалансированными, предыдущие два шага повторяются и необходимое количество заданий проталкивается из самой загруженной очереди выполнения в данную очередь выполнения. В конце концов, когда дисбаланс устранен, очередь выполнения разблокируется и происходит возврат из функции load_balance().

Далее показана функция load_balance(), немного упрощенная, но содержащая все важные детали.

static int load_balance(int this_cpu, runqueue_t *this_rq,
 struct sched_domain *sd, enum idle_type idle) {
 struct sched_group *group;
 runqueue_t *busiest;
 unsigned long imbalance;
 int nr_moved;
 spin_lock(&this_rq->lock);
 group = find_busiest_group(sd, this_cpu, &imbalance, idle);
 if (!group)
  goto out_balanced;
 busiest = find_busiest_queue(group);
 if (!busiest)
  goto out_balanced;
 nr_moved = 0;
 if (busiest->nr_running > 1) {
  double_lock_balance(this_rq, busiest);
  nr_moved = move_tasks(this_rq, this_cpu, busiest,
   imbalance, sd, idle);
  spin_unlock(&busiest->lock);
 }
 spin_unlock(&this_rq->lock);
 if (!nr_moved) {
  sd->nr_balance_failed++;
  if (unlikely(sd->nr_balance_failed > sd->cache_nice_tries+2)) {
   int wake = 0;
   spin_lock(&busiest->lock);
   if (!busiest->active_balance) {
    busiest->active_balance = 1;
    busiest->push_cpu = this_cpu;
    wake = 1;
   }
   spin_unlock(&busiest->lock);
   if (wake)
    wake_up_process(busiest->migration_thread);
   sd->nr_balance_failed = sd->cache_nice_tries;
  }
 } else
  sd->nr_balance_failed = 0;
 sd->balance_interval = sd->min_interval;
 return nr_moved;
out_balanced:
 spin_unlock(&this_rq->lock);
 if (sd->balance_interval < sd->max_interval)
  sd->balance_interval *= 2;
 return 0;
}

Оглавление книги