Книга: Разработка ядра Linux

Задачи планировщика ввода-вывода

Задачи планировщика ввода-вывода

Планировщик ввода-вывода работает управляя очередью запросов блочного устройства. Он определяет, в каком порядке должны следовать запросы в очереди и в какое время каждый запрос должен передаваться на блочное устройство. Управление производится с целью уменьшения количества операций поиска по жесткому диску, что значительно повышает общее быстродействие. Определение "общее" здесь существенно. Планировщик ввода-вывода ведет себя "нечестно" по отношению к некоторым запросам и за счет этого повышает производительность системы в целом.

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

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

Оглавление книги