08-调度算法
一、背景
1. CPU调度
上下文切换
- 切换CPU的当前任务，从一个进程/线程到另一个
- 保存当前进程/线程在PCB/TCB中的执行上下文（CPU状态）
- 读取下一个进程/线程的上下文
CPU调度
- 从就绪队列中挑选一个进程/线程作为CPU将要运行的下一个进程/线程
- 调度程序：挑选进程/线程的内核函数（通过一些调度策略）
- 什么时候进程调度？
内核运行调度程序的条件（满足一条即可）
- 一个进程从运行状态切换到等待状态
- 一个进程被终结了
不可抢占
- 调度程序必须等待事件结束
可以抢占
- 调度程序在中断被响应后执行
- 当前的进程从运行切换到就绪，或者一个进程从等待切换到就绪
- 当前运行的进程可以被换出
二、调度准则
执行模型：程序在CPU突发和I/O中交替
- 每个调度决定都是关于在下一个CPU突发时将哪个进程交给CPU
- 在时间片机制下，线程可能在结束当前CPU突发前被迫放弃CPU
1. 调度策略
CPU使用率
CPU处于忙状态锁占时间的百分比
吞吐量
在单位时间内完成的进程数量
周转时间
一个进程从初始化到结束，包括所有等待时间所花费的时间
等待时间
进程在就绪队列中的总时间
响应时间
从一个请求被提交到产生第一次响应所花费的总时间
2. 程序执行模型
3. 比较调度算法的准则
人们通常都需要更快的服务
什么是更快？
- 传输文件时的高带宽
- 玩游戏时的低延迟
- 这两个因素是独立的
和水管类比 - 低延迟：喝水的时候想要一打开水龙头就流出水
- 高带宽：给游泳池充水时希望水龙头里同时流出大量的水，并且不介意是否存在延迟
4. 吞吐量VS延迟
减少响应时间
及时处理用户的输出并且尽快将输出提供给用户
减少平均响应时间的波动
在交互系统中，可预测性比高差异低平均更重要
增加吞吐量-两个方面
减少开销（操作系统开销，上下文切换）
系统资源的高效利用（CPU,I/O设备）
减少等待时间
减少每个进程的等待时间
低延迟调度增加了交互式表现
如果移动了鼠标，但是屏幕中的光标却没动，我可能会重启电脑
但是操作系统需要保证吞吐量不受影响
我想要结束长时间的编程，所以操作系统必须不时进行调度，及时存在许多交互任务
吞吐量是操作几桶的计算带宽
响应时间是操作系统的计算延迟
5. 公平的目标
举例：
保证每个进程占用相同的CPU时间
这公平么？如果一个用户比其他用户运行更多的进程怎么办？
举例：
保证每个进程都等待相同的时间
公平通常或增加平均响应时间
三、调度算法
FCFS(first come, first served.先来先服务)
有一个先进先出队列存放等到执行的进程，如果当前执行进程阻塞，则队列中的下一个进程会得到CPU
优点：
简单
缺点：
- 平均等待时间波动较大
- 花费时间少的任务可能排在花费时间长的任务后面
- 可能导致I/O和CPU的重叠处理，CPU密集型进程会导致I/O设备闲置时，I/O密集型进程也在等待
SPN（SJF) SRT(Shortest Process Next(Shortest Job First) Shortest Remaining Time 短进程优先(短作业优先)短剩余时间优先)
选择下一个最短的进程（短任务优先）
按照预测的完成时间来将任务入队
可以是可抢占的或者不可抢占的
- 可抢占：又叫Shortest-Remaining-Time(SRT)最短剩余时间
优点：
具有最优的平均等待时间
缺点：
可能导致饥饿
- 连续的短任务流会使长任务饥饿
- 短任务可用的任何长任务的CPU时间都会增加平均等待时间
需要预知未来 - 怎么预估下一个CPU突发的持续时间
- 简单的解决办法：询问用户
- 如果用户欺骗就杀死进程
- 如果用户不知道怎么办？采用模型进行预估-这块没理解
HRRN(Highest Response Ratio Next 最高响应比优先)
- 在SPN调度的基础上改进
- 不可抢占
- 关注进程等待了多长时间
- 防止无限期推迟
R=(w+s)/s
w: waiting time 等待时间
s: service time 执行时间
选择R值最高的程序
Round Robin(轮询)
- 在叫作量子（或时间切片）的离散单元中分配处理器
- 时间片结束后，切换到下一个准备好的进程
时间花销：额外的上下文切换
时间量子太大
- 等待时间过长
- 极限情况退化成FCFS
时间量子太小 - 反应迅速，上下文切换开销较大
目标 - 选择一个合适的时间量子
- 经验规则：维持上下文切换开销处于1%以内 linux系统当前设置的时间切片为百分之一秒即10毫秒
Multilevel FeedBack Queues(多级反馈队列)
- 就绪队列被划分成独立的队列：例如 前台（交互），后台（批处理）
- 每个队列拥有自己的调度策略：前台（RR,实时）后台（FCFS 先进先执行）
- 调度必须在队列间进行
- 固定优先级 先处理前台，然后处理后台，可能导致饥饿
- 时间切片 每个队列都得到一个确定的能够调度其进程的CPU总时间，例如80%给使用RR的前台，20%给使用FCFS的后台
一个继承可以在不同的队列中移动
例如：n级优先级-优先级调度在所有几倍中，RR在每个级别中
时间量子大小随优先级别增加而增加
如果任务在当前的时间量子中没有完成，则降到下一个优先级
优点：
CPU密集型任务的优先级下降很快
I/O密集型任务停留在高优先级
Fair Share Scheduling(公平共享调度)
FSS控制用户对系统资源的访问
- 一些用户组相比其他用户组更重要
- 保证不重要的组无法垄断资源
- 未使用的资源按照每个组所分配的资源的比例来分配
- 没有达到资源使用率目标的组获得更高的优先级
确定性建模
确定一个工作量，然后计算每个算法的表现
队列模型
用来处理随机工作负载的数学方法
实现/模拟
- 建立一个允许算法运行实际数据的系统
- 最灵活/具有一般性
小结
FCFS 先来先服务
不公平，平均等待时间较差
SPN/SRT 短进程优先
不公平，但是平均等待时间最小
需要精确预测运行时间
可能导致饥饿
HRRN 最高响应比优先
基于SPN调度改进
不可抢占
Round Robin 轮询
公平，但是平均等待时间较差
MLFQ 多级反馈队列
和SPN类似
Fair-share scheduling 公平共享调度
公平是第一要素
四、实时调度
实时系统
定义：正确性依赖于其时间和功能两方面的一种操作系统
性能指标：
时间约束的及时性（deadlines）
速度和平均性能相对不重要
主要特性：
时间约束的可预测性
强实时系统：需要在保证的时间内完成重要的任务，必须完成
弱实时系统：要求重要的进程优先级更高，尽量完成，并非必须
任务（工作单元）
- 一次计算，一次文件读取，一次信息传递等等
属性 - 取得进展所需要的资源
- 定时参数
任务：一系列相似的任务
周期任务
任务有规律地重复
周期p = inter-release time(0<p)
执行时间 e=最大执行时间（0<e<p）
使用率 U= e/p
硬时限
- 如果过了最后期限，可能会发生灾难性或非常严重的后果
- 必须验证：在最坏的情况下也能够满足时限吗？
- 保证确定性
软时限
- 理想情况下，时限应该被最大满足。如果有时限没有被满足，那么就相应地降低要求
- 尽最大努力去保证
可调度性
表示一个实时系统是否能够满足deadline要求
- 决定实时任务执行的顺序
- 静态优先级调度
- 动态优先级调度
速率单调（RM）
- 最佳静态优先级调度
- 通过周期安排优先级
- 周期越短优先级越高
- 执行周期最短的任务
截止日期最早优先（EDF）
- 最佳的动态优先级调度
- Deadline越早优先级越高
- 执行Deadline最早的任务