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

                                                                                          Таблица 5
                    Процесс                            p0        p1              p2       p3

Продолжительность очередного CPU burst                 5             3           7        1

    При использовании невытесняющего алгоритма SJF первым для исполнения
будет выбран процесс p3, имеющий наименьшее значение продолжительности
очередного CPU burst. После его завершения для исполнения выбирается процесс
p1, затем p0 и, наконец, p2. Эта картина отражена в таблице 6.
                                                                              Таблица 6
           Вре мя    1    2   3   4   5   6   7    8   9    10 11 12 13 14 15 16
             p0      Г    Г   Г   Г   И   И   И    И   И
             p1      Г    И   И   И
             p2      Г    Г   Г   Г   Г   Г   Г    Г   Г    И    И       И   И    И   И   И
             p3      И
    Как мы видим, среднее время ожидания для алгоритма 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 и различными
моментами их появления в очереди процессов, готовых к исполнению (см. таблица
7).
                                                                                          Таблица 7
                         Время появления в очереди
   Процесс                                                       Продолжительность
                           очередного CPU burst
      p0        0                                            6
      p1        2                                            2
      p2        6                                            7
      p3        0                                            5
   В начальный момент времени в состоянии готовность находятся только два
процесса, p0 и p3. Меньшее время очередного CPU burst оказывается у процесса p3,
поэтому он и выбирается для исполнения (см. таблицу8). По прошествии 2 единиц
времени в систему поступает процесс p1. Время его CPU burst меньше, чем остаток
CPU burst у процесса p3, который вытесняется из состояния исполнение и
переводится в состояние готовность. По прошествии еще 2 единиц времени
процесс p1 завершается, и для исполнения вновь выбирается процесс p3. В момент
времени t = 6 в очереди процессов, готовых к исполнению, появляется процесс p2,
но поскольку ему для работы нужно 7 единиц времени, а процессу p3 осталось
трудиться всего 1 единицу времени, то процесс p3 остается в состоянии
исполнение. После его завершения в момент времени t = 7 в очереди находятся


                                              11