第八讲进程调度算法.ppt

共28页第8页
College of Technology and Engineering /
进程调度算法
共28页第10页
College of Technology and Engineering /
七种进程调度算法
先来先服务算法(FCFS)
短作业优先算法(SPF)
时间片轮转算法
优先级调度算法
最短剩余时间优先调度算法(可剥夺的SPF)
最高响应比优先调度算法
多级反馈队列调度算法
一、FCFS
基本思想:按照进程进入就绪队列的先后次序进行选择。
特点:属于非剥夺调度方式,看似公平,但对后进入的短进程、I/O型进程不公平
【例1】假设就绪队列中从队首开始依次排列有四个进程 P1、P2、P3、P4(假设它们几乎在0时刻同时到达就绪队列),它们的预计执行时间分别为16、12、4、3,若采用FCFS调度:
(1)试给出这些进程的运行进度表;
(2)计算各进程的周转时间和等待时间;
(3)计算系统的平均周转时间和平均等待时间;
解:(1)FCFS运行进度表:
0
16
28
32
35
P1
P2
P3
P4
(2)
进程
到达时刻
运行时间
开始时刻
结束时刻
周转时间
等待时间
P1
0
16
0
16
16
0
P2
0
12
16
28
28
16
P3
0
4
28
32
32
28
P4
0
3
32
35
35
32
(3)平均周转时间=(16+28+32+35)/4=28
平均等待时间=(0+16+28+32)/4=19
一、FCFS
一、FCFS
分析:
对短进程不公平。
当长进程排在就绪队列的前面时必将增加后面许多小进程的等待时间,从而将增加系统的平均周转时间。
不利于I/O型进程,未有效利用系统资源
现已很少用作主要的调度(分/实时系统中不能用),一般与其他调度算法混合使用。
FCFS同时适合于三级调度。
二、SPF
二、短进程优先(SPF--Short Process First)
基本思想:从进程的就绪队列中选择所需运行时间最短的进程占用处理机。
特点:属于非剥夺调度方式,不适合于分/实时系统。
【例2】同上例,用SPF求解。
分析:
与FCFS相比,降低了系统的平均等待时间和平均周转时间,改善了系统性能。
很难准确预测进程的执行时间,致使该算法很难真正做到短进程优先。
可能导致长进程饥饿,对长进程不公平。
采用非剥夺调度方式,未考虑进程的紧迫程度。
可用于作业调度和进程调度
二、SPF
三、时间片轮转算法
基本思想:
系统将所有就绪进程按到达时间的先后次序排成一个队列,进程调度程序总是按FCFS选择队首的进程执行,并规定其执行完一个时间片时,系统将它送至就绪队列的末尾,再把处理机分配给就绪队列的队首进程。这样,处于就绪队列中的进程,就可以依次轮流的获得一个时间片的处理时间,然后回到队列尾部,如此不断循环,直至完成为止。
特点:属于剥夺调度方式,分时系统的典型调度算法。(只用于进程调度)
三、时间片轮转算法
引例:请同学们思考,假设火车站限每人每次只可买一张票,现有4个人排队买票,要买的张数依次是6、4、8、5,那么他们买票的过程是?
分析:现将买一张票的时间看作一个时间片,4个人买票的过程分别看作进程1,2,3,4,那么它们就是采用时间片轮转算法的思想进行的。
三、时间片轮转算法
【例3】假设一个进程组有4(进程1,2,3,4)个进程,假设它们都在时刻0到达,到达的顺序为1、2、3、4,它们的执行时间分别为6、4、8、5(s),若采用时间片轮转调度算法调度,试给出当时间片分别为1s和4s时进程的运行进度表,并计算平均周转时间和平均等待时间。