Сначала кратчайший поиск (или сначала кратчайшее время поиска ) - это вторичный алгоритм планирования хранилища для определения движения плеча и головки диска при обслуживании запросов на чтение и запись.
Описание
Это прямое улучшение алгоритма « первым пришел - первым обслужен» (FCFS). Накопитель поддерживает входящий буфер запросов, и с каждым запросом связан номер цилиндра запроса. Меньшие номера цилиндров указывают на то, что цилиндр находится ближе к шпинделю, а более высокие числа указывают на то, что цилиндр находится дальше. Самый короткий алгоритм поиска сначала определяет, какой запрос ближе всего к текущей позиции головы, а затем обслуживает этот запрос следующим.
Анализ
Алгоритм кратчайшего поиска в первую очередь имеет прямое преимущество простоты и явно выгоден по сравнению с методом FIFO, так как общее движение руки уменьшается, что приводит к более низкому среднему времени отклика.
Однако, поскольку буфер всегда получает новые запросы, это может исказить время обслуживания запросов, которые могут находиться дальше всего от текущего местоположения головки диска, если все новые запросы находятся близко к текущему местоположению; на самом деле, это может привести к голодной смерти , и отдаленные просьбы никогда не смогут добиться прогресса. [1]
Алгоритм лифта является одна альтернативой для уменьшения движения руки и времени отклика, а также обеспечить последовательное обслуживание запросов.
Рекомендации
- ^ Эндрю С. Таненбаум; Герберт Бос (2015). Современные операционные системы . Пирсон. ISBN 978-0-13-359162-0.