СМОТРЕТЬ алгоритм - LOOK algorithm

СМОТРЮ это диск планирование алгоритм, используемый для определения порядка обработки новых запросов на чтение и запись на диск.

Описание

В СМОТРЮ алгоритм такой же, как и СКАНИРОВАТЬ алгоритм в том, что он также учитывает запросы в обоих направлениях развертки головки диска, однако этот алгоритм "смотрит" вперед, чтобы увидеть, есть ли какие-либо запросы, ожидающие обработки в направлении движения головки. Если в направлении движения головки нет ожидающих запросов, то перемещение головки диска будет обратным в противоположном направлении, и запросы в другом направлении могут быть обслужены. При планировании 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), но позволяет избежать проблемы голодания SSTF. Это связано с тем, что LOOK смещен в сторону недавно пройденной области и сильно отдает предпочтение трекам, сгруппированным на самых внешних и внутренних краях диска. LOOK также склоняется к новым вакансиям (в среднем).

Варианты

  • C-LOOK (Круговой ВЗГЛЯД)
Один из вариантов LOOK - C-LOOK. Это попытка устранить смещение в LOOK для кластеров дорожек по краям диска. C-LOOK в основном сканирует только в одном направлении. Либо вы сметаете изнутри наружу, либо снаружи внутрь. Когда вы доходите до конца, вы просто качаете головой до самого начала. Это фактически использует тот факт, что многие диски могут перемещать головку чтения / записи с высокой скоростью, если она перемещается по большому количеству дорожек (например, время поиска от последней дорожки до дорожки 0 меньше, чем можно было бы ожидать, и обычно значительно меньше времени, необходимого для поиска одного трека за раз). Огромный переход от одного запроса конца к другому не считается движением головы, поскольку цилиндры обрабатываются как круговой список.
  • N-LOOK и F-LOOK
N и F LOOK были разработаны, чтобы компенсировать предвзятое отношение LOOK к недавним вакансиям. Оба алгоритма разделяют очередь запросов на более мелкие подчиненные очереди и обрабатывают подчиненные очереди по порядку (сначала самые старые). N-LOOK называется так потому, что очередь запросов разделена на N вспомогательные очереди. F-LOOK - это упрощение, в котором всего 2 очереди, но они используются с двойной буферизацией. Пока F-LOOK обрабатывает одну очередь, все новые запросы переходят в другую. Чтобы объяснить эти алгоритмы, мы собираемся использовать пример диска с 200 дорожками, а головка чтения / записи начинается с дорожки 100. Очередь запросов по порядку содержит запросы на дорожки: 55, 58, 18, 90, 160, 38, мы предполагаем, что очередь запросов разделена на две, причем самая старая из них содержит запросы на треки: 55, 58, 18, 90. В этом случае N-LOOK и F-LOOK ведут себя одинаково. Также обратите внимание, что в этой конфигурации не имеет значения, в каком направлении двигалась голова, все запрошенные дорожки меньше 100, поэтому она будет двигаться только в направлении уменьшения дорожек.
Даже несмотря на то, что среднее количество пройденных треков такое же, как LOOK в худшем случае, N и F LOOK в каком-то смысле более справедливы, чем простой старый LOOK. Система дополнительных очередей ограничивает максимальную задержку, которую процесс может ожидать между запросом и его обслуживанием (в отличие от SSTF, который может останавливать процессы на произвольные промежутки времени).
  • S-LOOK
Алгоритм кратчайшего взгляда (S-LOOK) - это расширение алгоритма LOOK для обработки случаев, когда головка диска расположена между запросами на дальнем конце. Алгоритм предназначен для принятия решения о том, какое направление следует обслуживать первым, вместо того, чтобы продолжать поиск в том же направлении до поступления новых запросов. Поскольку время поиска прямо пропорционально расстоянию поиска, наша цель - минимизировать расстояние поиска и, следовательно, уменьшить время поиска.

Спектакль

У LOOK среднее время поиска немного лучше, чем у SCAN. C-LOOK имеет немного меньшую дисперсию времени поиска, чем LOOK, поскольку время поиска в худшем случае сокращается почти вдвое.

Смотрите также

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

использованная литература

  1. ^ «Лекция 17 - Планирование дисков».