(1)先来先服务调度算法(FCFS)(作业、进程调度):算法简单,但效率较低;有利于长作业,但对短作业不利,有利于CPU繁忙型作业,不利于I/O繁忙型作业。
(2)短作业优先调度算法(SJF)(作业、进程调度):运行时间短的进程(作业)优先执行,该算法对长作业不利,易造成“饥饿”问题,即长进程(作业)由于优先级低可能长期得不到处理。
(3)时间片轮转调度算法(进程调度):
时间片的大小对系统性能影响很大,如果时间片足够大,以至于所有的进程都能在一个时间片内执行完毕,则退化为FCFS算法,如果时间片很小,那么处理机在进程间频繁切换,处理机真正用于运行用户进程的时间将减少。
时间片的长短由:系统的响应时间、就绪队列中的进程个数和系统的处理能力决定。
(4)优先级调度算法(作业、进程调度):根据进程优先级决定运行的进程
(5)高响应比优先调度算法(作业调度):响应比 = 1 + 作业等待时间/估计运行时间重点内容
(6)多级队列调度算法(进程调度):对多个就绪队列设计不同的调度算法
(7)多级反馈队列调度算法:(UNIX调度用这个)
综合了FCFS调度算法和优先级调度算法
实现思想:
1) 系统中设置多个就绪队列,每个就绪队列对应一个优先级,第一个队列优先级最高,第二个次之,其余队列的优先级依次降低。
2) 每个队列中进程执行的时间片大小各不相同,进程所在队列的优先级越高,其相应的时间片越短,也就是说,优先级越高的队列中它的时间片就越短。
3) 当一个新进程进行系统时,首先把它放到第一个队列额末尾,安装FCFS的原则排队等待调度。当轮到该进程执行时,如能在此时间片内完成,便可准备撤离系统,如果它在一个时间片结束的时候尚未完成,调度程序便将该进程转入第2个队列,再同样按FCFS的原则等待调度;如果它在第2个队列中运行一个时间片后,仍未完成,转入第三个队列中。如此下去,在最后一个队列中使用时间片轮转调度算法。
4) 仅当第一个队列为空的时,调度程序才从第二个队列中选择进程运行;仅当第1个队列至第 i-1 为空的时,调度程序才从第 i 个队列中选择进程运行。当处理器正在执行第 i 个队列中的进程时,若又有新进程进入优先级较高的队列中,则此时新进程将抢占正在运行进程的处理机,即由调度程序把正在执行的进程放回第 i 个队列,重新将处理机分配给优先级更高的新进程。
作业的周转时间(Ti) = 作业 i 的等待时间 + 作业 i 的运行时间(作业 i 的完成时间 - 作业 i 的提交时间)
平均周转时间(T) = (T1 + T2 + ….. + Tn )/n
带权周转时间 (Wi)= 作业 i 的周转时间 /作业 i 的运行时间.
平均带权周转时间(W) = (W1 + W2 + …… + Wn) / n
例题:
例如到达时刻和运行时间如图所示:
作业号 | 到达时间 | 运行时间 | 优先级(越小越优先) |
---|---|---|---|
A | 0 | 2 | 4 |
B | 1 | 5 | 9 |
C | 2 | 8 | 1 |
D | 3 | 3 | 8 |
先来先服务:
作业号 | 到达时间 | 运行时间 | 等待时间 | 开始时间 | 结束时间 | 周转时间 | 带权周转时间 |
---|---|---|---|---|---|---|---|
A | 0 | 2 | 0 | 0 | 2 | 2 | 2/2=1 |
B | 1 | 5 | 1 | 2 | 7 | 6 | 6/5=1.2 |
C | 2 | 8 | 5 | 7 | 15 | 13 | 13/8=1.625 |
D | 3 | 3 | 12 | 15 | 18 | 15 | 15/3=5 |
平均 | 9 | 2.2 |
短作业优先:
作业号 | 到达时间 | 运行时间 | 等待时间 | 开始时间 | 结束时间 | 周转时间 | 带权周转时间 |
---|---|---|---|---|---|---|---|
A | 0 | 2 | 0 | 0 | 2 | 2 | 2/2=1 |
B | 1 | 5 | 1 | 2 | 7 | 6 | 6/5=1.2 |
D | 3 | 3 | 4 | 7 | 10 | 7 | 7/3=2.33 |
C | 2 | 8 | 8 | 10 | 18 | 16 | 16/8=2 |
平均 | 7.75 | 1.63 |
静态优先级:
作业号 | 到达时间 | 运行时间 | 等待时间 | 开始时间 | 结束时间 | 周转时间 | 带权周转时间 |
---|---|---|---|---|---|---|---|
A | 0 | 2 | 0 | 0 | 2 | 2 | 2/2=1 |
C | 2 | 8 | 0 | 2 | 10 | 8 | 8/8=1 |
D | 3 | 3 | 7 | 10 | 13 | 10 | 10/3=3.33 |
B | 1 | 5 | 12 | 13 | 18 | 17 | 17/5=3.4 |
平均 | 9.25 | 2.18 |
例二:
4个进程A、B、C、D,同时到达,运行时间分别为6、3、1、7(ms),采用时间片轮转调度算法(时间片分别为1和3,不可抢占)
时间片为1
调度图:
1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
A | B | C | D | A | B | D | A | B | D | A | D | A | D | A | D | D |
平均等待时间:((0+3+2+2+1+1)+(1+3+2)+2+(3+2+2+1+1+1+0))/4 = 6.75
平均周转时间 = 平均等待时间 + 平均运行时间 = 6.75 + (6+3+1+7)/4 = 11
时间片为3:
调度图:
1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
A | A | A | B | B | B | C | D | D | D | A | A | A | D | D | D | D |
平均等待时间:((0+7)+3+6+(7+3))/4 = 6.5
平均周转时间 = 平均等待时间 + 平均运行时间 = 6.5 + (6+3+1+7)/4 = 10.75