处理机调度

相关： os 0923 week3

概念

cpu资源的时分复用

• 进程切换： cpu资源的当前占用者切换
  • 保存当前进程在pcb中的执行上下文（cpu状态）
  • 恢复下一个进程的执行上下文
• 处理机调度
  • 从就绪队列中挑选下一个占用cpu运行的进程
  • 多处理机：从多个可用cpu中挑选就绪进程可使用的cpu资源
• 调度程序： 挑选就绪进程的内核函数
  • 要解决的问题
    • 调度策略：依据什么来选择进程/线程？
    • 调度时机：什么时候进行调度？

调度时机

五状态模型

• 条件
  • 进程从运行状态切换到等待状态
  • 进程退出了，被终结，cpu资源空出来
• 非抢占系统
  • 当前进程主动放弃cpu
• 可抢占系统
  • 中断请求服务/系统调用被服务例程相应完成时
  • 当前进程被抢占
    • 进程时间片用完 运行到就绪状态变化时，
    • 进程从等待切换到就绪，更急迫占用cpu

调度准则

调度策略

确定如何从就绪队列中选择下一个执行进程

• 要解决的问题
  • 挑选就绪队列中的哪一个进程？
  • 通过什么样的准则来选择？
• 调度算法
  • 在调度程序中实现的调度策略
• 比较调度算法的准则具体
  • 哪个策略/算法更好？

处理机资源的使用模式

• 进程在cpu计算和io操作间交替 ，两种状态
  • 每次调度决定在下一个cpu计算时将哪个工作交给cpu;在时间片机制下，进程可能在结束当前cpu计算前被迫放弃cpu,不利，选择合理时间片

比较调度算法的准则

目标，指标，度量好与坏

• 系统的角度
  • cpu使用率：cpu处于忙状态的时间百分比
  • 吞吐量：单位时间内完成的进程数量
• 用户的角度
  • 周转时间：进程从初始化到结束（包括等待）的总时间，提交作业到算出结果
  • 等待时间：进程在就绪队列中的总时间
  • 响应时间：提交请求到产生响应所花费的总时间。交互式

吞吐量与延迟

• 调度算法的要求
  • 希望 更快的服务
• 什么是快？
  • 不同情况不一样。带宽高 传输文件，对应 调度算法 单位时间 执行更多进程
  • 低延迟 ，玩游戏 。
  • 这两个因素是独立的。
• 与水管的类比
  • 低延迟： 喝水 的时候 想要一打开水龙头 水就流出来，提出请求到有水的时间
  • 高带宽：不关心开始的时间。不介意延迟。给游泳池充水时希望水龙头里同时流出大量的水， 最后灌满水的时间。

处理机调度策略的响应时间目标

• 减少响应时间
  • 及时处理用户的输入请求，尽快将输出反馈给用户
• 减少平均响应时间波动 抖动小
  • 在交互系统中，可预测性比高差异性低平均更重要，用户体验不稳定 一会儿高一会儿低
• 低延迟调度改善了用户的交互体验
  • 若移动鼠标时，屏幕中的光标没动，（没有响应）用户可能会重启电脑
• 响应时间时操作系统的计算延迟

处理机调度策略的吞吐量目标

• 增加吞吐量
  • 减少开销（操作系统开销、上下文切换）
  • 提高系统资源的利用率（cpu、i/o设备）
• 减少等待时间
  • 减少每个进程的等待时间（一石二鸟）
• 操作系统需要保证吞吐量不受用户交互的影响
  • os必须不时进行调度，即使存在许多交互任务
• 吞吐量是操作系统的计算带宽

处理机调度的公平性目标

• 公平的定义
  • 保证每个进程占用相同的cpu时间
  • 保证每个进程的等待时间相同
• 公平通常会增加平均响应时间 一定的开销来保证公平。

调度算法

先来先服务

FCFS :First Come,First Served

• 依据进程进入就绪状态的先后顺序排列
  • 进程进入等待或结束状态时，就绪队列的下一个进程占用cpu

特征

• 优点
  • 简单 排队没有变化
• 缺点
  • 平均等待时间波动较大
    • 短进程可能排在长进程后面，排的位置有影响
  • i/o资源和cpu资源利用率较低
    • cpu密集型进程会导致i/o设备闲置时，i/o密集型进程也等待。

短进程优先

SPN;SJF;SRT作业执行时间长短；考虑到进程的特征：执行时间 来排队

• 选择就绪队列中执行时间最短进程占用cpu进入运行状态
  • 按预期的时间

特征

• 优点：
  • 最优平均周转时间
  • 由短到长排队
• 缺点：
  • 可能导饥饿
  • 连续的短进程流会使长进程无法获得cpu资源
• 需要预知未来 如何预知下一个cpu计算的持续时间？ 简单的解决方法：询问用户 或者过去预知未来

最高响应比优先算法

前面只考虑执行时间。 避免长进程等待时间长。

• 选择就绪队列中响应比R值最高的进程
  • r=(w+s)/w w:等待时间；s:执行时间
• 在短进程优先算法的基础上改进
• 不可抢占
• 关注进程的等待时间
• 防止无限期推迟 等待时间越长 优先级越高 然后最高可以得到cpu

---

以上三种 ，关于 就绪队列 排序的算法 根据 到达时间 执行时间 等待时间 来排序

时间片轮转

Round Robin

• 时间片
  • 分配处理机资源的基本时间单元。
• 算法思路
  • 时间片结束时，按FCFS算法切换到下一个就绪进程
  • 每隔(n-1)个时间片进程执行一个时间片q todo
  • 算等待时间。每一轮
• RR算法开销
  • 额外的上下文切换 强行切换，时间一到
• 时间片太大
  • 等待时间过长
  • 极端情况退化成FCFS，大到任何一个进程可以在一个时间片内完成。先来先服务。
• 时间片太小
  • 反应迅速，大量时间用来切换 执行只占其中 一半 ，产生大量上下文切换
  • 大量上下文切换开销影响到系统吞吐量
• 时间片选择目标
  • 选择一个合适的时间片长度 10ms
  • 经验规则：维持上下文切换开销处于1%以内

多级反馈队列算法

MFQ 就绪多列 多个子队列 一个算法无法满足用户的所有需求。组合算法。

• 就绪队列被划分为多个独立的子队列
  • 如前台（交互 rr） 、后台（批处理fcfs）
• 每个队列拥有自己的调度策略
• 队列间的调度
  • 固定 先处理前台，再处理后 台，可能导致饥饿
  • 时间片轮转
    • 每个队列都得到一个确定的能够调度其进程的cpu总时间，前台占80 ，后台占20

mlfq 进程可再不同队列间移动的多级队列 - 时间片大小随优先级级别增加而增加 - 如进程在当前的时间片没有完成，降到下一个优先级

• 特征
  • cpu密集型进程优先级下降很快
  • i/o密集型进程停留在高优先级， 每一次算的时间短 时间片没有用完

公平共享调度算法 fair share scheduling

按照占用资源情况

控制 用户对系统资源的访问 一些用户组比其他用户组更重要 保证不重要的组无法垄断资源 没有使用的资源按比例分配 没有达到资源使用率目标的组获得更高的优先级

算法总结

• fcfs
  • 简单，但是不公平，平均等待时间较差，变动大
• 短进程
  • 不公平，但 平均周转时间最小
  • 需要精确预测计算时间 未来
  • 可能会导致饥饿
• 最高响应比优先算法
  • 基于spn调度 考虑等待时间
  • 不可抢占
• rr
  • 公平，平均等待时间较差
  • 响应好
• mlfq
  • 多种算法的集成 综合
• fss
  • 公平是第一要素