多线程最短作业优先调度算法

Question

我熟悉最短进程下一个调度算法（SJF），它是一种非抢先算法。但是，该算法一次只能处理一个突发时间最小的进程。是否可以一次修改为“下一个最短流程2”？

所以对于这里提到的例子：

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

第一行表示进程总数。随后的行表示进程ID、到达时间、突发时间。

一次有两个流程的SJF计划将按如下方式工作:

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

Idle表示当前有多少处理器空闲。在这种情况下，有2个处理器。可以观察到，在时间< code>t=4，有2个进程被调度，而不是1个。

Answer 1

为什么不使用rb树并根据任务的突发时间将任务添加到树中？

突发时间最少的任务（最短的作业）是树中最左边的节点。因此，当您选择下一个任务时，只需从树中删除最左边的节点。

任务完成后，您将从rb队列中获取下一个任务。

当任务阻塞时，您将其放在一个单独的结构上，并从树中获取下一个任务。您还更新突发时间。一旦它解除阻塞，您将其重新插入到rb-树中。

当任务产生时，更新突发时间并将其重新插入rb树中，然后从树中获取下一个任务。

您可以让多个处理器从rb树中获取任务，每个处理器都会选择突发时间最低的一个。

Linux CFS使用类似的机制。