Ключевые слова:io, scheduler, priority, linux, kernel, (найти похожие документы)
From: Yuri Trofimov <sysadmin.online@gmail.com.>
Date: Mon, 09 Feb 2009 17:02:14 +0000 (UTC)
Subject: Планировщики ввода/вывода в Linux
Оригинал: http://sysadminonline.ru/linux-io-schedulers/
Оригинал на английском: http://www.devshed.com/c/a/BrainDump/Linux-IO-Schedulers/
Планировщики ввода/вывода и производительность
Разрыв между показателями производительности дисков и остальных частей системы достаточно
большой и все время растет. Самое узкое место в производительности диска представляет собой
процесс перемещения головок чтения/записи из одной части диска в другую, эта операция
называется "установка головок" (seek). В мире, где многие операции измеряются несколькими
циклами процессора (каждый из которых может занять почти треть наносекунды), одна операция
установки головок диска может занять в среднем более восьми миллисекунд - это немного,
конечно, но это в 25 миллионов раз больше, чем один такт процессора!
Учитывая различия в производительности между диском и остальной частью системы, было бы
слишком грубо и неэффективно отправлять запросы ввода/вывода на диск в том порядке, в
котором они поступают. Таким образом, ядра современной операционной системы Linux имеют в
своем составе планировщики ввода/вывода, которые работают в целях минимизации количества и
величины перемещения головок дисков путем управления порядком обработки запросов
ввода/вывода и минимизации времени обслуживания. Планировщики ввода/вывода прилагают все
усилия, чтобы снизить накладные расходы производительности, связанные с доступом к диску.
Адресация диска
Для того чтобы понять роль планировщиков ввода/вывода, необходима некоторая справочная
информация. Жесткие диски адресуют свои данные, используя знакомую геометрию на основе
адресации цилиндров (cylinders), головок (heads) и секторов (sectors),- или CHS адресации.
Жесткий магнитный накопитель состоит из нескольких пластин, каждая из которых состоит из
одного диска, шпинделя и головки чтения/записи. Каждая пластина делится на круговые
кольцевые дорожки. Каждая дорожка затем делится на целое число секторов. Чтобы найти
конкретный блок данных на диске, логика привода требует трех частей информации: значения
цилиндра, головки и сектора.
К счастью, современные жесткие диски не используют вычислительные мощности компьютеров,
чтобы общаться с их дисками в терминах цилиндров, головок и секторов. Напротив, современные
жесткие диски эффективно отображают уникальный номер блока (также называемого физическим
блоком или блоком устройства) на каждую тройку - цилиндр/головку/сектор, а блок
отображается на конкретный сектор.
Современные операционные системы могут адресовать жесткие диски используя номера блоков -
процесс, известный как логическая адресация блоков (LBA) и далее жесткий диск внутри себя
транслирует номер блока в правильный CHS адрес.
Примечание. Хотя нет гарантий, что отображение номер-блока в CHS-координаты будет линейным.
Физически блок N обычно находится рядом с блоком N+1. Это последовательность отображения
имеет важное значение как мы скоро увидим.
Файловые системы, между тем, существуют только в области программного обеспечения.
Они оперируют своими собственными единицами, известными как логические блоки (иногда
называемыми блоками файловой системы, или просто блоками). Иными словами, файловая система
отображает логические блоки в один или несколько физических блоков на диске.
Жизнь планировщиков ввода/вывода
Планировщики ввода/вывода выполняют две основные операции: слияние и сортировка. Слияние
представляет собой процесс принятия двух или нескольких смежных запросов ввода/вывода и
объединения их в один запрос.
Рассмотрим два запроса, один для чтения с диска блока номер 5 и другого запроса на чтение
блоков с 6 по 7. Эти запросы могут быть объединены в один запрос на чтение блоков с 5 по 7.
Общий объем ввода/вывода может быть тот же самый, но количество операций ввода/вывода
сокращается вдвое.
Сортировка, более важная из этих двух операций,- это процесс упорядочивания запросов
ввода/вывода в восходящем порядке номеров блоков. Например, если есть операции ввода/вывода
с блоками номер 52, 109, и 7, то планировщик ввода/вывода будет сортировать эти запросы в
порядке 7, 52 и 109. Если запрос был выдан на блок 81, он будет вставлен между запросами на
блоки 52 и 109. Планировщик ввода/вывода направит запросы к диску в том порядке, в котором
они стоят в очереди: 7, затем 52, затем 81, и, наконец, 109.
Таким образом, перемещения головок диска сводятся к минимуму. Вместо потенциальных движений
наудачу туда-сюда-обратно, установка головок диска происходит в плавном, линейном режиме.
При этом возрастает производительность.
Helping Out Reads
Каждый запрос на чтение должен возвращать актуальные данные. Таким образом, если
запрашиваемые данные не в кэше страниц, процесс чтения должен быть блокирован до тех пор,
пока эти данные не будут считаны с диска - а это потенциально длительная операция.
Типичная программа может инициировать ряд запросов на чтение с диска в короткий период
времени. Т.к. каждый запрос в индивидуальном порядке синхронизирован, следующий запрос
зависит от ранее завершенного. Такие запросы становятся серийными: последующий запрос не
может быть завершен до тех пор, пока текущий запрос выполняется.
Это резко контрастирует с запросами на запись, которые (по умолчанию, в
несинхронизированном состоянии) заблаговременно не инициируют ввод/вывод. Таким образом, с
точки зрения user-space приложения, поток пишущих запросов не расходует производительность
диска. Это потоковое поведение лишь усугубляет проблему для чтения: пишущий поток требует
ресурсов ядра и диска. Этот феномен известен как проблема writes-starving-reads.
Если I/O scheduler всегда сортирует вставку новых запросов, то возможно что запросы на
далекие блоки будут "голодать" неопределенно долго. Рассмотрим наш предыдущий пример. Если
новые запросы беспрерывно поступают к блокам, скажем, 50-х номеров, запрос на блок 109
никогда не будет обслужен (имеется в виду, до тех пор, пока предыдущие запросы не будут
обслужены. Прим.пер.). Поскольку время ожидания по чтению имеет решающее значение, то от
такого поведения будет в значительной степени страдать производительность системы. Таким
образом, планировщики ввода/вывода должны использовать механизм для предотвращения голода.
Простой подход, например, принят в I/O scheduler в ядре Linux 2.4,- Linus Elevator -
заключается в том, чтобы просто остановить вставки-сортировки, если в очереди есть
достаточно старый запрос. Проблема заключается в том, что этот эвристический алгоритм
является слишком упрощенным. Признавая это, в ядре Linux Kernel 2.6 Linus Elevator был
убран и добавлено несколько новых планировщиков ввода/вывода.
Deadline I/O Scheduler
Deadline I/O Scheduler хранит отсортированную (как описано выше, прим.пер.) очередь, и
вводит две дополнительные очереди: FIFO очередь на чтение и FIFO очередь на запись. Записи
в каждой из этих очередей отсортированы по времени поступления (фактически, первый вошел -
первый вышел). Каждому запросу в очереди FIFO назначено время окончания. Для очереди
запросов чтения - это 500 миллисекунд. Для очереди запросов записи - это пять секунд. При
поступлении нового I/O запроса, он вставляется-сортируется в стандартную очередь и
помещается в конец соответствующей (на чтение или запись) FIFO очереди.
Как правило, к жесткому диску посылаются запросы ввода/вывода с головы стандартной
отсортированной очереди. Это максимизирует общую пропускную способность при минимизации
операций поиска и установки головок на диске, так как нормальная очередь сортируется по
номеру блока (как и с Linus Elevator).
Когда у записи вначале списка одной из дополнительных FIFO очередей истечет назначенное
время, I/O scheduler останавливает обработку I/O запросов из стандартной очереди, и
начинает обслуживание запросов из этой FIFO очереди. I/O scheduler проверяет и обрабатывает
запросы только с головы очереди, где находятся старейшие запросы.
Таким образом, Deadline I/O Scheduler поддерживает эффективную общую пропускную способность
без голодания какого-либо одного запроса недопустимо длительное время. Проблема
writes-starving-reads сводится к минимуму.
Anticipatory (упреждающий) I/O Scheduler
Проблема предыдущих планировщиков ввода/вывода вновь вытекает из зависимости: каждый новый
запрос на чтение выдается только тогда, когда предыдущий будет возвращен, но к тому
времени, когда приложение получает прочитанные данные и посылает следующий запрос на
чтение, I/O планировщик уже начал обслуживание других запросов. В этом случае планировщик
ввода/вывода в течении некоторого времени мог бы подождать поступление следующего запроса
на чтение. Именно так и работает Anticipatory I/O Scheduler. Он основан на Deadline I/O
Scheduler с добавлением механизма ожидания, до шести миллисекунд, следующего чтения. Если
6-ть миллисекунд истекли, но запроса на чтение не поступило, планировщик возвращается к
работе, которую выполнял до этого (например, обслуживание стандартной отсортированной
очереди).
Complete Fair Queuing (CFQ) I/O Scheduler
CFQ планировщик использует другой подход для достижения тех же целей. В CFQ каждому
процессу присваивается собственная очередь, и каждой очереди присваивается квант времени
(timeslice). Планировщик ввода/вывода по кругу обходит каждую очередь и обслуживает запросы
из очереди до тех пор, пока не будет исчерпан лимит времени (timeslice) или не останется
запросов в этой очереди. В последнем случае CFQ планировщик будет ждать, по умолчанию
10-мс, нового запроса из очереди. Если ожидание было напрасным, то планировщик переходит к
следующей очереди.
В рамках каждой очереди процесса, синхронизированные запросы (как, например, читающие)
имеют приоритет над несинхронизированными запросами. Таким образом, CFQ способствует чтению
и предотвращает проблему writes-starving-reads.
CFQ планировщик хорошо подходит для большинства задач, что делает его прекрасным первым
выбором.
Noop I/O Scheduler
NOOP планировщик является самым базовым из доступных планировщиков. Он не выполняет каких
сортировок, только основные слияния. Он используется для специализированных устройств,
которые не требуют сортировки их запросов.
