【操作系统笔记】OS_CPU调度(08)

李明燮(li_mingxie)
OS
Page content

这一篇整理了操作系统的CPU调度相关的内容。

1.背景

1.1 上下文切换

  • 切换CPU的当前任务, 从一个进程/线程到另一个
  • 保存当前进程/线程在PCB/TCB中的执行上下文(CPU状态)
  • 读取下一个进程/线程的上下文

1.2 CPU调度

  • 从就绪队列中挑选一个进程/线程作为CPU将要运行的下一个进程/线程
  • 调度程序: 挑选进程/线程的内核函数(通过一些调度策略)
  • 需要考虑调度的时机，什么时候进行调度?

1.3 在进程/线程生命周期的什么时候进行调度

图片备用地址
os_08_01

1.4 内核运行调度程序的条件(满足一条即可)

  • 一个进程从运行状态切换到等待状态
  • 一个进程被终结

1.5 不可抢占

  • 调度程序必须等待事件结束

1.6 可以抢占

  • 调度程序在中断被相应后执行
  • 当前的进程从运行切换到就绪, 或者一个进程从等待切换到就绪
  • 当前运行的进程可以被换出

2.调度原则

2.1 调度策略

执行模型 : 程序在CPU突发和IO中交替

  • 每个调度决定都是关于在下一个CPU突发时将哪个工作交给CPU
  • 在时间分片机制下,线程可能在结束当前CPU突发前被迫放弃CPU

2.2 评价指标

调度算法的准则

  • CPU使用率: CPU处于忙状态所占时间的百分比
  • 吞吐量: 在单位时间内完成的进程数量
  • 周转时间: 一个进程从初始化到结束,包括所有等待时间所花费的时间
  • 等待时间: 进程在就绪队列中的总时间
  • 响应时间: 从一个请求被提交到产生第一次相应所花费的总时间

人们通常都需要"更快"的服务
什么是更快?

  • 传输文件时的高带宽
  • 玩游戏时的低延迟
  • 这两个因素是独立的

和水管类比

  • 低延迟: 喝水的时候想要一打开水龙头水就流出来
  • 高带宽: 给游泳池充水时希望从水龙头里同时流出大量的水,并且不介意是否存在延迟

吞吐量vs延迟

对快的评价指标：传输文件时的高带宽；玩游戏时的低延迟(这两点相互独立)；

  • 减少响应时间：及时处理用户的输出并尽快将输出提供给用户；
  • 减少平均响应时间的波动：在交互系统中，可预测性比高差异/低平均更重要；
  • 增加吞吐量：减少开支(操作系统开支/上下文切换)；系统资源的高效利用(CPU，I/O设备)；
  • 减少等待时间：减少每个进程的等待时间。
低延迟调度增加了交互式表现(个人电脑)
  • 如果移动了鼠标，希望屏幕迅速反馈光标的移动。
操作系统保证吞吐量不受影响(服务器)
  • 若想结束长时间的编程，所以操作系统必须不时进行调度，即使存在许多交互任务。
吞吐量是操作系统的计算带宽
响应时间是操作系统的计算延迟

2.3 公平的定义

举例:

  • 保证每个进程占用相同的CPU时间
  • 这公平嘛?如果一个用户比其他用户运行更多的进程怎么办

举例:

  • 保证每个进程都等待相同的时间

公平通常会增加平均响应时间

3.调度算法

  • FCFS：先来先服务，first come，first served；
  • SPN(SJF) SRT: 短进程优先(短作业优先)短剩余时间优先，shortest process next(shortest job first) shortest remaining time；
  • HRRN:最高响应比优先，highest response ratio next；
  • Round Robin,轮循，使用时间切片和抢占来轮流执行任务；
  • Multilevel Feedback Queues,多级反馈队列，多级反馈队列，优先级队列中的轮循；
  • Fair Share Scheduling, 公平共享调度；

3.1 FCFS(先来先服务First come, First Served)

如果进程在执行中阻塞,队列中的下一个会得到CPU

图片备用地址
os_08_02

优点

  • 简单

缺点

  • 平均等待时间波动较大
  • 花费时间少的任务可能排在花费时间长的任务后面
  • 可能导致IO和CPU之间的重叠处理(CPU密集型进程会导致IO设备闲置时,IO密集型进程也在等待)

3.2 SPN(SJF) SRT(短进程优先(短作业优先)短剩余时间优先)[最优平均等待时间]

Shortest Process Next(Shortest Job First) Shortest Remaining Time
SPN(SJF)短进程优先(短作业优先)的意思是 选择下一个最短的进程(短任务优先)，即按照预测的完成时间排序将任务入列；
注意，它可以是抢占的也可以是不抢占的，对于抢占类型的，才是SRT短剩余时间优先。

图片备用地址
os_08_03

图片备用地址
os_08_04

优点

  • 平均周转时间最少；(下图是一个例子，可以发现SRT的进程平均周转时间会短一些)

缺点

  • 可能导致饥饿(连续的短任务流会使场任务饥饿)
  • 短任务可用时的任何场任务的CPU时间都会增加平均等待时间

需要预测未来

  • 怎么预估下一个CPU突发的持续时间
  • 简单的解决: 询问用户
  • 如果用户欺骗就杀死进程
  • 如果不知道怎么办?

3.3 HRRN(最高响应比优先)

