OS 基础教程

进程管理

同步

死锁

内存管理

文件管理

original icon
版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://www.knowledgedict.com/tutorial/os-srtf-scheduling-algorithm.html

最短剩余时间优先(SRTF)调度算法


该算法是SJF调度的抢先版本。 在SRTF中,过程的执行可以在一段时间后停止。 在每个进程到来时,短期调度程序在可用进程列表和正在运行的进程中以最少的剩余突发时间安排进程。

一旦所有进程都在就绪队列中可用,就不会执行抢占,并且该算法将作为SJF调度工作。 当进程从执行中被移除并且下一个进程被调度时,进程的上下文被保存在进程控制块中。 该PCB在下一次执行该过程时被访问。

示例

在这个例子中,有五个作业:P1P2P3P4P5P6。 它们的到达时间和爆发时间如下表所示。

进程ID 到达时间 突发时间 完成时间 周转时间 等待时间 响应时间
1 0 8 20 20 12 0
2 1 4 10 9 5 1
3 2 2 4 2 0 2
4 3 1 5 2 1 4
5 4 3 13 9 6 10
6 5 2 7 2 0 5

平均等待时间= 24/6

甘特图根据表中给出的到达和爆发时间进行准备。

  1. 因为在0时刻,唯一可用的进程是CPU的CPU突发时间为8的P1。这是列表中唯一可用的进程,因此它是按计划进行的。

  2. 下一个过程在时间单元1到达。由于使用的算法是抢占式的SRTF,所以当前的执行被停止,并且调度器以最小的突发时间检查过程。到目前为止,就绪队列中有两个进程可用。 到目前为止,操作系统已经执行了一个单元的P1; P1的剩余突发时间是7个单位。 过程P2的突发时间是4个单位。 因此,根据算法在CPU上调度进程P2。

  3. 下一个处理P3在时间单元2到达。此时,处理P3的执行停止,并搜索具有最小剩余突发时间的处理。 由于过程P3具有2个单位的突发时间,所以它将被给予优先于其他的优先权。

  4. 下一个进程P4以时间单元3到达。在这个到达时,调度程序将停止P4的执行并检查哪个进程在可用进程(P1,P2,P3和P4)中具有最少的突发时间。 P1和P2的剩余突发时间分别为7个单位和3个单位。
    P3和P4的剩余突发时间各有1个单位。 因为两者都是相同的,所以调度将根据他们的到达时间完成。 P3比P4早到,因此它会再次安排。

  5. 下一个进程P5以时间单元4到达。直到此时,进程P3已经完成执行,并且不在列表中。 调度程序将比较所有可用进程的剩余突发时间。 由于过程P4的突发时间是1,所以这是最少的,因此这将被安排。

  6. 下一个过程P6以时间单元5到达,直到此时,过程P4已经完成其执行。 我们有4个可用的过程,即P1(7),P2(3),P5(3)和P6(2)。 P6的爆发时间是最少的,因此P6被安排。 因为现在所有的过程都是可用的,所以现在算法与SJF一样工作。 P6将被执行直到完成,然后剩余时间最短的过程将被安排。

当所有进程到达,不抢占,算法将作为SJF。