Ключевые слова: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 планировщик является самым базовым из доступных планировщиков. Он не выполняет каких
сортировок, только основные слияния. Он используется для специализированных устройств,
которые не требуют сортировки их запросов.
Журнал "Linux Format" (Линукс Формат)- Единственный в России и странах СНГ журнал на русском языке,
посвящённый Linux и свободному ПО. Журнал для IT-директоров, IT-менеджеров, программистов, системных
администраторов, учителей школ и преподавателей ВУЗов и всех пользователей ПК. В каждом выпуске: Новости
индустрии OpenSource, обзоры новинок свободного ПО, обучающие и методические статьи.
Каждый, кто оформит подписку, получает бонус- объёмные наклейки на системный блок и подарки: с одним из
первых выпусков журнала в 2012 году- диск с архивом номеров за 2005-2011 г.г. и ежемесячно электронную
версию журнала в pdf-формате.
Подробнее о проведении акции вы можете прочитать на
странице сайта.
