Планировщики ввода-вывода в Linux

Это мой перевод вот этой статьи.
При переводе я немного сократил статью, убрав из нее повторения и очевидные вещи.
Введение
Наверняка всем известно, что ядро Linux является очень сложным. Оно может работать на широком спектре имеющегося оборудования: во встраиваемых устройствах (в том числе и тех, которые нуждаются в операционных системах реального времени), портативных устройствах, ноутбуках, рабочих станциях, серверах общего назначения, серверах баз данных, видео-серверах, DNS-серверах, на суперкомпьютерах различного масштаба, и т.д. Системы разного назначения предъявляют к ядру системы самые разные и порой противоречивые требования. Некоторые из них требуют, что система должна быть отзывчивой на все действия пользователя, не прерывая музыку, видео или работу прочих приложений, требующих внимания пользователя. В то же время, обязательно существуют требования к хорошей производительности системы ввода-вывода и для некоторых сфер применения эти требования очень высокие. Для обеспечения сбалансированного распределения ресурсов между пользователями и разными процессами, в ядре Linux используется концепция планировщиков.
Планировщики предназначены именно для того, о чем говорит их название - они планируют различные операции внутри ядра системы. Поскольку в данной статье мы рассматриваем только ввод-вывод, то и под термином «планировщик» далее будет пониматься только планировщик ввода-вывода. Далее будет рассмотрена общая концепция планировщиков ввода-вывода и возможные их параметры.
Основные идеи, заложенные в планирование ввода-вывода
Практически все приложения на Linux используют какие-либо операции ввода-вывода. Даже такое с виду простое занятие как веб-серфинг производит большое количество маленьких файлов, которые записываются на диск. Без планировщик, каждый раз когда происходит запрос на ввод-вывод, происходило бы взаимодействие с ядром и такие операции бы выполнялись немедленно. Более того, может возникнуть такая ситуация, когда вы можете получить огромное количество запросов на ввод-вывод, которое (чтобы удовлетворить все запросы пользователя) заставит головки диска буквально метаться по нему стороны в сторону. Еще важнее то, что со временем разница между производительностью жестких дисков и остальной системы выросла очень быстро, что означает предъявление ещё больших требований к вводу-выводу для обеспечения общей высокой производительности системы. Так, когда ядро должно обслужить прерывание — приостанавливается работа всех остальных приложений. Поэтому, со стороны это может выглядеть как снижение отзывчивости системы или даже как замедление ее работы.
Так каким же образом следует спланировать обслуживание запросов на ввод-вывод, чтобы при этом обеспечить высокую скорость и не жертвовать отзывчивостью системы? Ответ на данный вопрос, как и большинство других вещей, зависит от общей загрузки и назначения системы. В одних случаях было бы здорово производить операции ввода-вывода параллельно с другими. В других случаях, необходимо производить ввод-вывод как можно быстрее. Концепция планирования ввода-вывода (на самом деле это довольно старая концепция) и появилась для того, чтобы найти баланс между этими двумя крайними состояниями таким образом, чтобы одна операция не прерывала другую (по крайней мере, до тех пор пока это явно не будет нужно вам).
Планирование событий ввода-вывода несет в себе необходимость решения многих вопросов. К примеру, планировщику необходимо хранить поступившие запросы в специальной очереди. Каким образом он будет хранить эти события, возможно ли будет изменить порядок событий, сколько времени будут хранится эти события, будут ли выполняться все сохранённые события по достижению определенных условий или с какой-то периодичностью - все это очень важные аспекты работы планировщика. От того как именно реализованы перечисленные аспекты работы планировщика зависит общая производительность работы системы ввода-вывода и то, как воспринимается эта система пользователями.
Самое главное с чего следует начать при рассмотрении архитектуры планировщика или настройки существующих планировщиков — это определение назначения, функций и роли системы. Например, целевая система — рабочая станция, которая используется в основном для веб-серфинга, иногда для просмотра видео и/или прослушивания музыки, и может быть даже игр. Задача кажется простой, но тем не менее имеет свои подводные камни. Например, если вы смотрите видео, слушаете музыку или играете в игру, вы скорее всего не хотите, чтобы при этом возникали какие-то задержки или пропадали какие-то кадры, видео бы постоянно прерывалось и показывалось бы рывками. Или, как только вы приготовитесь снести голову какому-нибудь зомби-мутанту, система подвиснет как раз в момент вашего выстрела и когда она снова возобновит работу, вдруг окажется, что зомби уже опередил вас и ваш герой убит. И хотя «заикание» во время воспроизведения какой-нибудь музыки вполне может быть частью жанра, в большинстве случаев это сильно раздражает. Поэтому, если ваша целевая система представляет собой рабочую станцию, Вы возможно захотите как можно меньше задержек в ее работе и это имеет огромное влияние на алгоритм работы планировщика.
Одним из важных преимуществ, которое планирование ввода-вывода дает системе — является хранение различных событий в очереди и даже возможность ее (очереди) изменения для совершения отдельных операций ввода-вывода быстрее других. Поскольку скорость операций ввода-вывода может оказаться значительно медленнее, чем в других частей системы, перераспределение запросов на обращение к диску таким образом, чтобы минимизировать перемещение головок диска может повысить общую производительность работы системы. Новые файловые системы тоже могут работать с учетом некоторых из этих концепций, поэтому они вполне могут сами оптимизировать операции ввода-вывода с точки зрения скорости работы устройства хранения данных. Вы даже можете путем настройки самого планировщика эффективнее адаптировать систему к необычным свойствам SSD (твердотельные накопители не имеют головок чтения-записи по сравнению с традиционными жесткими дисками — прим. перев.).
Есть несколько типичных методов, которые используются планировщиками ввода-вывода:

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

