Лифтовая сортировка

Лифтовая сортировка (elevator sorting) – это метод для обеспечения большей эффективности операций произвольного ввода-вывода. Когда диск получает произвольные запросы ввода-вывода, головки должны перемещаться произвольным образом по дорожкам диска, внутрь и наружу. Из-за этих операций произвольного ввода-вывода возникают задержки, мы уже рассказывали вам об этом. Многие из RAID-контроллеров поддерживают лифтовую сортировку, благодаря которой поиск произвольных дорожек становится более эффективным. Когда на контроллере, поддерживающем лифтовую сортировку, собрались в очереди несколько запросов ввода-вывода, то операции ввода-вывода могут быть отсортированы таким образом, чтобы избавиться от лишних перемещений головок. Движения головок, оптимизированные при помощи лифтовой сортировки, напоминают движения лифта, забирающего попутных пассажиров при перемещении между этажами в нужном направлении.

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

Рис. 5.7. Лифтовая сортировка

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