Телекоммуникационный портал GateWay

Ядро предоставляет общую процедуру disksort(), которая может использоваться всеми драйверами дисковых устройств для сортировки запросов ввода/вывода в очереди запросов устройства, используя лифтовый алгоритм сортировки. Этот алгоритм сортирует запросы в циклическом восходящем блочном порядке таким образом, что запросы можно обслужить с минимальным однонаправленным сканированием диска. Это упорядочение было первоначально спроектировано для поддержки обычных упреждающих запросов файловой системы, а также для противодействия случайному размещению данных файловой системы на диске. С использованием усовершенствованных алгоритмов размещения в современных файловых системах эффект процедуры disksort() менее заметен; disksort() дает наибольший эффект, когда имеются несколько одновременно действующих пользователей диска.

Алгоритм disksort() приведен на рисунке. Очередь запросов диска составлена из двух списков запросов, упорядоченных по номерам блоков. Первый является активным списком; второй является списком следующего прохода. Запрос в начале активного списка показывает текущее положение диска. Если список следующего прохода не пуст, он составлен из запросов, которые находятся до текущей позиции. Каждый новый запрос сортируется либо в активном списке, либо в списке следующего прохода в соответствии с местом запроса. Когда головки достигают конца активного списка, активным становится список следующего прохода, создается пустой список следующего прохода, а диск начинает обслуживать новый активный список.

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

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