为什么先发制人SJF的平均等待时间保证不会大于非抢先SJF调度的平均等待时间?

问题描述 投票:0回答:1

SJF =最短的工作第一,标题不会让我适应它

抢先的SJF调度不会使进程的平均等待时间大于在非抢占式SJF调度算法中执行的时间吗?毕竟,您不断进行上下文切换,并迫使流程等待更长时间才能完成。

我似乎无法理解为什么先发制人的SJF(又名:Shortest-Time-Remaining-First,或STRF)优于非抢占式SJF(就进程的平均等待时间而言)。

谁可以给我解释一下这个?

谢谢。

scheduling job-scheduling
1个回答
1
投票

假设p1(8ms突发时间)在0ms到达队列,在执行p1 1ms后,另一个进程p2以4ms突发时间进入队列。该过程将停止执行过程p1并将开始执行过程p2。为什么?因为p1剩余7ms才能完成执行,而p1只剩下4 ms完成执行。

我认为很明显为什么它被称为“最短剩余时间优先”调度。因为它总是选择一个剩余时间最少的进程来执行。

对于你的另一个问题,为什么它更好....让我们扩展场景。

处理p1 - >突发时间8 ms,到达时间0 ms,

处理p2 - >突发时间4 ms,到达时间1 ms,

处理p3 - >突发时间9 ms,到达时间2 ms,

处理p4 - >突发时间5毫秒,到达时间3毫秒。

对于抢占式SJF,平均等待时间= [(对于p1)(10-1)+(对于p2)(1-1)+(对于p3)(17-2)+(对于p4)(5-3)] / 4 = 6.5毫秒

对于非抢占式SJF,平均等待时间= [(对于p1)(0)+(对于p2)(8-1)+(对于p3)(17-2)+(对于p4)(12-3) ] / 4 = 7.75毫秒

你可以看出为什么说preemptive比非抢先更好,这是因为使用这个算法执行所有过程所需的时间更少。

参考:Galvin,Silberschatz,Gagne的操作系统概念(第8版)。

© www.soinside.com 2019 - 2024. All rights reserved.