Блог

Я знаком с алгоритмом планирования следующего кратчайшего процесса (SJF), который не является упреждающим алгоритмом. Но этот алгоритм обрабатывает только один процесс за раз, который имеет наименьшее время всплеска. Может ли он быть изменен как Самый короткий процесс, следующий за 2 за раз?

Итак, для примера, упомянутого здесь:

 5
A 0 3
B 2 6
C 4 4
D 6 5
E 8 2
 

Первые строки обозначают общее количество процессов.
Последующие строки обозначают Идентификатор процесса, Время прибытия, Время пакета.

Планирование SJF с одновременным выполнением 2 процессов будет работать следующим образом :

 Time |    A |    B |    C |    D |    E | IDLE |
------------------------------------------------
   0 |   O  |      |      |      |      |   1  |
   1 |   O  |      |      |      |      |   1  |
   2 |   X  |   O  |      |      |      |      |
   3 |      |   O  |      |      |      |   1  |
   4 |      |   O  |   O  |      |      |      |
   5 |      |   O  |   O  |      |      |      |
   6 |      |   O  |   O  |      |      |      |
   7 |      |   X  |   X  |      |      |      |
   8 |      |      |      |   O  |   O  |      |
   9 |      |      |      |   O  |   X  |      |
  10 |      |      |      |   O  |      |   1  |
  11 |      |      |      |   O  |      |   1  |
  12 |      |      |      |   X  |      |   1  |
 

Здесь,

 O: Process scheduled
X: Process completed
 

Простоя означает, сколько процессоров в данный момент простаивает. Для этого случая есть 2 процессора.
Можно заметить , что в данный момент t=4 запланировано 2 процесса вместо 1.

Почему бы не использовать rb-дерево и не добавлять задачи в дерево в зависимости от времени их выполнения?

Задачи с наименьшим временем выполнения (самое короткое задание) — это самый левый узел в дереве. Поэтому, когда вы выбираете свои следующие задачи, вы просто удаляете самый левый узел из дерева.

Когда задача будет выполнена, вы возьмете следующую задачу из очереди rb.

Когда задача блокируется, вы помещаете ее в отдельную структуру и берете следующую задачу из дерева. Вы также обновляете время пакета. Как только он разблокируется, вы снова вставляете его обратно в rb-дерево.

Когда задача завершается, вы обновляете время пакета и повторно вставляете его обратно в дерево rb, а затем берете следующую задачу из дерева.

И у вас может быть несколько процессоров, выполняющих задачи из дерева rb, и каждый из них выберет тот, у которого наименьшее время пакетной обработки.

CFS Linux использует аналогичный механизм.