ПОСМОТРЕТЬ алгоритм
 | В этой статье есть несколько проблем. Пожалуйста, помогите улучшить его или обсудите эти проблемы на странице обсуждения . ( Узнайте, как и когда удалять эти шаблонные сообщения )
|
LOOK — это жесткого диска алгоритм планирования , используемый для определения порядка обработки новых запросов на чтение и запись на диск.
Описание
[ редактировать ]Алгоритм LOOK, аналогичный алгоритму SCAN , обрабатывает запросы в обоих направлениях движения головки диска, однако он дополнительно «просматривает» вперед, чтобы увидеть, есть ли какие-либо ожидающие запросы в направлении движения головки. Если в направлении движения головки нет запросов, то движение головки диска будет изменено на противоположное, и запросы в другом направлении могут быть обслужены. При планировании LOOK плечо доходит только до конечных запросов в каждом направлении, а затем меняет направление на противоположное, не дойдя до конца. Рассмотрим пример. Предположим, у нас есть диск с 200 цилиндрами (0–199). Предположим, у нас есть 8 ожидающих запросов: 98, 183, 37, 122, 14, 124, 65, 67, и что головка чтения/записи в настоящее время находится в цилиндре 53. Чтобы выполнить эти запросы, рука сначала будет двигаться в возрастающем порядке, а затем, дойдя до конца, будет двигаться в убывающем порядке. Итак, порядок его выполнения: 65, 67, 98, 122, 124, 183, 37, 14. [ 1 ]
LOOK позволяет избежать проблемы нехватки времени первого поиска (SSTF). Это связано с тем, что LOOK смещен в сторону недавно пройденной области и отдает предпочтение трекам, сгруппированным на самых внешних и самых внутренних краях диска. LOOK также отдает предпочтение недавно появившимся вакансиям (в среднем).
Варианты
[ редактировать ]C-LOOK
[ редактировать ]Одним из вариантов LOOK является круговой LOOK (C-LOOK). Это попытка устранить смещение в LOOK кластеров дорожек по краям диска. C-LOOK в основном сканирует только в одном направлении. Либо вы подметаете изнутри наружу, либо снаружи внутрь. Когда вы достигаете конца, вы просто поворачиваете голову обратно к началу. Это фактически использует тот факт, что многие приводы могут перемещать головку чтения/записи на высоких скоростях, если она перемещается по большому количеству дорожек (например, время поиска от последней дорожки до дорожки 0 меньше, чем можно было бы ожидать, и обычно значительно меньше, чем время, необходимое для поиска по одному треку за раз). Огромный скачок от одного конечного запроса к другому не рассматривается как движение головки, поскольку цилиндры рассматриваются как круговой список.
N-LOOK и F-LOOK
[ редактировать ]N и F LOOK были созданы, чтобы компенсировать предвзятость LOOK в отношении недавних вакансий. Оба алгоритма разделяют очередь запросов на более мелкие подочереди и обрабатывают подочереди по порядку (сначала самые старые). N-LOOK называется так потому, что очередь запросов разделена на N подочередей. F-LOOK — это упрощение, в котором имеется только две очереди, но они используются с двойной буферизацией. Пока F-LOOK обрабатывает одну очередь, все новые запросы попадают в другую. Для объяснения этих алгоритмов мы воспользуемся примером диска с 200 дорожками, а головка чтения/записи начинается с дорожки 100. Очередь запросов по порядку содержит запросы на дорожки: 55, 58, 18, 90, 160, 38, мы предполагаем, что очередь запросов разделена на две части, самая старая из которых содержит запросы треков: 55, 58, 18, 90. В этом случае N-LOOK и F-LOOK ведут себя одинаково. Также обратите внимание, что в этой конфигурации не имеет значения, в каком направлении двигалась головка, все запрошенные дорожки меньше 100, поэтому она будет двигаться только в направлении убывания дорожек. Несмотря на то, что среднее количество пройденных путей такое же, как и в худшем случае, N и F LOOK в некотором смысле более справедливы, чем старый добрый LOOK. Система подочередей ограничивает максимальную задержку, которую процесс может ожидать между запросом и его обслуживанием (в отличие от SSTF, который может останавливать процессы на произвольный период времени).
S-LOOK
[ редактировать ]Самый короткий алгоритм LOOK (S-LOOK) является расширением алгоритма LOOK для обработки случаев, когда головка диска находится между запросами на дальнем конце. Алгоритм предназначен для принятия решения о том, какое направление следует обслуживать в первую очередь, вместо того, чтобы продолжать поиск в том же направлении до поступления новых запросов. Поскольку время поиска прямо пропорционально расстоянию поиска, наша цель — минимизировать расстояние поиска и, следовательно, уменьшить время поиска.
Производительность
[ редактировать ]У LOOK среднее время поиска немного лучше, чем у SCAN. C-LOOK имеет немного меньшую дисперсию времени поиска, чем LOOK, поскольку в худшем случае время поиска сокращается почти вдвое.
См. также
[ редактировать ]- СКАН - Алгоритм лифта
- ФСКАН
- N-шаг-СКАН