The design of the UNIX Operating System 5 страница
Как мы видим, среднее время ожидания для алгоритма SJF составляет (4 + 1 + 9 + 0)/4 = 3,5 единицы времени. Легко посчитать , что для алгоритма FCFS при порядке процессов p0, p1, p2, p3 эта величина бу - дет равняться (0 + 5 + 8 + 15)/4 = 7 единицам времени, т. е. будет в два раза больше, чем для алгоритма SJF. Можно показать, что для заданного набора процессов (если в очереди не появляются новые процес-сы) алгоритм SJF является оптимальным с точки зрения минимизации среднего времени ожидания среди класса невытесняющих алгоритмов.
|
|
|
Для рассмотрения примера вытесняющего SJF планирования мы возьмем ряд процессов p0, p1, p2 и p3 с различными временами CPU burst и различными моментами их появления в очереди процессов, готовых к исполнению (см. табл. 3.6.).
Таблица 3.6.
Процесс Время появления в очереди очередного CPU burst Продолжительность
p 0
p 1
p 2
p 3
| 0 | 6 | |||
|
| ||||
| 2 | 2 | |||
|
| ||||
| 6 | 7 | |||
|
| ||||
| 0 | 5 | |||
В начальный момент времени в состоянии готовность находятся только два процесса , p0 и p3. Меньшее время очередного CPU burst оказывается у процесса p3, поэтому он и выбирается для исполнения (см. таблицу3.7.) . По прошествии 2 единиц времени в систему поступает процесс p1. Время его CPU burst меньше , чем остаток CPU burst у процесса p3, который вытесняется из состояния исполнение и перево-дится в состояние готовность. По прошествии еще 2 единиц времени процесс p1 завершается, и для ис-полнения вновь выбирается процесс p3. В момент времени t = 6 в очереди процессов , готовых к исполне-нию, появляется процесс p2, но поскольку ему для работы нужно 7 единиц времени, а процессу p3 оста-лось трудиться всего 1 единицу времени, то процесс p3 остается в состоянии исполнение. После его за-вершения в момент времени t = 7 в очереди находятся процессы p0 и p2 , из которых выбирается процесс p0. Наконец, последним получит возможность выполняться процесс p2.
|
|
|
|
|
|
| Таблица 3.7. | ||||||||||
| Время 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 11 12 13 14 15 16 17 18 19 20 | |
| p 0 | Г Г Г Г Г Г Г И И И И И И | |||||||||
| p 1 | И И | |||||||||
| p 2 | Г Г Г Г Г Г Г И И И И И И И | |||||||||
| p 3 | И И Г Г И И И | |||||||||
Дата добавления: 2021-01-21; просмотров: 99; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!