Введение
Алгоритм планирования диска Алгоритм планирования диска, или SCAN, — это алгоритм, определяющий перемещение головки и руки диска при обработке запросов на чтение и запись. Этот алгоритм получил свое название по аналогии с работой лифта в здании: лифт продолжает движение в текущем направлении (вверх или вниз), пока не станет пустым, останавливаясь только для высадки или посадки пассажиров, следующих в том же направлении. С точки зрения реализации, устройство поддерживает буфер ожидающих запросов на чтение/запись, а также соответствующий номер цилиндра для каждого запроса. Меньшие номера цилиндров обычно указывают на близость цилиндра к шпинделю, а большие — на удаленность.
The elevator algorithm, or SCAN, is a disk scheduling algorithm to determine the motion of the disk's arm and head in servicing read and write requests. This algorithm is named after the behavior of a building elevator, where the elevator continues to travel in its current direction (up or down) until empty, stopping only to let individuals off or to pick up new individuals heading in the same direction. From an implementation perspective, the drive maintains a buffer of pending read/write requests, along with the associated cylinder number of the request, in which lower cylinder numbers generally indicate that the cylinder is closer to the spindle, and higher numbers indicate the cylinder is farther away.
Описание
Когда поступает новый запрос, пока диск простаивает, первоначальное перемещение головки будет в направлении цилиндра, где хранятся данные – внутрь или наружу. По мере поступления новых запросов, они обслуживаются только в текущем направлении движения головки, пока она не достигнет края диска. Когда это происходит, направление движения головки меняется на противоположное, и обслуживаются запросы, которые ожидали в обратном направлении, и так далее.
Анализ
Для обеих версий алгоритма лифта перемещение головки чтения/записи занимает менее чем в два раза больше общего числа цилиндров и обеспечивает меньшее разброс времени отклика. Алгоритм также относительно прост в реализации. Алгоритм лифта не всегда превосходит алгоритм поиска в порядке кратчайшего перемещения, который лишь немного ближе к оптимальному, но может приводить к большому разбросу времени отклика и даже к "голоданию" запросов, когда новые запросы постоянно обслуживаются в приоритете перед существующими. Методы предотвращения "голодания" могут быть применены к алгоритму поиска в порядке кратчайшего перемещения, чтобы гарантировать максимальное время отклика.