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

 

Введение

Для начала вспомним, что такое планировщик ввода/вывода. Он отвечает за распределение дисковых операций по процессам. В ранних ядрах Linux (как минимум в ядре 2.4) существовал только один планировщик — Linus Elevator. Он был слишком примитивным, и поэтому в ядре 2.6 появились еще три планировщика, часть из которых ныне уже ушла в небытие. Таким образом, сейчас в ядре существует три планировщика, а в ближайшее время, возможно, прибавится еще и четвертый:

  • NOOP — наиболее простой планировщик. Он банально помещает все запросы в очередь FIFO и исполняет их вне зависимости от того, пытаются ли приложения читать или писать. Планировщик этот, тем не менее, пытается объединять однотипные запросы для сокращения операций ввода/вывода.
  • CFQ был разработан в 2003 году. Заключается его алгоритм в следующем. Каждому процессу назначается своя очередь запросов ввода/вывода. Каждой очереди затем присваивается квант времени. Планировщик же циклически обходит все процессы и обслуживает каждый из них, пока не закончится очередь либо не истечет заданный квант времени. Если очередь закончилась раньше, чем истек выделенный для нее квант времени, планировщик подождет (по умолчанию 10 мс) и, в случае напрасного ожидания, перейдет к следующей очереди. Отмечу, что в рамках каждой очереди чтение имеет приоритет над записью.
  • Deadline в настоящее время является стандартным планировщиком, был разработан в 2002 году. В основе его работы, как это ясно из названия, лежит предельный срок выполнения — то есть планировщик пытается выполнить запрос в указанное время. В дополнение к обычной отсортированной очереди, которая появилась еще в Linus Elevator, в нем есть еще две очереди — на чтение и на запись. Чтение опять же более приоритетно, чем запись. Кроме того, запросы объединяются в пакеты. Пакетом называется последовательность запросов на чтение либо на запись, которая идет в сторону б?льших секторов («алгоритм лифта»). После его обработки планировщик смотрит, есть ли запросы на запись, которые не обслуживались длительное время, и в зависимости от этого решает, создавать ли пакет на чтение либо же на запись.
  • BFQ (Budget Fair Queueing) — относительно новый планировщик. Базируется на CFQ. Если не вдаваться в технические подробности, каждой очереди (которая, как и в CFQ, назначается попроцессно) выделяется свой «бюджет», и, если процесс интенсивно работает с диском, данный «бюджет» увеличивается.

Но, как говорится, не все грибочки одинаково полезны — планировщик для домашнего компьютера (который мы и попытаемся выбрать в статье) отличается от планировщика для сервера.

 

INFO

В FreeBSD имеется фреймворк (GEOM scheduler framework), позволяющий создавать планировщики ввода/вывода. На текущий момент, однако, на нем базируется только планировщик rr.

 

Подготовка

Первым делом скачаем ядро и наложим патч BFQ (на момент написания статьи существовал для ядер по версию 3.13 включительно):

$ RELEASE=3.13.0-v7r2
$ git clone git://git.kernel.org/pub/scm/linux/kernel/git/stable/linux-stable.git linux
$ cd linux
$ git checkout -b stable-3.13 v3.13.7
$ wget -nd --no-parent --level 1 -r -R "*.html*" --reject $RELEASE http://algo.ing.unimo.it/people/paolo/disk_sched/patches/$RELEASE
$ patch -p1 < ./0001-block-cgroups-kconfig-build-bits-for-BFQ-v7r2-3.13.patch 
$ patch -p1 < ./0002-block-introduce-the-BFQ-v7r2-I-O-sched-for-3.13.patch 
$ patch -p1 < ./0003-block-bfq-add-Early-Queue-Merge-EQM-to-BFQ-v7r2-for-3.13.0.patch 
$ cp /boot/config-`uname -r` ./.config

Затем включим этот планировщик в Enable the block layer -> IO Schedulers (планировщик по умолчанию можно оставить стандартный — все равно их можно переключать как во время работы, так и используя опции ядра) и скомпилируем ядро:

$ fakeroot make-kpkg --initrd --append-to-version=-my kernel_image kernel_headers

Перед этим нужно убедиться, что в файле /etc/kernel-pkg.conf стоит многопоточная сборка (параметр CONCURRENCY_LEVEL в идеале должен быть равен количеству ядер процессора плюс один).

