Помимо атомарных операций KMS для пользователей рабочей станции Linux недавно завезли еще одно полезное новшество — планировщик подсистемы ввода и вывода BFQ (Budget Fair Queue). Он является усовершенствованием дефолтного CFQ (Completely Fair Queue), дебютировал аж 9 лет назад, но только в версии 4.12 попал в основную ветку.

Прежде чем поговорить о принципах работы планировщика ознакомьтесь с демо-роликом разработчика Paolo Valente, это добавит вам мотивации продолжить. На снимке экрана показан замер старта проигрывателя с 10 фоновыми задачами читать файл с диска для двух планировщиков: CFQ и BFQ. Угадайте, который из них так и не стартовал при такой нагрузке?

Теперь вкратце об алгоритме. Так же как в CFQ синхронные запросы группируются в очередях по задачам, а асинхронные — по устройствам. Затем BFQ для новых задач преобразует простой планировщик Round Robin, основанный на временных отметках, так, что алгоритм берет за основание бюджеты, в которых мерой служат дисковые сектора. В зависимости от характера и поведения задачи бюджет может изменяться, а BFQ гарантирует, что поток дисковых данных будет адекватно распределяться между задачами.

BFQ в каждый данный момент работает лишь с одной задачей. Когда драйвер устройства готов обслуживать следующую задачу, алгоритм запрашивает из очереди первую в порядке заданном C-LOOK и передает ее на исполнение драйверу.

Бюджетная политика планировщика

Давайте рассмотрим более подробно отдельные аспекты алгоритма в псевдокоде. Функция add_request доавляет в очередь новый запрос R и если других запросов не поступило, то на этом все.

active_appl = none ; //приложение активное в данный момент
remaining_budget = 0 ; //остаток бюджета активного приложения

//ввод: индекс приложений, запрос отправленный приложением

add_request(int i, request R) {

appl = applications[i] ; //указание на приложение i

  // добавляем в очередь приложение R;
  enqueue(R, appl.queue) ;

  if (appl.queue.size == 1) { //очередь была пуста
    if (appl != active_appl)
      b-wf2q+_insert(appl) ;
    else //приложение является активным
      if(waiting_for_next_req()) //обманчивое затишье
        unset_timer() ; //поступил следующий запрос
  }
}

Логическая схема планировщика.

На диаграмме стрелы указывают на путь, от запроса до дискового устройства, а эллипсы — алгоритмы и операции.

Функция dispatch возвращает значение no request, если все приложения бездействуют, или активное приложение ожидает поступление следующего запроса. С другой стороны, приложение выводится из списка, если не успевает выполнить запрос в отведенный ей бюджет. Вызов функции b?wf2q+update_vfintime обновляет временные метки приложения так, чтобы учитывалось только полезное время, в течении которого обрабатывались запросы. Тот факт, что приложение не сумело обнулить очередь запросов, означает что пакет запросов превышал отведенный бюджет. Стало быть бюджет надо увеличить на заданную величину, которая не превышает некоторый пороговый уровень B_i,max.

