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优点）
- 不必实现估计进程的运行时间（避免用户作假）
- 可灵活的调整对各类进程的偏好程度
缺点：一般不说缺点
是否导致饥饿：会
示例
