1. 调度算法评价指标
1.1 CPU使用率
- CPU“忙碌”的时间占总时间的比例
利用率 = 忙碌时间 / 总时间
1.2系统吞吐量
- 单位时间内完成作业的数量
系统吞吐量 = 总共完成了多少道作业/总共花了多长时间
1.3周转时间
- 是指作业被提交给操作系统开始,到作业完成为止的这段时间间隔
周转时间 = 作业完成时间 - 作业提交时间
平均周转时间 = 各作业周转时间之和 / 作业数
带权周转时间 = 作业周转时间 / 作业实际运行的时间
- 带权周转时间必然 >= 1
- 带权周转时间于周转时间越小越好
平均带权周转时间 = 各作业带权周转时间之和 / 作业数
1.4等待时间
- 进程/作业 等待被服务的时间之和,等待时间越长,用户满意度越低
- 对进程来说,指进程建立后等待被服务的时间之和
- 对作业来说,不仅要考虑建立进程后等待时间,还要加上作业在外存后备队列中等待的时间
- 平均等级时间即各个 进程/作业 等待时间的平均值
1.5响应时间
- 从用户提交请求到首次产生响应所用的时间
2. 选择调度算法的准则
- 公平:确保每个进程获得合理的CPU份额
- 有效:使CPU尽可能地忙碌
- 响应时间:使交互用户的响应时间尽可能短
- 周转时间:使批处理用户等待输出的时间尽可能短
- 吞吐量:使单位时间处理的进程树尽可能多
3. 调度算法
(1) 先来先服务调度算法(FCFS)
规则
- 主要从“公平”的角度考虑
- 按照作业/进程到达的先后顺序进行服务
是否抢占:非抢占式算法
优点:公平、算法实现简单
缺点:对长作业有利,对短作业不利
是否导致饥饿:不会
示例

(2)短作业优先调度算法(SJF)
规则
- 追求最少的平均等待时间,最少的平均周转时间、最少的平均带权周转时间
- 最短的作业/进程优先得到服务
- 即可用于作业调度,又可用于进程调度
是否抢占
- SJF和SPF是非抢占式的算法
- 但也有抢占式的版本——最短剩余时间优先算法(SRTN, Shortest Remaining Time Next)
优点:"最短的"平均等待时间、平均周转时间
缺点:不公平。对短作业有利,对长作业不利,可能会产生饥饿现象
是否考虑等待时间&运行时间:只考虑运行时间
是否导致饥饿:会。如果一直得不到服务,则称为”饿死“
示例
- 非抢占式

- 抢占式

(3)高响应比优先调度算法(HRRN)
规则
- 要综合考虑作业/进程的等待时间和要求服务的时间
- 每次调度时先计算各个作业/进程的响应比,选择响应比最高的作业/进程为其服务
响应比 = (等待时间 + 要求服务时间) / 要求服务时间
- 既可用于作业调度,也可用于进程调度
是否抢占:非抢占式算法
优点
- 综合考虑等待时间和运行时间(要求服务时间)
- 等待时间相同时,要求服务短的优先(SJF的优点)
- 要求服务时间相同时,等待时间长的优先(FCFS优点)
是否考虑等待时间&运行时间:两个都考虑
是否导致饥饿
- 不会
- 对于长作业来说,随着等待时间越来越久,其相应比也会越来越大,从而避免长作业饥饿问题
示例

(4)时间片轮转调度算法(RR)
规则
- 公平地、轮流的为各个进程服务,让每个进程在一定时间内都可以得到响应
- 按照各进程达到就绪队列的顺序,轮流让每个进程执行一个时间片
- 若进程未在一个时间片内执行完,则剥夺处理机,将进程重新放到就绪队列队尾重新排队
是否抢占
- 抢占式算法
- 由时钟装置发出时钟中断来通知CPU时间片已到
优点
- 公平
- 响应快,适用于分时操作系统
缺点
- 由于高频率的进程切换,因此有一定开销
- 不区分任务的紧急程度
是否导致饥饿:不会
补充
- 如果时间片太大,则退化为先来先服务调度算法,并且会增大进程响应时间
- 进程的切换是有时间代价的,时间片也不能太小
示例

(5)优先级调度算法
规则
- 需要根据任务的紧急程度来决定处理的顺序
- 每个作业/进程有各自的优先级,调度时选择优先级最高的作业/进程
- 即可用于作业调度,也可用于进程调度
是否抢占:抢占式、非抢占式都有,注意区别
优点
- 用优先级区分紧急程度、重要程度,适用于实时操作系统
- 可灵活地调整对各种作业/进程的偏好程度
缺点
- 若源源不断的有高优先级的进程到来,则可能导致饥饿
是否导致饥饿:会
补充
- 静态调整优先级
- 动态调整优先级
示例
- 非抢占式

- 抢占式

(6)多级反馈队列调度算法
规则
- 对其他调度算法的折中平衡,用于进程调度
- 1、设置多级就绪队列,各级队列优先级从高到低,时间片大小从小到大
- 2、新进程到达时先进入第1级队列,按FCFS原则排队等待被分配时间片,若用完时间片还没结束,则进程进入下一级队列队尾。如果此时已经是在最下级的队列,则重新放回该队列队尾。
- 3、只有第k级队列为空时,才会为k+1级队头得进程分配时间片
是否抢占
- 抢占式算法
- 在K级队列的进程运行过程中,若更上级的队列(1~ k-1级)中进入一个新进程,则由于新进程处于优先级更高的队列中,因此抢占处理机,原来运行的进程放回k级队列队尾
优点
- 对各个类型进程相对公平(FCFS优点)
- 每个新到达的进程都可以很快得到相应(RR优点)
- 短进程只用较少的时间就可以完成(SPF优点)
- 不必实现估计进程的运行时间(避免用户作假)
- 可灵活的调整对各类进程的偏好程度
缺点:一般不说缺点
是否导致饥饿:会
示例
