0

我熟悉 Shortest Process next Scheduling Algorithm (SJF)，它是一种非抢占式算法。但是，该算法一次只处理一个具有最小突发时间的进程。可以一次修改为 Shortest Process Next 2 吗？

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

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

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

一次有 2 个进程的 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 个处理器。可以观察到，在 time t=4，调度了 2 个进程而不是 1 个。

4

1 回答 1

0

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

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

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

当任务阻塞时，你把它放在一个单独的结构上，然后从树中取出下一个任务。您还可以更新突发时间。一旦它解除阻塞，你将它重新插入到 rb-tree 中。

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

您可以让多个处理器从 rb-tree 中执行任务，每个处理器都会选择突发时间最短的一个。

Linux CFS 使用类似的机制。

于 2021-09-29T11:19:42.850 回答