Основы операционных систем

         

Алгоритм First Come First Served (FCFS)


Простейшим алгоритмом, к которому мы уже должны были привыкнуть, является алгоритм First Come First Served (FCFS) – первым пришел, первым обслужен. Все запросы организуются в очередь FIFO и обслуживаются в порядке поступления. Алгоритм прост в реализации, но может приводить к достаточно длительному общему времени обслуживания запросов. Рассмотрим пример. Пусть у нас на диске из 100 цилиндров (от 0 до 99) есть следующая очередь запросов: 23, 67, 55, 14, 31, 7, 84, 10 и головки в начальный момент находятся на 63-м цилиндре. Тогда положение головок будет меняться следующим образом:

63

Алгоритм First Come First Served (FCFS)
23
Алгоритм First Come First Served (FCFS)
67
Алгоритм First Come First Served (FCFS)
55
Алгоритм First Come First Served (FCFS)
14
Алгоритм First Come First Served (FCFS)
31
Алгоритм First Come First Served (FCFS)
7
Алгоритм First Come First Served (FCFS)
84
Алгоритм First Come First Served (FCFS)
10

и всего головки переместятся на 329 цилиндров. Неэффективность алгоритма хорошо иллюстрируется двумя последними перемещениями с 7 цилиндра через весь диск на 84 цилиндр и затем опять через весь диск на цилиндр 10. Простая замена порядка двух последних перемещений (7

Алгоритм First Come First Served (FCFS)
10
Алгоритм First Come First Served (FCFS)
84) позволила бы существенно сократить общее время обслуживания запросов. Поэтому давайте перейдем к рассмотрению другого алгоритма.



Содержание раздела