多线程最短作业优先调度算法
多线程最短作业优先调度算法
提问于 2021-09-29 08:02:40
我熟悉最短进程下一步调度算法(SJF)，它是一种非抢占式算法。但是，该算法一次只处理一个具有最小突发时间的进程。是否可以一次修改为最短流程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 completedidle表示当前有多少处理器处于空闲状态。在本例中，有2个处理器。可以观察到，在时间t=4处，调度了2个进程，而不是1个。
回答 1
Stack Overflow用户
发布于 2021-09-29 11:19:43
为什么不使用rb树，并根据任务的突发时间将任务添加到树中？
具有最少突发时间的任务(最短的作业)是树中最左边的节点。因此，当您选择下一个任务时，您只需从树中删除最左侧的节点。
任务完成后，您将从rb队列中获取下一个任务。
当任务阻塞时，您将其放在单独的结构中，然后从树中获取下一个任务。您还可以更新突发时间。一旦解除阻塞，您就可以将其重新插入到rb树中。
当任务产生时，更新突发时间并将其重新插入到rb树中，然后从树中获取下一个任务。
您可以让多个处理器从rb树中提取任务，每个处理器将选择具有最低突发时间的处理器。
Linux CFS使用类似的机制。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/69372602
复制相关文章
相似问题
腾讯云开发者
