Linux Kernel (Ядро линукса) (часть 2)

Алгоритмы планирования ввода/вывода

Когда в очередь запросов добавляется новый запрос, общий слой работы с блочными устройствами вызывает планировщик ввода/вывода, чтобы тот определил точное положение нового элемента в очереди. Планировщик старается поддерживать очередь упорядоченной по секторам. Если запросы, под
лежащие обработке, брать из списка поочередно, то время поиска на диске существенно сократится, поскольку головка будет двигаться в одном направлении, от внутренней дорожки к внешней (или наоборот), а не дергаться случайным образом от одной дорожки к другой. Такой подход напоминает алгоритм, используемый в лифтах при обработке вызовов, поступающих с разных этажей от людей, которые хотят спуститься или подняться. Лифт двигается в одном направлении. Когда он доходит до последнего заказанного этажа, он меняет направление движения. По аналогии, планировщики ввода/вывода иногда называются лифтами.

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

В настоящее время Linux 2.6 предлагает четыре типа планировщиков ввода/вывода, или лифтов. Они называются Anticipatory (Предвидящий), Deadline (Крайний срок), CFQ (Complete Fairness Queueing, Абсолютно честная очередь) и Noop (No Operation, Никаких действий). Лифт, используемый ядром по умолчанию для большинства блочных устройств, указывается на этапе загрузки в параметре ядра eievator=, где — это одна из таких последовательностей: as, deadline, cfq и noop. Если на этапе загрузки аргумент не задан, ядро использует планировщик Anticipatory. В любом случае драйвер устройства может заменить лифт, установленный по умолчанию, на другой. Кроме того, драйвер может определить собственный алгоритм планирования ввода/вывода, но это делается крайне редко.

Более того, системный администратор может во время работы системы заменить планировщик ввода/вывода конкретного блочного устройства. Например, чтобы заменить планировщик, используемый master-диском первого IDE-канала, администратор может записать имя лифта в файл /sys/block /hda/queue/scheduler специальной файловой системы sysfs

Алгоритм планирования ввода/вывода, используемый в очереди запросов, представлен объектом-лифтом, имеющим тип eievator t. Его адрес хранится в поле elevator дескриптора очереди запросов. Объект-лифт имеет несколько методов, покрывающих все возможные операции над лифтом: связывание лифта с очередью запросов и отсоединение от нее, добавление запросов в очередь, слияние запросов в очереди, удаление запросов из очереди, получе
ние из очереди следующего запроса для обработки и т. д. Лифт содержит также адрес таблицы со всей информацией, необходимой для управления очередью запросов. Кроме того, каждый дескриптор запроса имеет поле eievator private, которое указывает на дополнительную структуру данных, используемую планировщиком ввода/вывода при обработке запроса.

Далее мы кратко опишем четыре алгоритма планирования ввода/вывода, от простейшего до самого сложного. Хотим предупредить читателя, что разработка планировщика ввода/вывода во многом напоминает разработку планировщика центрального процессора: эвристика и значения констант подбираются в результате большого количества экспериментов и тестов.

Вообще говоря, во всех алгоритмах используется диспетчерная очередь, которая содержит все запросы, расставленные в том порядке, в каком они должны быть обработаны драйвером; следующий запрос, подлежащий обработке, всегда стоит первым в диспетчерной очереди. Фактически, эта очередь — не что иное, как очередь запросов с корнем в поле queue head дескриптора очереди запросов. Почти все алгоритмы пользуются дополнительными очередями для классификации и сортировки запросов. Все они позволяют драйверу добавлять структуры bio к существующим запросам и, если необходимо, объединять смежные” запросы.