Сначала ищем кратчайший путь

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

Описание

Это альтернатива алгоритму «первым пришел — первым обслужен » (FCFS). Привод поддерживает входящий буфер запросов, и с каждым запросом связан номер цилиндра запроса. Меньшие номера цилиндров указывают на то, что цилиндр находится ближе к шпинделю, а более высокие номера указывают на то, что цилиндр находится дальше.Алгоритм кратчайшего поиска сначала определяет, какой запрос ближе всего к текущей позиции головы, а затем обслуживает следующий запрос.

Анализ

Преимущество алгоритма с кратчайшим поиском в первую очередь состоит в том, что общее движение руки уменьшается, что приводит к меньшему среднему времени отклика.

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

Алгоритм лифта является одной из альтернатив, позволяющей сократить количество движений рук и время отклика, а также обеспечить последовательное обслуживание запросов.