进程从就绪态转化为运行态,或者从运行态转化为就绪态都需要调度器
CPU运行哪个进程由调度算法决定。
一个进程在CPU上运行的时间由时间片决定。
执行调度器/调度程序的时机:
如果是非抢占式调度策略:只有在进程退出,或者进程阻塞的时候才会触发调度器
抢占式调度策略:每个或每K个时钟中断都会触发调度器。
需要注意:
如果没有进程就绪时,此时CPU就会运行闲逛进程。
闲逛进程的特点:
CPU利用率: (CPU处于忙碌时间)÷(CPU总时间)(通常会考察多道程序并发执行的情况下CPU利用率)
系统吞吐量: 单位时间内完成的作业数目
系统吞吐量=(一段时间内完成的作业数目÷一段时间)
周转时间: 作业被提交到系统到作业完成的这段时间
等待时间: 进程/作业处于等待处理机状态的时间
相应时间: 用户提交请求到首次产生响应所用的时间
思路:按照作业,进程到达的先后顺序进行服务
当用于作业调度时:考虑那个作业先到达后备队列。
当用于进程调度时:考虑那个进行先到达就绪队列。
FCFS调度算法是非抢占式的调度算法
解:这些进程都是纯计算型进程,首先采用先来先服务调度算法,进程的调度顺序为:
p1->p2->p3->p4
周转时间:(完成时间-到达时间)
带权周转时间:周转时间÷运行时间
等待时间:周转时间-运行时间
需要注意:
如果涉及IO操作的进程,等待时间=周转时间-等待时间-I/O操作时间
平均等待时间:4.75
平均周转时间:8.75
平均带权周转时间:3.5
优点:
缺点:
思想:要求服务时间最短的优先调度
当用于作业调度时:称为SJF
当用于进程调度时:称为短进程优先算法SPF
SJF与SPF是非抢占式调度算法
但是也有其抢占式调度的变种:最短剩余时间优先算法(SRTN)
解:首先分析调度顺序
短作业/进程优先调度算法:每次调度时选择当前已到达且运行时间最短的作业/进程。
调度顺序为:p1->p3->p2->p4
具体计算过程省略:
平均周转时间= (7+4+10+11)/4 = 8
平均带权周转时间=(1+4+2.5+2.75)/4 = 2.56
平均等待时间= (0+3+6+7)/4 = 4
如果采用抢占式短作业优先算法(SRTN):
最短剩余时间优先算法:每当有进程加入就绪队列,就绪队列改变时就需要调度,如果新到达的进程剩余时间比当前运行的进程剩余时间更短,则由新进程抢占处理机,当前运行进程重新回到就绪队列。另外,当一个进程完成时也需要调度。
进程调度顺序分析如下:
平均周转时间=(16+5+1+6)/4 = 7
平均带权周转时间=(2.28+1.25+1+1.5)/4 = 1.50
平均等待时间=(9+1+0+2)/4 = 3
可以发现,采用抢占式短作业优先比非抢占式的短作业优先更加高效。
如果题目没有明确指明,提到的短作业优先默认是非抢占式的。
注意:
1. 在所有的进程同时可以运行的情况下(所有的进程近似同时到达),采用短作业优先调度算法平均等待时间,平均周转次数最短。
2. 如果没有限定条件,抢占式短作业优先算法(SRTN)平均等待时间,平均周转次数最短
优点:
缺点:
思路:在每次调度时先计算各个作业/进程的响应比,选择响应比最高的作业/进程为其服务(响应比:(等待时间+要求服务时间)÷要求服务时间。)
属于非抢占式调度算法,在进程主动放弃CPU(正常结束,异常结束,挂起阻塞)时才需要进行调度。
分析调度顺序:
优点:
前三种算法主要保证公平性,不区分任务的紧急程度对用户的交互性很差
思想:按照进程进入就绪队列的顺序,轮流让进程在CPU中执行一个时间片长度。如果进程在一个时间段内没有完成任务,则剥夺处理机,让这个进程进入就绪队列尾部等待CPU调度。
需要注意:
设时间片大小为2时
时间片为5的情况不在赘述
需要注意:
如果设置的时间片比较大时,会导致每个进程都在一个时间片内完成,此时时间片轮转调度算法和先进先服务算法调度顺序相同。
时间片大小不适合太大,也不适合太小。太大了会增加进程响应的时间,太小了回到是进程切换频繁,系统开销增大
优点:
缺点
思路:每个作业/进程有各自的优先级,调度时选择优先级最高的作业/进程
这个算法既可以用在进程调度,也可以用于作业调度(同时也适用于IO调度)
优先级调度算法可以由抢占式,也可以有非抢占式
非抢占式调度图:
抢占式优先级调度算法:
需要注意:
优点:
缺点:
这种算法是上述几种调度算法的综合
具体思路:
这种算法只适用于进程调度,不适用于作业调度。
此外这种调度算法属于抢占式调度算法
调度分析:
0时刻,此时只有p1进程,p1进程在第一级队列被调度
时刻1,此时p2进程到达,p1进程时间片到,p1进程到第二级队列队尾。p2进程进入第一级队列队尾。CPU处理p2进程
时刻2,此时p2进程时间片到达,进入第二级别队列队尾
此时第一级别队列为空,为第二级别队列分配时间片,此时p1在队头,CPU调度p1进程
时刻4,p1时间片到,执行调度算法,CPU调度p2进程
时刻5,进程p3进程到达,p3进入第一级队列,p2被抢占,p2回到原来队列的队尾,CPU调度p3
之后的调度过程与上面类似,就不在赘述了
最终调度顺序为:
P1(1)->P2(1)->P1(2)->P2(1)->P3(1)->P2(2)->P1(4)->P1(1)
优点:
缺点:
思路:进程被后会对进程进行分类。不同类别的进程优先级不同
队列之间可以采用时间片轮转调度。
eg:如三个队列分配时间50%、40%、10%
每个队列自身可以采用上述的各种不同的调度算法
eg: