当前位置：文江博客话题详情

Muntz-Coffman 算法（调度）

发布于 2024-11-08 19:22:05 字数 123 浏览 5 评论 0原文

Muntz Coffman example

我想知道你到底如何计算时间片 (2, 4, 5.5, 7, 8.5) 。

原文

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

小猫一只 2024-11-15 19:22:05

Muntz–Coffman 基本上是关键路径方法。每个作业的优先级是从该作业开始的依赖链的最大持续时间。在每个时间点，正在运行的作业都是具有最高优先级的作业。

初始优先级以逆拓扑顺序在线性时间内计算。

K: 1 + max(0) = 1
H: 1 + max(0, K) = 2
I: 2 + max(0, K) = 3
J: 4 + max(0) = 4
E: 3 + max(0, H) = 5
F: 2 + max(0, H, I) = 5
G: 3 + max(0, I, J) = 7
A: 2 + max(0, E, F) = 7
B: 1 + max(0, E, F, G) = 8
C: 1 + max(0, G) = 8
D: 2 + max(0, F, G) = 9

D（2 个单位）是唯一的最大值，因此它拥有一台完全属于自己的机器。 B（1 台）和 C（1 台）平局，因此它们将另一台机器平分为 50/50。在t时刻，D的优先级为9-2t，B和C的优先级为8-t。在这三项工作完成之前，它们仍然高于优先级 7（次高），D 高于 B 和 C，B 和 C 保持平局。

在时间 2，次高的是 A（2 个单位）和 G（3 个单位），它们各自接收自己的机器。 2个单位时间后，A完成，G的优先级降低到5，与E和F并列。现在E、F和G都以均匀的三路分割进行调度，一直持续到时间5.5，此时点 G 已完成，其他点现在处于优先级 4，将它们与 J 联系起来。

三向工作持续到时间 7，F 完成，E 和 J 的优先级已滑落至 3。现在 E、I、和 J 被调度，直到 E 完成并且 I 和 J 的优先级降到 2，此时（时间 8.5）H、I 和 J 被调度。 H 和 I 完成，J 处于 1，此时（时间 10）J 和 K 被安排为 50/50，直到时间 11 结束。

Muntz–Coffman is basically the critical path method. The priority of each job is the maximum duration of a chain of dependencies starting from that job. At each point in time, the running jobs are those with the highest priority.

Initial priorities are computed in linear time in reverse topological order.

K: 1 + max(0) = 1
H: 1 + max(0, K) = 2
I: 2 + max(0, K) = 3
J: 4 + max(0) = 4
E: 3 + max(0, H) = 5
F: 2 + max(0, H, I) = 5
G: 3 + max(0, I, J) = 7
A: 2 + max(0, E, F) = 7
B: 1 + max(0, E, F, G) = 8
C: 1 + max(0, G) = 8
D: 2 + max(0, F, G) = 9

D (2 units) is the unique maximum, so it gets a machine all to itself. B (1 unit) and C (1 unit) are tied, so they split the other machine 50/50. At time t, the priority of D is 9 - 2t, and the priority of B and C is 8 - t. Until these three jobs finish, they remain above priority 7, the next highest, D is above B and C, and B and C remain tied.

At time 2, the next highest are A (2 units) and G (3 units), which each receive their own machine. After 2 units of time, A is done, and G's priority has been reduced to 5, tying with E and F. Now E, F, and G are all scheduled with an even three-way split, which lasts until time 5.5 at which point G is finished and the the others are now at priority 4, tying them with J.

Three-way work continues until at time 7, F is done and E's and J's priorities have slipped to 3. Now E, I, and J are scheduled until E is done and I's and J's priorities are down to 2, at which point (time 8.5) H, I, and J are scheduled. H and I finish and J is at 1, at which point (time 10) J and K are scheduled 50/50 until the end at time 11.

回复收藏 0 原文

~没有更多了~