• «Алгоритм лифта»: Запросы ввода-вывода упорядочиваются исходя из физического размещения данных на диске таким образом, чтобы головки диска как можно больше перемещались в одном направлении и как можно более упорядоченно.

• Переупорядочение запросов: Эта техника переупорядочивает запросы на основе их приоритета. Алгоритм реализации данной техники зависит от конкретного планировщика.

• Кроме того, почти все планировщики ввода-вывода учитывают фактор «ресурсного голодания», поэтому в итоге (рано или поздно) будут обслужены все запросы (имеется ввиду, что планировщик следит за тем, чтобы запрос на ввод-вывод слишком долго не находился в очереди, т.е. не «голодал» бы — прим.перев.).

В настоящее время в ядре Linux существует четыре планировщика ввода-вывода:

• NOOP
• Anticipatory
• Deadline
• CFQ (Completely Fair Queuing — алгоритм полностью честной очереди)

Планировщик NOOP
Планировщик NOOP (no-operate) является самым простым. Он помещает все входящие запросы ввода-вывода в простой буфер типа FIFO (First-In, First-Out — первый вошел, первый вышел) и затем просто запускает их на исполнение. Заметим, что это происходит для всех процессов, существующих в системе, независимо от типа запросов ввода-вывода (чтение, запись, поиск необходимой дорожки т.д.). Также он выполняет нечто подобное слиянию запросов (см. выше).
Согласно этой статье, планировщик NOOP "... использует минимальное количество инструкций процессора на операцию ввода-вывода для выполнения простейшей функциональности: слияние и сортировка запросов". Данный планировщик предполагает, что сами устройства хранения данных будут оптимизировать быстродействие операций ввода-вывода (например, внешний RAID-контроллер или SAN).
Потенциально, планировщик NOOP будет хорошо работать с устройствами хранения данных, которые не имеют механических частей для чтения данных (т.е. головок диска). Причина кроется в том, что данный планировщик не делает никаких попыток оптимизировать движение головок, выполняя простейшее слияние запросов, что также помогает повышению пропускной способности диска. Поэтому такие устройства хранения как флэш-диски, SSD-диски, USB-накопители и т.п., которые имеют очень малое время поиска данных (seek time) могут получить преимущество, используя планировщик NOOP.