request dispatch() { //
  if (all_applic_are_idle() OR waiting_for_next_req())
    return no_request ;

  if(active_appl ! = none AND
    remaining budget <
    C?LOOK next req (active_appl.queue).size ) {
      b?wf2q+update_vfintime(active_appl,
      active_appl.budget ? remaining_budget);

      if(active_appl.budget + BUDG_INC_STEP <=
        active_appl. max_budget)
        active_appl.budget += BUDG INC STEP ;
      else
        active_appl.budget = active_appl.max budget ;

      b?wf2q+ insert(active_appl) ;
      active_appl = none ;
}

      if (active_appl == none ) {
//получить и извлечь следующее активное приложение из b-wf2q+
        active_appl = b?wf2q+ get_next_application() ;
        remaining budget = active_appl.budget ;
}

// получить и изъять из очереди активного приложения следующий запрос
      next_request = dequeue_next_req(active_appl.queue) ;

      remaining budget ?= next_request.size;
      if(is empty (active_appl.queue))
      set_timer(T_wait) ; //начинается ожидание следующего запроса

//отчитываем сервис в b-wf2q+
      b-wf2q+_inc_tot_service(next_request.size) ;

      return next_request ;

Далее, приложение с новым бюджетом попадает в планировщик B-WF²Q+. Если теперь активных приложений не осталось из очереди планировщика B-WF²Q+ берется следующее и все по новой — для активного приложения очередной запрос R берется из вереницы подобных и ему присваивается бюджет.

Наконец очередь активного приложения исчерпана. Новый таймер устанавливается равным текущему времени + T_wait, в случае отсутствия новых запросов в дело вступает функция timer_expiration. Приложению объявляется простаивающим и новый получает новый бюджет равный предыдущему.

timer_expiration()
    active_appl.budget = active_appl.budget ? remaining_budget ;
    b-wf2q+_update_vfintime(active_appl, active_appl.budget); 
    active_appl = none ; //активных приложение не осталось,
//dispatch() выберет следующее приложение.

Стоит еще упомянуть о внутренних алгоритмах: C-LOOK B-WF²Q+.

• C-LOOK (Circular LOOK) является планировщиком диска, в котором головка диска двигается от одного конца к другому, обслуживая поступившие запросы. Затем после последнего запроса, меняет направление на противоположное, не достигнув финиша в отличие от алгоритма C-SCAN.
• B-WF²Q+ адаптированный для блочных устройств вариант планировщика пакетов WF²Q+. Алгоритм Weighted Fair Queue позволяет задать каждому потоку свой приоритет, или вес, пропорционально которому выделяется часть канала.

Так в чем же дело?

Тут следует разместить картинку Боромира, который с раздражением пытается сказать, что нельзя просто взять и добавить планировщик в основную ветку Linux ядра. Помимо вылизанного до зеркально блеска кода тут нужно терпение и продвинутые социальные навыки коммуникации. Нет никаких осязаемых причин из-за которых следовало так долго мариновать BFQ и остается лишь аплодировать непреклонной настойчивости его автора. Официальной причиной отказа принять новый лучший планировщик было отсутствие поддержки нового multiqueue API, так как BFQ умел только в предшествующее API блочных устройств. Благо на помощь пришел Йенс Эксбое (Jens Axboe) — мейнтейнер multiqueue API, и вместе они сумели добиться нужного результата.

Старт приложения gnome-terminal на Hitachi HDD (меньшее — лучше).

На данный момент пользователи этих дистрибутивов могут спокойно смотреть фильмы во время копирования файла с флешки, распаковки большого архива и прочих требовательных к ресурсам I/O операциях. В них планировщик BFQ используется по умолчанию.

• Manjaro
• Mageia
• OpenMandriva
• Sabayon
• Arch Linux ARM
• ROSA

Производительность на Hitachi HDD (большее — лучше).

По выбору, планировщик BFQ доступен в:

• Arch
• openSUSE
• PCLinuxOS
• Gentoo

Тут требуется совершить несколько простых действий. Во-первых поменять строку загрузчика GRUB, чтобы она выглядела так:

GRUB_CMDLINE_LINUX="scsi_mod.use_blk_mq=1"

Далее после перезагрузки проверить наличие требуемого планировщика.

(5:500)$ sudo cat /sys/block/sda/queue/scheduler
noop bfq deadline [cfq]

Меняем планировщик по умолчанию.

(5:501)$ sudo echo bfq > /sys/block/sda/queue/scheduler

Можно сделать это более основательно, применив правило udev, записав файл /path/to/rules.d/60-scheduler.rules.

ACTION=="add|change", KERNEL=="sd[a-z]", ATTR{queue/scheduler}="bfq"

Материалы по теме

• A way forward for BFQ
• Budget Fair Queueing (BFQ) Storage-I/O Scheduler
• High Throughput Disk Scheduling with Fair Bandwidth Distribution
• What Excites Me The Most About The Linux 4.12 Kernel