The design of the UNIX Operating System 107 страница
63 
67 55 31 23 14 10 7 84
и всего головки переместятся на 141 цилиндр. Заметим, что наш алгоритм похож на алгоритм SJF плани - рования процессов, если за аналог оценки времени очередного CPU burst процесса выбирать расстояние между текущим положением головки и положением, необходимым для удовлетворения запроса. И точно так же, как алгоритм SJF, он может приводить к длительному откладыванию выполнения какого-либо запроса. Необходимо вспомнить, что запросы в очереди могут появляться в любой момент времени. Если у нас все запросы, кроме одного, постоянно группируются в области с большими номерами цилиндров, то этот один запрос может находиться в очереди неопределенно долго.
|
|
|
Точный алгоритм SJF являлся оптимальным для заданного набора процессов с заданными временами CPU burst. Очевидно, что алгоритм SSTF не является оптимальным. Если мы перенесем обслуживание запроса 67-го цилиндра в промежуток между запросами 7-го и 84-го цилиндров, мы уменьшим общее время обслуживания. Это наблюдение приводит нас к идее целого семейства других алгоритмов – алго-ритмов сканирования.
|
|
|
Алгоритмы сканирования (SCAN, C-SCAN, LOOK, C-LOOK)
В простейшем из алгоритмов сканирования – SCAN – головки постоянно перемещаются от одного края диска до другого, по ходу дела обслуживая все встречающиеся запросы. По достижении другого края на-правление движения меняется, и все повторяется снова. Пусть в предыдущем примере в начальный мо-мент времени головки двигаются в направлении уменьшения номеров цилиндров. Тогда мы и получим порядок обслуживания запросов, подсмотренный в конце предыдущего раздела. Последовательность пе-ремещения головок выглядит следующим образом:
|
|
|
|
|
|
63 55 31 23 14 10 7 0 67 84
и всего головки переместятся на 147 цилиндров.
Если мы знаем, что обслужили последний попутный запрос в направлении движения головок, то мы мо-жем не доходить до края диска, а сразу изменить направление движения на обратное:
63 
55 31 23 14 10 7 67 84
и всего головки переместятся на 133 цилиндра. Полученная модификация алгоритма SCAN получила на-звание LOOK.
Допустим, что к моменту изменения направления движения головки в алгоритме SCAN, т. е. когда го-ловка достигла одного из краев диска, у этого края накопилось большое количество новых запросов, на обслуживание которых будет потрачено достаточно много времени (не забываем, что надо не только пе-ремещать головку, но еще и передавать прочитанные данные!). Тогда запросы, относящиеся к другому краю диска и поступившие раньше, будут ждать обслуживания несправедливо долго. Для сокращения времени ожидания запросов применяется другая модификация алгоритма SCAN – циклическое сканиро-вание. Когда головка достигает одного из краев диска, она без чтения попутных запросов (иногда суще-ственно быстрее, чем при выполнении обычного поиска цилиндра) перемещается на другой край, откуда вновь начинает движение в прежнем направлении. Для этого алгоритма, получившего название C-SCAN, последовательность перемещений будет выглядеть так:
| Основы операционных систем | 144 |
63 55 31 23 14 10 7 0 99 84 67
Дата добавления: 2021-01-21; просмотров: 96; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!