Anticipatory IO Scheduler (Предполагающий планировщик)
Anticipatory IO Scheduler, как следует из названия, пытается предположить к каким блокам диска будут выполнены следующие запросы. Он выполняет слияние запросов, простейший однонаправленный алгоритм лифта, объединение (request batching) запросов на чтение и запись. После того как планировщик обслужил запрос на чтение-запись, он предполагает, что следующий запрос будет для последующего блока, приостанавливаясь на небольшое количество времени. Если такой запрос поступает, то он обслуживается очень быстро, поскольку головки диска находятся в нужном месте. Такой подход привносит незначительное замедление в работу системы ввода-вывода по причине необходимости ожидания следующего запроса. Однако этот недостаток может быть компенсирован увеличением производительности запросов к соседним областям диска.
Некоторые исследования показали, что anticipatory scheduler работает действительно хорошо при некоторых загрузках системы. Например, наблюдалось, что веб-сервер Apache может достигать увеличить свою пропускную способность до 71% с помощью данного планировщика. С другой стороны, существуют наблюдения, что данный планировщик вызывал замедление работы баз данных на 15%.

Deadline IO Scheduler (планировщик предельных сроков)
Deadline IO Scheduler был написан Дженсом Аксбо (Jens Axboe), широко известным разработчиком ядра. Основополагающим принципом его работы является гарантированное время запуска запросов ввода-вывода на обслуживание. Он сочетает в себе такие возможности как слияние запросов, однонаправленный алгоритм лифта и устанавливает предельный срок на обслуживание всех запросов (отсюда и такое название). Он поддерживает две специальные «очереди сроков выполнения» (deadline queues) в дополнение к двум отдельным «отсортированным очередям» на чтение и запись (sorted queues). Задания в очереди сроков выполнения сортируются по времени исполнения запросов по принципу «меньшее время — более раннее обслуживание — ближе к началу очереди». Очереди на чтение и запись сортируются на основе запрашиваемого ими номера сектора (алгоритм лифта).
Данный планировщик действительно помогает пропускной способности в случаях чтения с секторов с большим номером блока (на внешних областях диска — прим.перев.). Операции чтения могут иногда заблокировать приложения, поскольку пока они выполняются, приложения ждут их завершения. С другой стороны, операции записи могут выполняться гораздо быстрее, поскольку они производятся в дисковый кэш (если только вы не отключили его использование). Более медленные операции чтения с внешних областей диска перемещаются к концу очереди, а более быстрые операции чтения с более близких областей поступят на обслуживание раньше. Такой алгоритм планировщика позволяет быстрее обслужить все запросы на чтение-запись, даже если существуют запросы на чтение с дальних областей диска.
Схема работы планировщика достаточно прямолинейна. Планировщик сначала решает какую очередь использовать первой. Более высокий приоритет установлен для операций чтения, поскольку, как уже упоминалось, приложения обычно блокируются при запросах на чтение. Затем он проверяет истекло ли время исполнения первого запроса. Если так — данный запрос сразу же обслуживается. В противном случае, планировщик обслуживает пакет запросов из отсортированной очереди. В обоих случаях, планировщик также обслуживает пакет запросов следующий за выбранным в отсортированной очереди.
Deadline scheduler очень полезен для некоторых приложений. В частности, в системах реального времени используется данный планировщик, поскольку в большинстве случаев, он сохраняет низкое время отклика (все запросы обслуживаются в короткий временной период). Также было отмечено, что он также хорошо подходит для систем баз данных, которые имеют диски без поддержки TCQ.

