最短剩余时间优先法则SRTN
时间: 2023-07-19 17:50:07 浏览: 115
最短剩余时间优先(Shortest Remaining Time Next,SRTN)是一种调度算法,它选择剩余时间最短的进程优先执行,以最小化平均等待时间和平均周转时间。在SRTN中,进程的剩余CPU时间是动态计算的,因此可以更准确地反映进程的实际需求。
SRTN算法的基本思想是,对于就绪队列中的所有进程,每次都选择剩余时间最短的进程来运行。如果一个新的进程到达了系统,它的剩余时间比当前运行的进程还要短,那么当前进程就会被暂停,新进程得以运行。
SRTN算法可以避免长作业的饥饿现象,但是由于需要频繁地计算剩余时间,因此会增加系统的开销。此外,SRTN算法也可能会导致进程的抢占,从而影响系统的响应时间。
相关问题
最短剩余时间优先法则SRTN会引发饥饿吗
最短剩余时间优先(SRTN)调度算法不会引发饥饿问题,因为该算法保证了短作业优先,每个进程都有机会被运行。SRTN算法在每次选择进程时,都会选择剩余时间最短的进程来运行,这样保证了短作业优先,避免了长作业的饥饿现象。
当一个进程到达系统时,SRTN算法会检查就绪队列中所有进程的剩余时间,并选择剩余时间最短的进程来运行。如果有一个进程的剩余时间比当前正在运行的进程还短,那么当前进程就会被暂停,新进程得以运行。这样,即使有长作业存在,也可以在短作业运行完毕后被运行,避免了饥饿现象的发生。
因此,SRTN算法是一种有效的调度算法,可以在保证短作业优先的前提下,避免饥饿问题的发生。
各进程到达就绪队列的时间、运行时间和优先级如表1所示(注:优先级数值越大,优先级越高)。 问题:分别使用抢占式的最短剩余时间优先算法(SRTN)和时间片为2的时间片轮转调度算法(RR),分析进程调度情况并计算平均周转时间。 表1进程调度表 进程 到达时间 运行时间 优先数 P1 0 7 1 P2 4 1 2 P3 4 1 3 P4 5 4 2
使用抢占式的最短剩余时间优先算法(SRTN):
1. 初始状态:所有进程均未执行,就绪队列为空;
2. 当前时间为0,进程P1到达就绪队列,就绪队列为P1;
3. 进程P1执行时间片7,当前时间为7,进程P1结束;
4. 当前时间为7,进程P2和P3同时到达就绪队列,就绪队列为P2 -> P3;
5. 进程P2执行时间片1,当前时间为8,进程P2结束;
6. 当前时间为8,就绪队列为P3;
7. 进程P3执行时间片1,当前时间为9,进程P3结束;
8. 当前时间为9,进程P4到达就绪队列,就绪队列为P4;
9. 进程P4执行时间片4,当前时间为13,进程P4结束;
10. 所有进程执行完毕,计算平均周转时间:
P1周转时间 = 7 - 0 = 7
P2周转时间 = 8 - 4 = 4
P3周转时间 = 9 - 4 = 5
P4周转时间 = 13 - 5 = 8
平均周转时间 = (7 + 4 + 5 + 8) / 4 = 6
使用时间片为2的时间片轮转调度算法(RR):
1. 初始状态:所有进程均未执行,就绪队列为空;
2. 当前时间为0,进程P1到达就绪队列,就绪队列为P1;
3. 进程P1执行时间片2,当前时间为2,进程P1仍需执行时间为5,进程P1被挂起,就绪队列为P2 -> P3;
4. 进程P2执行时间片2,当前时间为4,进程P2仍需执行时间为1,进程P2结束;
5. 当前时间为4,就绪队列为P3;
6. 进程P3执行时间片2,当前时间为6,进程P3仍需执行时间为1,进程P3结束;
7. 当前时间为6,进程P4到达就绪队列,就绪队列为P4 -> P3;
8. 进程P4执行时间片2,当前时间为8,进程P4仍需执行时间为2,进程P4被挂起,就绪队列为P3;
9. 进程P3执行时间片2,当前时间为10,进程P3结束;
10. 进程P4执行时间片2,当前时间为12,进程P4结束;
11. 所有进程执行完毕,计算平均周转时间:
P1周转时间 = 7 - 0 = 7
P2周转时间 = 4 - 4 = 0
P3周转时间 = 10 - 4 = 6
P4周转时间 = 12 - 5 = 7
平均周转时间 = (7 + 0 + 6 + 7) / 4 = 5