Алгоритм лифта

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

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

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

Описание

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

Вариации

Один из вариантов этого метода гарантирует, что все запросы обслуживаются только в одном направлении, то есть, как только головка достигает внешнего края диска, она возвращается к началу и обслуживает новые запросы только в этом одном направлении (или наоборот). ). Это известно как «Алгоритм кругового лифта» или C-SCAN. Хотя время обратного поиска тратится впустую, это приводит к более равной производительности для всех положений головки, поскольку ожидаемое расстояние от головки всегда составляет половину максимального расстояния, в отличие от стандартного алгоритма лифта, где цилиндры в середине будут обслуживаться как почти в два раза чаще, чем самые внутренние или самые внешние цилиндры.

Другие варианты включают:

• ФСКАН
• СМОТРЕТЬ
  • C-LOOK
• N-шаг-СКАН

	СКАНИРОВАНИЕ	СМОТРЕТЬ	С-СКАН	скрывать C-LOOK
Повторяющееся движение	Переходит к последней дорожке (независимо от того, запрошено оно или нет), затем меняет направление и переходит к первой дорожке.	Доходит только до последнего запроса в этом направлении, а затем меняет направление.	Переходит к последней дорожке, затем переходит к первой дорожке и продолжает движение в том же направлении.	Доходит только до последнего запроса, затем переходит к первому запросу и продолжает в том же направлении.

Пример

Ниже приведен пример расчета среднего времени поиска на диске для алгоритмов SCAN и C-SCAN.

• Пример списка ожидающих запросов к диску (по номеру дорожки): 100, 50, 10, 20, 75.
• Начальный номер трека для примеров будет 35.
• Список нужно будет отсортировать по возрастанию: 10, 20, 50, 75, 100.

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

• Ищите 1: 50 − 35 = 15
• Ищите 2: 75 − 50 = 25
• Ищите 3: 100 − 75 = 25

На данный момент оба достигли самого высокого (конечного) запроса дорожки. SCAN просто изменит направление и обслужит следующий ближайший запрос к диску (в данном примере 20), а C-SCAN всегда вернется к дорожке 0 и начнет переходить к запросам более высокой дорожки.

• Поиск 4 (СКАНИРОВАНИЕ): 20–100 = 80
• Поиск 5 (СКАНИРОВАНИЕ): 10 − 20 = 10
• Всего (СКАН): 155
• Среднее (СКАНИРОВАНИЕ): 155 ÷ 5 = 31
• Поиск 4 (C-SCAN): 0–100 = 0 движение головки, поскольку цилиндры рассматриваются как циклический список (C-SCAN всегда возвращается к первой дорожке)
• Поиск 5 (C-SCAN): 10 − 0 = 10
• Поиск 6 (C-SCAN): 20 − 10 = 10
• Всего (C-SCAN): 85
• Среднее (C-SCAN): 85 ÷ 5 = 17

Несмотря на то, что с использованием алгоритма C-SCAN было выполнено шесть поисков, фактически было выполнено только пять операций ввода-вывода.

Анализ

Для обеих версий алгоритма лифта движение руки вдвое превышает общее количество цилиндров и приводит к меньшему отклонению во времени отклика. Алгоритм также относительно прост.

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

См. также

• ФИФО (вычисления и электроника)