Планировщик ввода / вывода BFQ лучше

    Помимо атомарных операций 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 обновляет временные метки приложения так, чтобы учитывалось только полезное время, в течении которого обрабатывались запросы. Тот факт, что приложение не сумело обнулить очередь запросов, означает что пакет запросов превышал отведенный бюджет. Стало быть бюджет надо увеличить на заданную величину, которая не превышает некоторый пороговый уровень Bi,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-WF2Q+. Если теперь активных приложений не осталось из очереди планировщика B-WF2Q+ берется следующее и все по новой — для активного приложения очередной запрос R берется из вереницы подобных и ему присваивается бюджет.


    Наконец очередь активного приложения исчерпана. Новый таймер устанавливается равным текущему времени + Twait, в случае отсутствия новых запросов в дело вступает функция 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-WF2Q+.


    • C-LOOK (Circular LOOK) является планировщиком диска, в котором головка диска двигается от одного конца к другому, обслуживая поступившие запросы. Затем после последнего запроса, меняет направление на противоположное, не достигнув финиша в отличие от алгоритма C-SCAN.
    • B-WF2Q+ адаптированный для блочных устройств вариант планировщика пакетов WF2Q+. Алгоритм 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"

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


    Поделиться публикацией

    Похожие публикации

    Комментарии 26

      0
      Хорошо написано, спасибо.
      А про планировщик задач можете написать?
        0

        Спасибо за отзыв. Постараюсь, там тоже история заковыристая, но на данный момент бурлений вроде нет.

          0
          Как там MyQSS поживает? Ему в ванили всё так же не рады?
        +1
        Судя по данному тесту — www.phoronix.com/scan.php?page=article&item=linux-412-io&num=1
        не так то он хорош (в контексте теста, т.е. для ssd)
        Интересно было бы посмотреть аналогичный тест из демо-ролика для SSD
        +1
        multiqueue API

        только оно поломано в 4.12. Проявляется, к примеру, в полном зависании при выходе из сна. Выключение — решает проблему.


        Первые сборки 4.12 в Manjaro были с blk-mq. Теперь оставили только в экспериментальном 4.13, где так же есть данная проблема.


        В них планировщик BFQ используется по умолчанию.
        Manjaro

        Уже не совсем правда. При включенном blk-mq дефолтный планировщик теперь mq-deadline. А согласно тестированию фороникса, BFQ уже далеко не в лидерах (ссылка в предыдущем коментарии), по крайней мере для SSD.


        Стоит отметить, что при включенном blk-mq CFQ перестаёт быть доступным (по крайней мере для HDD) и среди возможных вариантов (мы про Manjaro): mq-deadline, kyber (тоже появился в 4.12), noop и bfq-mq. Лично я настроил правила udev и в данной конфигурации для HDD используется bfq-mq, тогда как для SSD — mq-deadline. Для системы без blk-mq — дефолтный планирощик (bfq-sq).


        А Kyber, судя по всему, должен быть хорош для современных SSD дисков. Но у меня SSD нет.

          0
          В моем случае проявляется поломанность более капитально: при значительной i/o нагрузке система фризится так, что даже alt-sysrq не помогает. И происходит это еще при старте системы :(
            0

            Да, в моём случае SysRq тоже не помогает. Так что природа, судя по всему — одна и та же.

              0
              Есть надежда, что в 4.14 пофиксят.
          +2

          Кстати, в статье явно не хватает ссылки: Two new block I/O schedulers for 4.12

            +1
            Там пишут, что kyber — это когда нужна высокая производительность, а bfq — когда нужны низкие задержки.

            Забавно, что выводы selectel'а полностью противоположные. И кому верить?
            +4
            Очень заинтересовали. Если дойдут руки, сравню на серверной синтетике.
              0
              Поделитесь потом?
                0

                Присоединяюсь, хотелось бы увидеть больше замеров: синтетических и прочих.

              0
              Подскажите, для Mageia — с какой версии планировщик уже по умолчанию BFQ, а с какой он есть, но не по умолчанию? (и есть ли вовсе)
              Интересует Mageia 5, Mageia 2.
              Хотелось бы проверить хотя бы на времени загрузки (ну и на типовом использовании): Mageia 5 у меня на быстром компе с SSD диском, Mageia 2 на старом двухъядернике с древним HDD 20GB.
                0

                Скорее всего с последней 6-й, так как ядро 4.12 вышло лишь в июле. Но на старой можно использовать кернел последней версии для проверки, если у вас только 5-я версия имеется.

                  0
                  У меня на 5й сейчас ядро 4.4.82, значит, пока не получится.
                  Кстати, я и не заметил как 6я магия вышла из беты…
                +1
                Хочу добавить, что Arch'евский пакет linux-ck в AUR великолепен, если хочется собрать своё ядро, очень удобно оформлен PKGBUILD. И даже выключить в нём BFQ не проблема, если захочется :)
                  0

                  Спасибо, я в итоге перешёл на ядро от Repo-ck из-за вашей наводки) Пока что работается как минимум не хуже чем на основном ядре.

                  0
                  Проверил у себя, для моего NVMe SSD никакого планировщика не используется, хотя доступны mq-deadline, kyber и bfq. Не могли бы вы пояснить ситуацию с NVMe? Так и не смог нагуглить никакой информации по этому вопросу.
                    0
                    Это, скорее всего, потому, что для NVMe SSD с его большой внутренней очередью и низким latency планировщик в принципе не нужен: лучше отправлять запросы сразу напрямую.
                    0

                    Опасная какая-то тема)) Попробовал у себя на арч линуксе на ноуте с SSD. Через две перезагрузки ноут перестал нормально загружаться и стал выдавать сообщения подобные сообщениям в этом треде. Вернулся я обратно на cfq, в общем)

                      0

                      Хотя на вышеуказанном ядре Repo-ck всё пока что работает нормально в том числе и на bfq планировщике.

                        0

                        А нет… казалось, что с вынутым кабелем зарядки ноут не стартует тоже. В общем… По-моему, стандратное ядро без дополнительных навесов — всё-таки вещь тоже хорошая...) По крайней мере работает во всех ситуациях стабильно и без глюков.

                      0
                      глядя на последний график, остается впечатление, что под OLTP БД deadline всё ещё самый подходящий.
                        0

                        Только надо включать этот планировщик аккуратно, потому что включение multiqueue API приводит к отключению non-multiqueue планировщиков (noop, cfq, deadline)

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

                        Самое читаемое