 |
Алгоритм First Come First Served (FCFS)
|
|
|
|
Простейшим алгоритмом является алгоритм First Come First Served (FCFS) – первым пришел, первым обслужен.
Все запросы организуются в очередь FIFO и обслуживаются в порядке поступления. Алгоритм прост в реализации, но может приводить к достаточно длительному общему времени обслуживания запросов.
Рассмотрим пример. Пусть у нас на диске из 100 цилиндров (от 0 до 99) есть следующая очередь запросов: 23, 67, 55, 14, 31, 7, 84, 10 и головки в начальный момент находятся на 63-м цилиндре. Тогда положение головок будет меняться следующим образом:
63 
23 67 55 14 31 7 84 10
и всего головки переместятся на 329 цилиндров. Неэффективность алгоритма хорошо иллюстрируется двумя последними перемещениями с 7 цилиндра через весь диск на 84 цилиндр и затем опять через весь диск на цилиндр 10. Простая замена порядка двух последних перемещений (7 10 84) позволила бы существенно сократить общее время обслуживания запросов.
Поэтому перейдем к рассмотрению другого алгоритма.
Алгоритм Short Seek Time First (SSTF)
Как мы убедились, достаточно разумным является первоочередное обслуживание запросов, данные для которых лежат рядом с текущей позицией головок, а уж затем далеко отстоящих.
Алгоритм Short Seek Time First (SSTF) – короткое время поиска первым.
Для очередного обслуживания будем выбирать запрос, данные для которого лежат наиболее близко к текущему положению магнитных головок. Естественно, что при наличии равноудаленных запросов решение о выборе между ними может приниматься исходя из различных соображений, например по алгоритму FCFS.
Для предыдущего примера алгоритм даст такую последовательность положений головок:
63 67 55 31 23 14 10 7 84
и всего головки переместятся на 141 цилиндр.
Алгоритмы сканирования (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.
Вопросы для проверки
1. Расскажите о строении жесткого диска.
2. Какие характеристики диска полностью определяют запрос на чтение-запись?
3. Что представляют собой данные характеристики диска?
4. Из каких составляющих складывается время для выполнения запроса к диску?
5. Назовите алгоритмы обслуживания запросов к диску.
6. В чем состоит разница между первым и вторым алгоритмами?
Литература
1. Попов А.В. «Командная строка и сценарии Windows», Интернет адрес курса http://www.intuit.ru/department/os/compromtwin/.
2. Microsoft Windows Script Technologies – Справочная информация по сценариям Windows.
3. Борн Г. «Руководство разработчика на Windows Script Host 2.0», ПИТЕР, 2001.
4. Попов А. «Windows Script Host для Windows 2000/ХP», ПИТЕР, 2004.
5. Коньков К.А., Карпов В.Е.«Основы операционных систем», Интернет адрес курса http://www.intuit.ru/department/os/osintro/.
|
|
|
