比较调度算法的准则
CPU 使用率: CPU 处于忙状态的时间百分比
吞吐量: 单位时间内完成的进程数量
周转时间: 进程从初始化到结束 (包括等待) 的总时间
就绪等待时间: 进程在就绪队列中的总时间
响应时间: 从提交请求到产生响应所花费的总时间
决策模式
决策模式说明选择函数在执行的瞬间的处理方式, 通常分为以下两类:
非抢占: 一旦进入运行状态, 就不会终止直到运行结束.
抢占: 当前正在运行的进程可以被打断, 并转移到就绪态. 一个调度算法是否能抢占, 对进程的顺序有着极大的影响.
一, 先来先服务(FCFS)
先来先服务是最简单的策略, 也称为先进先出 FIFO. 首先它是一个非抢占的. 如字面意思, 它根据进程到达时间决定先运行哪一个进程.
FCFS 的周转时间
示例: 3 个进程, 计算时间分别为 12,3,3
FCFS 优点
简单
缺点
平均等待时间波动较大: 短进程可能排在长进程后面
I/O 资源和 CPU 资源的利用率较低: CPU 密集型进程会导致 I/O 设备闲置时, I/O 密集型进程也等待.
二, 短进程优先算法(SPN)
选择就绪队列中执行时间最短进程占用 CPU 进入运行状态, 就绪队列按预期的执行时间来排序, 短进程优先算法具有最优平均周转时间.
SPN 算法中一组进程的平均周转时间
而修改进程执行顺序不能减少平均等待时间
短进程优先算法缺点:
可能导致饥饿: 连续的短进程流会使长进程无法获得 CPU 资源
需要预知下一个 CPU 计算的持续时间, 简单的解决办法 - 询问用户, 用户欺骗就杀死相应进程, 用户不知道到, 则...
短进程优先算法的执行时间预估: 用历史的执行时间来预估未来的执行时间.
三, 最高响应比优先算法(HRRN)
选择就绪队列中响应比 R 值最高的进程
特点
在短进程优先算法的基础上改进
不可抢占
关注进程的等待时间
防止无限期推迟
四, 时间片轮转算法(RR, Round-Robin)
1. 时间片: 分配处理及资源的基本时间单元
2. 算法思路
时间片结束时, 按 FCFS 算法切换到下一个就绪进程
每隔 (n-1) 个时间片进程执行一个时间片 q
3. 时间片为 20 的 RR 算法示例
4. 时间片轮换算法中的时间片长度
RR 算法开销, 额外的上下文切换
时间片太长
等待时间过长
极限情况退化为 FCFS
时间片太小
反映迅速, 但产生大量的上下文切换
大量的上下文切换开销影响到系统吞吐量
时间片长度选择目标
选择一个合适的时间片长度
经验规则: 维持上下文切换开销处于 1% 以内
五, 多级队列调度算法(MQ)
1. 就绪队列被划分为多个独立的子队列
如: 前台(交互), 后台(批处理)
2. 每个队列拥有自己的调度策略
如: 前台 - RR, 后台 - FCFS
3. 队列间的调度
固定优先级
先处理前台, 后处理后台
可能导致饥饿
2. 时间片轮换
每个队列得到一个确定的能够调度其进程的 CPU 总时间
如: 80%CPU 时间用于前台, 20%CPU 时间用于后台
六, 多级反馈队列算法(MLFQ)
进程可在不同队列中移动的多级队列算法
时间片大小随优先级级别增加而增加
如进程在当前的时间片没有完成, 则降到下一个优先级
MLFQ 算法的特征:
CPU 密集型进程的优先级下降很快
I/O 密集型进程停留在高优先级
来源: http://www.bubuko.com/infodetail-3375267.html