SJF调度算法（操作系统）短作业优先和最短剩余时间优先

SJF短作业优先算法

算法思想： 追求更少的平均时间，最少的平均周转时间，最少的平均平均带权周转时间

算法规则： 最短的作业/进程优先得到服务（所谓“最短”，是指要求服务时间最短）

用于作业/进程调度： 即可用于作业调度，也可用于进程调度。用于进程调度时称为“短进程优先（SPF，Shortest Process First）算法”

是否可抢占？： SJF和SPF都是 非抢占式的算法 。但是也有抢占式的版本—- 最短剩余时间优先算法。（SRTN,Shortest Remaining Time Next）

优点： “最短的"平均等待时间、平均周转时间

缺点： 不公平。 对短作业有利，对长作业不利 。可能产生==饥饿现象。==另外，进程/作业的运行时间都是由用户提供的，并不一定真实，不一定能做到真正的短作业优先。

饥饿： 会导致饥饿

例题

例题：各进程到达就绪队列的时间、需要的运行时间如下所示，使用 非抢占式的短作业优先 调度算法，计算各进程的等待时间、平均等待时间、周转时间、平均周转时间、带权周转时间、平均带权周转时间

短作业/进程优先调度算法：每次调度选择 当前已到达 且 运行时间最短 的作业/进程。

经过简单的分析之后，可以知道 调度顺序为 p1–>p3–>p2–>p4

下面我们来用最短剩余时间来考虑：

最短剩余时间优先 算法：每当有进程加入 就绪队列改变时就需要调度 ，如果新到达的进程 剩余时间 比当前运行的进程剩余时间 更短 ，则由新进程 抢占 处理机，当前运行进程重新回到就绪队列。另外,当一个 进程完成时也需要调度。

需要注意的是，当有新进程到达时就绪队列就会改变，就要按照上述规则就行检查。以下p n (m)表示当前p n 进程剩余时间为m。每个时刻的情况如下

(我们用黄色表示这个时刻剩余时间最短的进程)

• 0时刻（p1到达）： p 1 (7)
• 2时刻（p2到达）：p 1 (5) 、 p 2 (4)
• 4时刻（p3到达）：p 1 (5)、p 2 （2）、 p 3 (1)
• 5时刻(p3完成且p4刚好到达)：p 1 (5)、 p 2 （2） 、p 4 (4)
• 7时刻（p2完成）：p 1 (5)、= p 4 (4)
• 11时刻（p4完成）：p 1 (5)
• 16时刻（p1完成）：结束

周转时间=完成时间-到达时间

带权周转时间=周转时间 / 运行时间

等待时间=周转时间- 运行时间

平均周转时间=（16+5+1+6）/4=7

平均带权周转时间=(2.28+1.25+1+1.5)/4=1.5

平均等待时间=(9+1+0+2)/4=3

68747470733a2f2f62:6c6f672e6373646e2e6e65742f6d305f34373634323337362f:61727469636c652f64657461696c732f313037383935343832