CFQ IO Scheduler (планировщик с полностью честной очередью)
CFQ (Completely Fair Queue — планировщик с полностью честной очередью) IO scheduler в настоящее время является планировщиком по умолчанию в ядре Linux. Он использует и слияние запросов и алгоритм лифта. При работе CFQ синхронно размещает запросы на ввод-вывод от процессов в ряд очередей на каждый процесс (per-process queues). Затем он выделяет отрезки времени (timeslices) для каждой очереди на доступ к диску. Длина отрезков времени и количество запросов в очереди, которые будут обслужены, зависит от приоритета ввода-вывода конкретного процесса. Асинхронные запросы от всех процессов объединяются в несколько очередей по одной на каждый приоритет.
Дженс Аксбо (Jens Axboe) является автором планировщика CFQ и включает то, что Дженс называет "алгоритмом лифта Линуса". Добавление данной возможности произошло при необходимости внесения функций для предотвращения «голодания процессов» в наиболее неблагоприятной ситуации, которая может произойти при чтении со внешних дорожек диска. Также приведенная ссылка указывает на хорошую дискуссию по разработке планировщика CFQ и сложностях его дизайна (также в нем обсуждается дизайн deadline scheduler — очень рекомендую это прочесть).
CFQ предоставляет пользователям (процессам) конкретного устройства хранения данных необходимое количество запросов ввода-вывода для определённого промежутка времени. Это сделано для многопользовательских систем, так как все пользователи в таких системах получат один и тот же уровень отклика. Более того, CFQ достигает некоторых из характеристик anticipatory scheduler по хорошей пропускной способности, поскольку позволяет обслуживаемой очереди простаивать какое-то время по завершению выполнения запроса на ввод-вывод в ожидании запроса, который может оказаться близким к только что выполненному запросу (и к тому же позволяет настройку своих параметров — прим. перев.).

Переключение планировщиков
Ядра Linux версии 2.6 фактически позволяют вам изменять планировщик ввода-вывода несколькими способами. Например, вы можете изменить планировщик по умолчанию для системы в целом используя опцию "elevator=" в строке параметров ядра. Это можно сделать вручную во время загрузки или может в конфигурационном файле Grub.
Для изменения планировщик ввода-вывода по умолчанию отредактируйте файл конфигурации Grub /boot/grub/menu.lst , добавив опцию «elevator=» в конец конца строки. Например, вы можете изменить его с CFQ на deadline добавив параметр “elevator=deadline” в строку, которая начинается словом «kernel».
Второй способ изменить планировщик позволяет менять его «на лету» для конкретных устройств. Например, вы можете определить, какой планировщик ввода-вывода используется, посмотрев содержимое файла ”/sys/block/[device]/queue/scheduler”, где [device] — имя соответствующего устройства. Например, на моем ноутбуке:

root@laytonjb-laptop:~#cat /sys/block/sdb/queue/scheduler
noop anticipatory deadline [cfq] NOOP

Обратите внимание, что текущий планировщик - CFQ. Вы можете изменить планировщик командой echo передав ей имя желаемого планировщика и переадресовав ее вывод в соответствующий файл устройства - “/sys/block/[device]/queue/scheduler”. Например, я могу изменить планировщик на моем ноутбуке следующим образом:

root@laytonjb-laptop:~# echo deadline > /sys/block/sdb/queue/scheduler
root@laytonjb-laptop:~# cat /sys/block/sdb/queue/scheduler
noop anticipatory [deadline] cfq

Обратите внимание, теперь планировщик изменился на deadline. Когда мы меняем планировщик, «старый» планировщик выполняет все поступившие запросы, а затем ядро переключается на новый (правда же Linux великолепен?).

Заключение
Эта статья всего лишь краткое обозрение планировщиков ввода-вывода в Linux. Современные системы могут иметь большое число пользователей, интенсивную нагрузку на подсистему ввода-вывода, требовать высокий уровень отзывчивости, требования реального времени, плюс большое количество дисков и/или файловых систем. Именно здесь на помощь приходит планировщик ввода-вывода.
Планировщик ввода-вывода не является новой идеей, но тем не менее он очень важен. Эти планировщики могут быть разработаны для работы с системой ввода-вывода так как пожелаете вы. В настоящее время в ядре Linux существует четыре планировщика ввода-вывода: NOOP, deadline, anticipatory и CFQ. Различные аспекты их работы были обсуждены в этой статье на достаточно высоком уровне.
В этой статье не рассматривалась настройка различных планировщиков под конкретную нагрузку. Для ознакомления с этой темой вы можете изучить документацию, которая поставляется с исходниками текущего ядра. Например, на моем ноутбуке, документацию можно найти в каталоге /usr/src/linux-source-2.6.27/Documentation/block. Кроме того, по настройке планировщиков в Интернет существует большое количество статей.
Одна простая вещь, которую вы можете сделать — это попробовать поменять планировщик ввода-вывода, связанный с определенным устройством (было рассмотрено выше). Это довольно легко сделать и может привести к некоторым интересным результатам (прозрачный намек ;) ).