Включение планировщика BFQ в menuconfig
Включение планировщика BFQ в menuconfig

Следом же устанавливаем получившиеся пакеты:

$ sudo dpkg -i ../linux-image-3.13.7-my+_3.13.7-my+-10.00.Custom_amd64.deb ../linux-headers-3.13.7-my+_3.13.7-my+-10.00.Custom_amd64.deb 

И перезагружаемся.

Помимо ядра, нужно установить некоторые пакеты для собственно бенчмаркинга:

$ sudo apt-get install hdparm bonnie++ 

Наконец можно приступать к тестированию.

Установка Bonnie++
Установка Bonnie++
 

Тюнинг планировщиков

Как правило, планировщики не требуют тонкой подстройки. Однако если тебе захочется поэкспериментировать — такая возможность у нас есть. Рассмотрим некоторые параметры подстройки BFQ, находящиеся (в моем случае) в каталоге /sys/block/sda/queue/iosched:

  • slice_idle — время ожидания поступления запросов (в миллисекундах). По умолчанию 8;
  • quantum — число запросов ввода/вывода, передаваемых дисковому контроллеру за один раз (тем самым ограничивая длину очереди). Нужно соблюдать осторожность при его увеличении, поскольку при высокой нагрузке система может начать тормозить. По умолчанию 4;
  • low_latency — для интерактивных процессов и процессов мягкого реального времени при значении по умолчанию пытается дать меньшую задержку, чем для других процессов. Процессы эти определяются эвристически;
  • max_budget — максимальный бюджет для очереди, измеряющийся в секторах. Разумеется, этот бюджет применяется для очереди с учетом всех временных лимитов. Значение по умолчанию равно нулю и включает автоматическую подстройку данного параметра.
 

Тестирование

Прежде чем приступить к проведению бенчмарков, нужно рассказать о тестовом стенде. Железо: материнская плата ASUS Sabertooth 990FX R2.0, 16 Гб RAM, Seagate ST3000DM001-1CH166. ПО: Xubuntu 13.10 x64 с ядром 3.13.7. Также в моем случае имело смысл создать отдельный раздел как минимум вдвое большего объема, чем вся доступная оперативная память, что я и сделал, создав таковой в размере 35 Гб с файловой системой ext4. Сначала удостоверимся, что текущий планировщик для диска — Deadline, для чего наберем следующую команду:

$ cat /sys/block/sda/queue/scheduler

Текущий планировщик выделяется квадратными скобками.

Первый бенчмарк, который я проведу, будет тест чтения с помощью утилиты hdparm — хотя предназначена она для тонкой подстройки параметров HDD, в ней есть и бенчмарк.

# hdparm -tT /dev/sda

Для более точного результата лучше запускать эту команду три — пять раз.

Следующим бенчмарком будет тест с помощью команды dd. Этот тест тоже достаточно полезен для оценки производительности ввода/вывода, хоть и кажется примитивным.

# cd /media/rom/benchmarking
# time dd if=/dev/zero of=./benchfile bs=1M count=19900 conv=fdatasync,notrunc

Затем нужно будет очистить кеш, записав цифру 3 в файл /proc/sys/vm/drop_caches. Запись этой цифры в данный файл очищает как страничный кеш, так и кеш инод с dentry. Лишь после очистки можно будет запустить вторую часть теста:

# time dd if=./benchfile of=/dev/null bs=1M count=19900

Как и в случае с hdparm, обе части теста лучше запустить несколько раз.

Переходим к очередному тесту — им у нас будет распаковка архива с ядром. Скачиваем его и запускаем распаковку (опять же три — пять раз):

# wget https://www.kernel.org/pub/linux/kernel/v3.x/linux-3.13.7.tar.xz
# time tar xJf linux-3.13.7.tar.xz

