Планирование ввода-вывода¶

Планирование ввода-вывода (англ. I/O scheduling) — это механизм операционной системы, управляющий порядком выполнения запросов на операции ввода-вывода (чтение и запись) к блочным устройствам (жёстким дискам, твердотельным накопителям, оптическим приводам) с целью оптимизации производительности, минимизации задержек и обеспечения справедливого доступа к устройству для различных процессов.

¶История и предпосылки

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

В 1970-х годах появились первые алгоритмы, такие как SCAN (лифтовый алгоритм), которые группировали запросы по направлению движения головки. В 1980-х годах, с распространением Unix-систем, алгоритмы планирования стали частью ядра операционной системы. В Linux, начиная с версии 2.6 (2003 год), были внедрены несколько планировщиков, включая Deadline и CFQ (Completely Fair Queuing). В современных системах (Linux 5.x и новее) по умолчанию используется планировщик BFQ (Budget Fair Queuing) или Kyber, в зависимости от типа накопителя.

¶Цели планирования ввода-вывода

Основные задачи планировщика ввода-вывода включают:

• Минимизация времени поиска (seek time) — для механических дисков (HDD), где головка перемещается к нужному сектору.
• Минимизация задержек (latency) — обеспечение быстрого ответа для интерактивных приложений.
• Максимизация пропускной способности (throughput) — увеличение количества обработанных запросов в единицу времени.
• Справедливость (fairness) — предотвращение монополизации устройства одним процессом.
• Приоритезация — обслуживание критичных запросов (например, от системных процессов) раньше фоновых.

¶Классификация алгоритмов

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

¶По принципу работы

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

¶По типу устройства

• Для HDD — ориентированы на сокращение времени поиска и вращения (например, SCAN, C-SCAN, CFQ).
• Для SSD — минимизируют накладные расходы на управление, так как время доступа к данным практически не зависит от порядка запросов. Используются упрощённые алгоритмы (NOOP, Kyber, BFQ).
• Для NVMe — высокоскоростные накопители, где планировщик может быть отключён (none) для снижения задержек.

¶Основные алгоритмы планирования

¶SCAN (лифтовый алгоритм)

Головка движется в одном направлении, обслуживая все запросы на пути, затем меняет направление. Вариант C-SCAN (Circular SCAN) обслуживает только запросы в одном направлении, после чего возвращается в начало. Обеспечивает равномерное время ожидания для всех запросов.

¶Deadline

Каждому запросу назначается временной лимит (обычно 500 мс для чтения, 5 с для записи). Если запрос не был обслужен в срок, он получает приоритет. Это предотвращает «голодание» запросов и улучшает отзывчивость. Используется в Linux по умолчанию для HDD.

¶CFQ (Completely Fair Queuing)

Распределяет время доступа к устройству между процессами, выделяя каждому квант времени. Обеспечивает справедливость, но может снижать пропускную способность на высоких нагрузках. Был заменён на BFQ в Linux 5.0.

¶BFQ (Budget Fair Queuing)

Эволюция CFQ, где каждому процессу выделяется «бюджет» на операции ввода-вывода. Улучшает отзывчивость для интерактивных приложений и снижает задержки. Используется в Linux по умолчанию для HDD и SSD.

¶NOOP (No Operation)

Простейший планировщик, который выполняет только слияние запросов, но не сортирует их. Рекомендуется для SSD и NVMe, где порядок запросов не влияет на производительность.

¶Kyber

Адаптивный планировщик, который динамически регулирует глубину очереди запросов на основе текущей нагрузки. Минимизирует задержки для чтения, не снижая пропускную способность. Используется в Linux для SSD.

¶Реализация в операционных системах

¶Linux

В ядре Linux планировщики ввода-вывода реализованы как модули, которые можно выбирать для каждого устройства. Основные планировщики:

• mq-deadline — многопоточная версия Deadline для современных многоядерных систем.
• bfq — для HDD и SSD с акцентом на справедливость.
• kyber — для высокоскоростных SSD.
• none — отключение планирования (для NVMe и виртуальных дисков).

Выбор планировщика осуществляется через sysfs (например, /sys/block/sda/queue/scheduler). В дистрибутивах, таких как Ubuntu и Fedora, по умолчанию используется bfq для HDD и none для NVMe.

¶Windows

В Windows планировщик ввода-вывода встроен в драйвер диска (storport.sys). Использует алгоритм, аналогичный Deadline, с приоритетами для чтения и записи. Начиная с Windows 8, планировщик адаптирован для SSD, отключая дефрагментацию и оптимизируя запросы.

¶macOS

В macOS (XNU) используется планировщик, основанный на алгоритме SCAN, с дополнительной приоритезацией для системных процессов. Для SSD применяется упрощённый режим.

¶Влияние на производительность

Выбор планировщика существенно влияет на производительность системы:

• Для HDD: алгоритмы SCAN и CFQ могут увеличить пропускную способность на 20–30% по сравнению с FIFO при смешанной нагрузке.
• Для SSD: использование сложных планировщиков (CFQ, BFQ) может увеличить задержки на 5–10% из-за накладных расходов. Рекомендуется NOOP или none.
• Для NVMe: отключение планирования (none) снижает задержки до минимума, так как контроллер накопителя сам управляет очередью команд (NVMe поддерживает до 64 тыс. очередей).

¶Критика и ограничения

• Сложность настройки: пользователи редко меняют планировщик, что приводит к неоптимальной работе на некоторых устройствах.
• Неэффективность на SSD: традиционные алгоритмы, ориентированные на HDD, могут ухудшать производительность на твердотельных накопителях.
• Голодание процессов: при неправильной настройке приоритетов некоторые процессы могут долго ждать доступа к устройству.
• Отсутствие единого стандарта: разные операционные системы используют разные алгоритмы, что усложняет переносимость приложений.

¶Источники

• Andrew S. Tanenbaum, Herbert Bos. «Modern Operating Systems» (4th edition), 2014.
• Daniel P. Bovet, Marco Cesati. «Understanding the Linux Kernel» (3rd edition), 2005.
• Документация ядра Linux: «I/O schedulers» (kernel.org/doc/Documentation/block/).
• Jonathan Corbet. «I/O Schedulers» (LWN.net, 2003–2018).
• Microsoft Docs. «Storage Driver Architecture» (Windows Driver Kit).