调度算法

article/2025/9/15 16:17:58

1.先来先服务调度算法（FCFS）：

按照到达的先后顺序进行调度。

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

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

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

特殊情况：当有I/O操作（输入/输出）的进程的时候，等待时间=周转时间 - 运行时间 - I/O操作时间

非抢占式的算法：由系统主动结束进程，而非外界将进程中断。

“饥饿”：某进程长期得不到服务，进而导致’饥饿‘

2.短作业优先算法（SJF）：

（1）短进程优先调度算法（SPF）：

该算法是非抢占式的。

P1 $\rightarrow$ P3 $\rightarrow$ P2 $\rightarrow$ P4 :

因为P1到达时间为0，所以P1先进行运算。等P1运算完成时，时间来到了7秒，这时候P2,P3,P4都已经到达。根据短进程优先的原则，P3的运行时间为1秒，所以先进行P3的运算。P3结束后，由于P2与P4的运行时间相同，所以比较到达时间，P2的到达时间比P4快，所以先进行P2的运算，再进行P4的运算。

（2）最短剩余时间优先算法（SRTN）：

该算法是抢占式的。

P1 $\rightarrow$ P2 $\rightarrow$ P3 $\rightarrow$ P2 $\rightarrow$ P4 $\rightarrow$ P1 :

因为P1的到达时间为0，所以先进行P1的运算，当P1运行了两秒时，P2到达，（这时候P1还需要5秒运算完成，而P2只需要4秒完成。根据最短剩余时间优先的规则 ，这时候停止P1的运算，进行P2的运算。 ）当P2运行2秒的时候，P3到达就绪队列（P3只需要1秒就可运行完毕，而P2还需要2秒才能运行完毕。根据最短剩余时间优先的规则，停止P2的运算，进行P3的运算）当P3运行完1秒时（P3已结束），P4已到达。这时候 P1因为一开始已经运行了两秒，所以还剩5秒。同理，P2还剩2秒，P4还剩4秒。进行比较剩余时间，根据最短剩余时间优先的规则，先进行P2的运行，再进行P4的运行，最后进行P1的运行。

注意：

3.高响应比优先算法（HRRN）：

该算法是非抢占式的。

P1 $\rightarrow$ P3 $\rightarrow$ P2 $\rightarrow$ P4 :

首先P1先到达，先进行运算，由于该调度算法是非抢占式的，所以P1会进行到底，进行到底之后，时间过了7秒，这时候P2,P3,P4都到达了，所以要比较响应比，在P1进行到了第4秒的时候，P3开始进入就绪队列，开始进行准备，当P1结束时，P3的等待时间为3秒，要求服务时间为1秒，所以P3的响应比为3。同理，P2,P4的响应比为2.25，1.5。 P3的响应比最大，所以先进行P3的进程。由于该调度算法是非抢占式的，所以P3会进行到底，所以等P3运行结束后，再比较P2与P4的抢占比（要重新计算）,所以就是先进行P2,在进行P4。