Следующий тест будет сделан с помощью утилиты Bonnie++, о которой стоит рассказать подробнее. Это крайне гибкий набор бенчмарков для тестирования производительности ввода/вывода. Операции с файлами, к сожалению, не сводятся только к последовательному чтению/записи одного файла или к распаковке архива, поэтому приведенные тесты не дают однозначного результата для всех ситуаций. Bonnie++ же, хоть и является синтетическим тестом, более реалистично симулирует обращения к подсистеме ввода/вывода. Так, в число тестов входит симуляция работы СУБД — в данном случае создается файл (либо файлы, если указан размер больший, чем 1 Гб) и производится как последовательное, так и рандомное чтение/запись, при этом чтение в несколько потоков. Помимо этого теста есть еще тест на создание/изменение/удаление тысяч маленьких файлов. Опции у данного приложения следующие:

  • -d — каталог для работы программы;
  • -s — размер файла в мегабайтах для первого теста (симуляция работы СУБД). Как я уже сказал, если размер будет указан больший, чем 1 Гб, файлов будет больше одного;
  • -n — количество файлов для второго теста (симуляция работы Squid или какого-нибудь сервера электронной почты, использующего для хранения писем файлы). Формат аргумента таков: num:max_size:min_size:num_dirs, где num — количество файлов, кратное 1024, max_size и min_size — соответственно, максимальный и минимальный размер в байтах для создаваемых файлов (по умолчанию оба этих размера равны нулю, если же их установить, размер файлов будет задаваться рандомно), а num_dirs — количество каталогов, в которых файлы будут размещаться;
  • -x — количество проходов тестов;
  • -q — «тихий» режим. Кроме результатов теста и ошибок, ничего не выводится;
  • -u — пользователь, под которым запускать тесты. Поскольку они сильно нагружают, пользователь root не рекомендуется — во избежание всяческих ошибок.

Итоговые команды будут следующими:

# mkdir rom && chown rom:rom rom
$ bonnie++ -d ./rom -n 115:25381:0:27 -x 5 -q > ~/bonnie_out_deadline.csv

То есть запускаем пять проходов тестов в текущей директории с количеством файлов 115*1024, максимальным размером 25 381 байт, количеством каталогов 27 в «тихом» режиме. Затем нужно преобразовать этот самый CSV в удобочитаемый вид, для чего в составе пакета есть утилиты — можно преобразовывать как в txt, так и в HTML:

$ cat ~/bonnie_out_deadline.csv |bon_csv2html > ~/bonnie_out_deadline.html

Напомню, что данные тесты нужно проводить на всех планировщиках, а не только на текущем. Для их переключения есть два способа. Первый способ — использовать параметр загрузки ядра elevator. При этом нужно будет редактировать файл /etc/default/grub и обновлять загрузочный конфиг GRUB. Второй способ не требует перезагрузки и состоит в указании планировщика через sysfs. Например, для указания планировщика CFQ на устройстве /dev/sda достаточно следующей команды:

# echo cfq > /sys/block/sda/queue/scheduler

Лично мне в конечном итоге оказалось проще написать скрипт, который запускает по пять проходов каждого теста (за исключением Bonnie++ — в нем указывается параметр -x) для каждого планировщика. Посмотрим же, что у нас получилось.

Скрипт для бенчмарка
Скрипт для бенчмарка

 

Немного о процессе добавления BFQ в основную ветку ядра

Я начал работу над BFQ вместе с Фабио Чеккони (Fabio Checconi) в 2008 году. Фабио написал первую версию кода. Затем мы протестировали его, исправили ошибки и немного улучшили функционал. Мы думали, что этого будет достаточно для добавления в ядро:

Однако BFQ не приняли в основную ветку ядра, несмотря на позитивный отклик общественности. Причиной тому послужили замечания Дженса Аксбо (Jens Axboe). С одной стороны, он был обеспокоен сложностью движка планировщика, сетовал на то, что эта сложность обернется проблемами с поддержкой кода, если его добавят в ядро. С другой — он был убежден, что в Linux должен быть только один главный планировщик ввода/вывода. Им был (и есть) CFQ.

Хотя BFQ не вошел в ядро, некоторые продвинутые пользователи стали скачивать его с нашего сайта. BFQ также был включен в некоторые модифицированные ядра, например Zen Kernel.

Тем временем я наткнулся на одну занимательную ветку LKML по теме ввода/вывода. В ней обсуждалось время старта некоторых популярных приложений, таких как Firefox и терминал. Я был поражен, насколько оно может быть мало. По сути, такое время достигалось только при последовательном чтении соответствующего бинарного файла. Я вдохновился этой идеей и придумал новую фичу для планировщика: необходимо определять и давать привилегии интерактивным приложениям. После добавления этого и некоторых других незначительных улучшений я представил BFQ-v1 в июле 2010-го.

