Время появления в очереди очередного CPU burst

↑

⇐ ПредыдущаяСтр 6 из 10Следующая ⇒

Таблица 3.5.

Время

p₀

Г

Г

Г

Г

И

И

И

И

И

p₁

Г

И

И

И

p₂

Г

Г

Г

Г

Г

Г

Г

Г

Г

И

И

И

И

И

И

И

p₃

И

Как мы видим, среднее время ожидания для алгоритма SJF составляет (4 + 1 + 9 + 0)/4 = 3,5 единицы времени. Легко посчитать, что для алгоритма FCFS при порядке процессов p₀, p₁, p₂, p₃ эта величина будет равняться (0 + 5 + 8 + 15)/4 = 7 единицам времени, т. е. будет в два раза больше, чем для алгоритма SJF. Можно показать, что для заданного набора процессов (если в очереди не появляются новые процессы) алгоритм SJF является оптимальным с точки зрения минимизации среднего времени ожидания среди класса невытесняющих алгоритмов.

Для рассмотрения примера вытесняющего SJF планирования мы возьмем ряд процессов p0, p1, p2 и p3 с различными временами CPU burst и различными моментами их появления в очереди процессов, готовых к исполнению (см. табл. 3.6.).

Таблица 3.6.

Процесс

Время появления в очереди очередного CPU burst

Продолжительность

p₀

p₁

p₂

p₃

В начальный момент времени в состоянии готовность находятся только два процесса, p₀ и p₃. Меньшее время очередного CPU burst оказывается у процесса p₃, поэтому он и выбирается для исполнения (см. таблицу 3.7.). По прошествии 2 единиц времени в систему поступает процесс p₁. Время его CPU burst меньше, чем остаток CPU burst у процесса p₃, который вытесняется из состояния исполнение и переводится в состояние готовность. По прошествии еще 2 единиц времени процесс p₁ завершается, и для исполнения вновь выбирается процесс p₃. В момент времени t = 6 в очереди процессов, готовых к исполнению, появляется процесс p₂, но поскольку ему для работы нужно 7 единиц времени, а процессу p₃ осталось трудиться всего 1 единицу времени, то процесс p₃ остается в состоянии исполнение. После его завершения в момент времени t = 7 в очереди находятся процессы p₀ и p₂, из которых выбирается процесс p₀. Наконец, последним получит возможность выполняться процесс p₂.

Познавательные статьи:



Коммуникативные барьеры и пути их преодоления

Рынок недвижимости. Сущность недвижимости

Решение задач с использованием генеалогического метода

История происхождения и развития детской игры