Highest Response Ratio Next

  • 在SPN调度的基础上改进(考虑了等待时间，改善饥饿现象)；
  • 不可抢占；
  • 关注进程等待了多长时间；
  • 防止无限期推迟；

R = (w + s) / s (选择R值最高的进程) ，其中
w:waiting time等待时间 s:service time执行时间

3.4 Round Robin(轮循)

  • 在叫做量子(或者时间切片)的离散单元中分配处理器
  • 时间片结束时,切换到下一个准备好的进程

图片备用地址
os_08_05

图片备用地址
os_08_06

图片备用地址
os_08_07

  1. RR花销: 额外的上下文切换
  2. 时间量子太大:
    • 等待时间过长
    • 极限情况退化成FCFS
  3. 时间量子太小:
    • 反应迅速
    • 吞吐量由于大量的上下文切换开销受到影响
  4. 目标:
    • 选择一个合适的时间量子
    • 经验规则: 维持上下文切换开销处于1%以内

3.5 Multilevel Feedback Queues(多级反馈队列)

优先级队列中的轮循

  • 就绪队列被划分成独立的队列: 比如前台(交互),后台(批处理)

  • 每个队列拥有自己的调度策略: 比如前台(RR),后台(FCFS)

  • 调度必须在队列间进行:

    • 固定优先级: 先处理前台,然后处理后台;可能导致饥饿
    • 时间切片: 每个队列都得到一个确定的能够调度其进程的CPU总时间;比如80%使用RR的前台,20%使用FCFS的后台

  • 一个进程可以在不同的队列中移动

  • 例如,n级优先级-优先级调度在所有级别中,RR在每个级别中

    • 时间量子大小随优先级级别增加而增加
    • 如果任务在当前的时间量子中没有完成,则降到下一个优先级

图片备用地址
os_08_08

优点

CPU密集型任务的优先级下降很快;IO密集型任务停留在高优先级

3.6 Fair Share Scheduling(公平共享调度)**

FSS控制用户对系统资源的访问

  • 一些用户组比其他用户组更重要
  • 保证不重要的组无法垄断资源
  • 未使用的资源按照每个组所分配的资源的比例来分配
  • 没有达到资源使用率目标的组获得更高的优先级

3.7 不同调度模型的评价准则

  • 确定性建模：确定一个工作量，然后计算每个算法的表现；
  • 队列模型：用来处理随机工作负载的数学方法；
  • 实现/模拟：建立一个允许算法运行实际数据的系统。

图片备用地址
os_08_09

3.8 总结

实际上这些调度算法和实际的调度算法是有很多区别的(复杂的多)，但是基本的特征是类似的。

  1. FCFS先来先服务
    • 不公平，等待时间较长；
  2. SPN/SRT短进程优先
    • 不公平，但是平均等待时间最小；
    • 需要精确预测计算机时间；
    • 可能导致饥饿；
  3. HRRN最高响应比优先
    • 给予SPN调度的改进；
    • 不可抢占；
  4. Round Robin轮循
    • 公平，但是平均等待时间较长；
  5. MLFQ多级反馈队列
    • 根据CPU和I/O状态动态调整；和SPN类似；
  6. Fair-share scheduling公平共享调度
    • 公平是第一要素。

4.实时调度

  • 定义: 正确性依赖于其时间和功能两方面的一个操作系统
  • 性能指标: 时间约束的及时性;速度和平均性能相对不重要
  • 主要特征: 时间约束的可预测性

分类

  • 强实时系统: 需要在保证时间内完成重要的任务,必须完成

  • 弱实时系统: 要求重要的进程的优先级更高,尽量完成,并非必须

  • 任务(工作单元): 一次计算,一次文件读取,一次信息传递等

  • 属性: 去的进展所需要的资源;定时参数

图片备用地址
os_08_10

硬时限

  • 如果错过了最后期限，可能会发生灾难性或非常严重的后果；
  • 必须验证：在最坏的情况下也能够满足时限吗？
  • 保证确定性；

软时限

  • 理想情况下，时限应该被最大满足。如果有时限没有被满足，那么就相应地降低要求；
  • 尽最大努力去保证；

图片备用地址
os_08_11

单调速率(RM)

  • 最佳静态优先级调度
  • 通过周期安排优先级
  • 周期越短优先级越高
  • 执行周期最短的任务

截止日期最早优先(EDF)

  • 最佳的动态优先级调度
  • Deadline越早优先级越高
  • 执行Deadline最早的任务

5.多处理器调度

多处理器的CPU调度更复杂

  • 多个相同的单处理器组成一个多处理器
  • 优点: 复杂共享

对称多处理器(SMP)

  • 每个处理器运行自己的调度程序
  • 需要在调度程序中同步

图片备用地址
os_08_12

6.优先级反转

图片备用地址
os_08_13

图片备用地址
os_08_14

  • 优先级天花板：“拥有资源”的优先级和“所有可以锁定该资源任务中优先级最高的那个任务”的优先级相同(T3拥有T1的资源，所以它的优先级提升到T1)；
  • 除非当前进程的优先级高于系统中所有被锁定的资源的优先级的上线，否则任务尝试执行临界区的时候会被阻塞；
  • 持有最高优先级上限信号量锁的任务，会继承被该锁所阻塞的任务的优先级。

欢迎大家的意见和交流

email: li_mingxie@163.com