С этого момента BFQ начал набирать обороты: за прошедшие годы некоторые модифицированные Linux-ядра, Android-ядра, дистрибутивы Linux приняли BFQ в качестве планировщика по умолчанию или дополнительного планировщика (pf-kernel, многие ядра для Android, CyanogenMod, Sabayon, Gentoo Linux, Arch Linux, OpenMandriva, Rosa, ныне Manjaro). Кроме того, по моим данным, в течение последних нескольких лет каждый день планировщик скачивают несколько десятков пользователей разных дистрибутивов.

Между тем я продолжал добавлять новые функции и усовершенствования, например эвристические методы распознавания интерактивных приложений. Я добавил поддержку новых характеристик жестких дисков, например NCQ, а также оптимизировал работу с SSD. К счастью, в этой работе мне помогали такие хорошие люди, как Франческо Аллертсен (Francesco Allertsen), Мауро Андреолини (Mauro Andreolini) и особенно Арианна Аванцини (Arianna Avanzini). За несколько лет она внесла большой вклад в проект BFQ, разработала новые решения и подготовила патчи для множеств версий ядра.

Все расширения для правильной обработки новых устройств, которые Арианна и я добавили в BFQ, были до этого добавлены и в CFQ. Вместе с этим в CFQ появлялись некоторые другие полезные функции. Мы не только портируем все эти функции в BFQ, но и по возможности дорабатываем их для улучшения пропускной способности, времени отклика и быстроты исполнения. Так, нами был разработан унифицированный механизм обработки ввода/вывода QEMU для достижения высоких показателей пропускной способности.

Поддерживать такую высокую скорость разработки совсем не легко. Без поддержки Арианны проект, скорее всего, пришлось бы закрыть. Однако с выходом версии v7r3 мы в конце концов сделали это: теперь BFQ поддерживает весь спектр популярных устройств для хранения информации. Кроме этого, весь функционал, который я планировал реализовать, теперь работает стабильно. Наконец-то код выглядит зрелым и достаточно стройным.

Вот почему я думаю, что сейчас BFQ готов для представления в LKML. С этой целью мы уже подготовили патчсет для ревью. Но, прежде чем приступить к добавлению в основную ветку, нам нужно закончить тестирование версии v7r3 и выпустить релиз. Надеюсь, мы сможем это сделать в ближайшую неделю.

Паоло Валенте (Paolo Valente), основатель планировщика BFQ

 

Анализ результатов тестирования

Поскольку написание статьи связано с планировщиком BFQ, сосредоточимся именно на нем.

Запись с помощью dd у меня заняла в среднем 137,71 с, что, конечно, немного больше, чем при использовании планировщика Deadline (в среднем 136,89 с), но меньше, чем при использовании других планировщиков, — например, при сравнении с CFQ BFQ опережает его почти на 4 с.

Чтение же с помощью dd столь значительной разницы не показало. Тем не менее в этом тесте BFQ впереди планеты всей, а CFQ опять аутсайдер.

Тесты с помощью hdparm (чтение как из кеша, так и из дискового буфера) по неизвестным причинам вывели на первое место планировщик Deadline. Впрочем, полагаться на результат именно этого теста особого смысла нет — выглядит он слишком уж синтетическим.

Замер общего времени выполнения распаковки ядра с помощью команды time снова вывел BFQ на второе место — хотя и этот тест выглядит не менее синтетическим, чем предыдущий.

Таблица результатов моих собственных тестов
Таблица результатов моих собственных тестов

А теперь перейдем к результатам Bonnie++. Результатов там много, но я покажу только самые основные. Рассматривать я буду исключительно максимальную задержку для одной операции (опять же усредненную). При использовании функции putc() задержка у нашего кандидата на включение в ядро составляет 12 901 мкс, что выводит его на первое место. То же самое можно сказать и про запись блока — при данном тесте BFQ вырывается далеко вперед. А вот при чтении блока выигрывает CFQ с его 9082,6 мкс, BFQ же в этом тесте (как и в тесте на перезапись блока) стоит на втором месте. В тесте последовательного создания файлов BFQ на втором месте, зато в тестах рандомного создания/удаления он вновь лидирует.

Таблица результатов (среднее значение задержки) для Bonnie++
Таблица результатов (среднее значение задержки) для Bonnie++

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

 

Оставить мнение

Check Also

Алмазный фонд «Хакера». Самые крутые материалы по реверсингу и malware за три года

Иногда мы, редакторы и авторы «Хакера», сами читаем «Хакер». Нет, ну то есть мы постоянно …