Роберт Лав - Разработка ядра Linux

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

Теперь предположим, что наш запрос на чтение помещается в очередь запросов, но там нет других запросов на чтение соседних секторов. Поэтому нет возможности выполнить объединение этого запроса с другими запросами, находящимися в очереди. Можно просто поместить запрос в конец очереди. Но что если в очереди есть запросы к близкорасположенным секторам диска? Не лучше ли будет поместить новый запрос в очередь где-то рядом с запросами к физически близко расположенным секторам диска. На самом деле планировщики ввода-вывода именно так и делают, Вся очередь запросов поддерживается в отсортированном состоянии по секторам, чтобы последовательность запросов в очереди (насколько это возможно) соответствовала линейному движению по секторам жесткого диска. Цель состоит в том, чтобы не только уменьшить количество перемещений в каждом индивидуальном случае, но и минимизировать общее количество операций поиска таким образом, чтобы головка двигалась по прямой линии. Это аналогично алгоритму, который используется в лифте (elevator) — лифт не прыгает между этажами. Вместо этого он плавно пытается двигаться в одном направлении. Когда лифт доходит до последнего этажа в одном направлении, он начинает двигаться в другую сторону. Из-за такой аналогии планировщик ввода-вывода (а иногда только алгоритм сортировки) называют лифтовым планировщиком ( алгоритмом лифта , elevator ).

Рассмотрим некоторые планировщики ввода-вывода, применяемые в реальной жизни. Первый планировщик ввода-вывода, который мы рассмотрим, называется Linus Elevator ( лифтовой алгоритм Линуса ). Это не опечатка, действительно существует лифтовой планировщик, разработанный Линусом Торвальдсом и названный в его честь! Это основной планировщик ввода-вывода в ядре 2.4. В ядре 2.6 его заменили другими планировщиками, которые мы ниже рассмотрим. Однако поскольку этот алгоритм значительно проще новых и в то же время позволяет выполнять почти те же функции, то он заслуживает внимания.

Лифтовой алгоритм Линуса позволяет выполнять как объединение, так и сортировку запросов. Когда запрос добавляется в очередь, вначале он сравнивается со всеми ожидающими запросами, чтобы обнаружить все возможные кандидаты на объединение. Алгоритм Линуса выполняет два типа объединения: добавление в начало запроса ( front merging ) и добавление в конец запроса ( back merging ). Тип объединения соответствует тому, с какой стороны найдено соседство. Если новый запрос следует перед существующим, то выполняется вставка в начало запроса. Если новый запрос следует сразу за существующим — добавление выполняется в конец очереди. В связи с тем, что секторы, в которых хранится файл, расположены по мере увеличения номера сектора и операции ввода-вывода чаще всего выполняются от начала файла до конца, а не наоборот, то при обычной работе вставка в начало запроса встречается значительно реже, чем вставка в конец. Тем не менее алгоритм Линуса проверяет и выполняет оба типа объединения.

Если попытка объединения была неудачной, то определяется возможное место вставки запроса в очередь (положение в очереди, в котором новый запрос наилучшим образом вписывается по номеру сектора между окружающими запросами). Если такое положение находится, то новый запрос помещается туда. Если подходящего места не найдено, то запрос помещается в конец очереди. В дополнение к этому, если в очереди найден запрос, который является достаточно старым, то новый запрос также добавляется в конец очереди. Это предотвращает ситуацию, в которой наличие большого количества запросов к близко расположенным секторам приводит к недостатку обслуживания других запросов. К сожалению, такая проверка "на старость" не очень эффективна. В рассмотренном алгоритме не предпринимается никаких попыток обслуживания запросов в заданных временных рамках, а просто прекращается процесс сортировки-вставки при наличии определенной задержки. Это в свою очередь приводит к задержке в обслуживании, что было веской причиной для доработки планировщика ввода-вывода ядра 2.4.