Операционные системы. Макушкина Л.А - 10 стр.

= 4 единицам времени. Среднее полное время исполнения составит (18 + 9 + 3)/3 =
10 единиц времени.
                                                                       Таблица 4
   Вре мя   1   2   3   4   5   6   7   8    9   10 11 12 13 14 15 16 17 18
     p0     И   Г   Г   И   Г   И   Г   И    Г   И И И И И И И И И
     p1     Г   И   Г   Г   И   Г   И   Г    И
     p2     Г   Г   И
   При очень больших величинах кванта времени, когда каждый процесс успевает
завершить свой CPU burst до возникновения прерывания по времени, алгоритм RR
вырождается в алгоритм FCFS. При очень малых величинах создается иллюзия
того, что каждый из n процессов работает на собственном виртуальном процессоре
с производительностью ~ 1/n от производительности реального процессора.
Правда, это справедливо лишь при теоретическом анализе при условии
пренебрежения временами переключения контекста процессов. В реальных
условиях при слишком малой величине кванта времени и, соответственно,
слишком частом переключении контекста накладные расходы на переключение
резко снижают производительность системы.

   2.1.3 Shortest-Job-First (SJF)
   При рассмотрении алгоритмов FCFS и RR мы видели, насколько существенным
для них является порядок расположения процессов в очереди процессов, готовых к
исполнению. Если короткие задачи расположены в очереди ближе к ее началу, то
общая производительность этих алгоритмов значительно возрастает. Если бы мы
знали время следующих CPU burst для процессов, находящихся в состоянии
готовность, то могли бы выбрать для исполнения не процесс из начала очереди, а
процесс с минимальной длительностью CPU burst. Если же таких процессов два
или больше, то для выбора одного из них можно использовать уже известный нам
алгоритм FCFS. Квантование времени при этом не применяется. Описанный
алгоритм получил название "кратчайшая работа первой" или Shortest Job First
(SJF).
   SJF-алгоритм краткосрочного планирования может быть как вытесняющим, так
и невытесняющим. При невытесняющем SJF-планировании процессор
предоставляется избранному процессу на все необходимое ему время, независимо
от событий, происходящих в вычислительной системе. При вытесняющем SJF-
планировании учитывается появление новых процессов в очереди готовых к
исполнению (из числа вновь родившихся или разблокированных) во время работы
выбранного процесса. Если CPU burst нового процесса меньше, чем остаток CPU
burst у исполняющегося, то исполняющийся процесс вытесняется новым.
   Рассмотрим пример работы невытесняющего алгоритма SJF. Пусть в состоянии
готовность находятся четыре процесса, p0, p1, p2 и p3, для которых известны
времена их очередных CPU burst. Эти времена приведены в таблице 5. Как и
прежде, будем полагать, что вся деятельность процессов ограничивается
использованием только одного промежутка CPU burst, что процессы не совершают
операций ввода-вывода и что временем переключения контекста можно
пренебречь.

                                        10