个性化阅读
专注于IT技术分析

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

点击下载

该算法是SJF调度的抢先版本。在SRTF中, 可以在一定时间后停止该线程的执行。在每个进程到达时, 短期调度程序都会在可用进程列表和正在运行的进程中以最小的突发时间来调度进程。

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

例子

在此示例中, 有五个作业P1, P2, P3, P4, P5和P6。它们的到达时间和突发时间在下表中给出。

Process ID 到达时间 Burst Time Completion Time 周转时间 等待的时间 响应时间
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
os srtf调度算法

平均等待时间= 24/6

甘特图是根据表中给出的到达时间和突发时间准备的。

  1. 由于在时间0, 唯一可用的进程是CPU突发时间为8的P1。这是列表中唯一可用的进程, 因此已对其进行了调度。
  2. 下一个进程到达时间单位1。由于我们使用的算法是SRTF, 它是抢占算法, 因此当前执行将停止, 并且调度程序将以最少的突发时间检查该进程。
    到目前为止, 就绪队列中有两个可用的进程。到目前为止, OS已经执行了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个单位。
  5. P3和P4的剩余突发时间各为1个单位。由于两者相等, 因此将根据其到达时间进行调度。 P3早于P4到达, 因此将再次安排。
  6. 下一进程P5在时间单元4到达。直到此时, 进程P3已完成其执行, 并且不再存在于列表中。调度程序将比较所有可用进程的剩余突发时间。由于线程P4的突发时间是1, 这是所有事件中最少的, 因此将对其进行调度。
  7. 下一线程P6到达时间单元5, 直到此时, 线程P4已经完成其执行。到目前为止, 我们有4个可用线程, 分别是P1(7), P2(3), P5(3)和P6(2)。在所有事件中, P6的突发时间是最短的, 因此计划了P6。由于现在所有进程都可用, 因此算法现在将与SJF相同。 P6将一直执行到完成为止, 然后安排剩余时间最少的线程。

一旦所有进程到达, 就不会进行抢占, 该算法将作为SJF工作。

赞(2)
未经允许不得转载:srcmini » 最短剩余时间优先(SRTF)调度算法

评论 抢沙发

评论前必须登录!