6.1单核处理器调度
调度的含义
一般情况下我们要运行的线程/进程的数量比CPU核数要多得多. 即使这样, 我们依旧希望可以同时运行, 至少看着像是同时运行.
比如我要跑一个大模型训练, 我也希望等它的同时刷刷视频听听歌啥的, 如果不能同时或者近似同时运行我就只能等训练完再听歌了.
这时候就需要调度了. 调度可以协调请求对资源的使用.
调度器目标
- 降低周转时间
任务第一次进入系统到执行结束的时间
- 降低响应时间
任务第一次进入系统到第一次给用户输出的时间
- 实时性
在任务的截止时间内完成任务
- 公平性
每个任务都应该有机会执行, 不能饿死
- 开销低
调度器是为了优化系统, 而非制造性能bug
- 可扩展
随着任务数量增加, 仍能正常工作
调度的挑战
调度开销VS调度效果
优先级VS公平
能耗VS性能
缺少信息
调度的机制
策略 做什么, 从上层去分析, 解决问题
机制 怎么做, 实现某一策略, 功能
长期调度策略
限制真正被短期调度的进程数量, 管理系统资源利用率.
负责决定哪些进程可以从新生态进入就绪态. 只管大局, 不是谁都可以马上被运行.
短期调度策略
负责和运行状态相关的调度, 如就绪态, 运行态和阻塞态的转移.
中期调度策略
内存空间不足时, 选择挂起一些影响性能的进程, 比如频繁缺页异常, 或者长时间未响应的进程.
优先换出挂起的进程进入硬盘.
负责阻塞态, 挂起阻塞和挂起就绪状态的转移.
Linux调度策略
Linux为不同需求提供了多种调度策略,
公平调度 Complete Fair Scheduler, CFS
- SCHED_ORDER
- SCHED_BATCH
- SCHED_IDLE
实时调度 Real Time Scheduler, RT
- SCHED_FIFO
- SCHED_RR
单核调度策略
经典调度
先到先得(First Come First Served)
优点 简单直观
缺点 平均周转, 响应时间过长. 对IO密集型任务不友好
IO密集型任务主要时间都在阻塞态, 只是偶尔进入到运行态运行一会然后继续阻塞. 明明只要一点时间, 但是却要等很久.
最短任务优先(Shortest Job First)
优点 平均周转时间短
缺点
- 不公平, 可能有任务饿死
- 平均响应时间过长
调度有抢占式和非抢占式, 非抢占式就是等前一个任务完成才执行下一个; 抢占式是每个任务执行一定时间会换下一个任务, 不管有没有完成.
最短完成时间任务优先
大概就是完成时间比较短的可以抢占运行权, 自己运行完后交给下一个任务, 或者被更短的抢占.
优点 平均周转时间短
缺点 会打断正在运行的任务
时间片轮转(Round Robin)
每个任务都分配相同的时间片, 然后在自己的时间片运行, 用完时间片后换下一个任务.
优点 使用轮询, 公平, 平均响应时间短
缺点 牺牲周转时间
优先级调度
就跟人一样, 任务也该分成三六九等. 优先级高的优先调度或者时间片更多.
在前面的调度中都有类似优先级的概念, 比如先到的优先级高, 或者完成时间短的优先级高. 时间片轮转则是完全公平, 优先级都一样.
在操作系统中,
有明确截止时间的实时任务优先级最高
交互式任务分配较高优先级
批处理任务优先级较低
基于多级队列的调度策略
维护多个队列, 跟浏览器一样.
维护多个优先级队列
高优先级的任务优先执行
同优先级内使用时间片轮转调度
多级队列的问题
- 低资源利用率
对于一些共享资源, 可能优先级不同的需要不同的共享资源, 但是整份共享资源只能被一个线程使用.
- 优先级反转
高低优先级都需要独占共享资源时, 如果是低优先级独占独院的时候, 高优先级才过来, 那高优先级任务也得等着.
独占通常是用互斥锁之类的东西实现的, 就算高优先级抢占了CPU, 锁没放开也用不了, 只能进入阻塞态.
解决方案: 优先级继承 高优先级暂时将优先级转移给低优先级任务, 让它快点用完资源.
- 低优先级任务饥饿
多级反馈队列
初始默认都是短任务, 短任务拥有更高优先级
低优先级任务采用更长的时间片
定时将所有任务的优先级提升至最高
公平共享调度
在云服务器中, 如果是共享CPU的话, 那就要多个用户共用一个CPU了. 如果使用时间片轮转, 那任务多的用户占用的时间更长, 但是它们花的钱一样.
每个用户占用的资源应该是成比例的, 而非由任务的数量决定.
使用ticket表示任务的权重
ticket表示每个任务对应的权重, T为ticket的总量.
那么每个问题的占比应该是
彩票调度
这是一种公平共享实现.
调度时, 生成随机数
把任务都排成一排, 然后根据R找到对应的任务就行了. 相当于在一条有很多线段的线上随便找一个点, 这个点所属的线段就是任务.
彩票组织成链表的形式.
权重跟优先级不同, 优先级可能会有饿死的情况, 权重永远不会有饿死情况.
步幅调度
随机很简单, 但是不精确. 随机是伪随机而不是真随机.
步幅调度是确定性版的彩票调度.
- Stride 步幅, 任务执行一次增加的虚拟时间.
这个MaxStride是一个足够大的整数. 设为所有tickets的最小公倍数.
- Pass 累计执行的虚拟时间
每次调度时, 选择并移除运行队列中虚拟时间最小的任务.
调度该任务并让它执行一个时间片
使用该任务的步幅计算调度后的虚拟时间, 然后放回去.
Linux的公平调度器使用的就是类似步幅调度的公平共享调度策略.
实时调度
每一个实时任务都有截止时间(Deadline)
对于软实时, 比如需要每一帧渲染的视频播放, 超过截止时间会导致画质差;
对于硬实时, 如自动驾驶, 要是超过截止时间可能要似人了.
但是对于普通系统来说, 确定性的时延是非常困难的. 程序运行时间也许很稳定, 但是调度太不稳定了.
实时操作系统的特点
- 确定性
完成时间有明确上界.
调度时延可以被准确预测
CPU利用率
只考虑周期任务, 周期的结束就是截止时间.
CPU利用率则是所有任务利用率之和
满足实时调度要求的必要条件是U<=1. 如果没能满足, 不能被实时调度.
速率单调(Rate-Monotonic, RM)策略
静态优先级实时调度, 任务周期越短, 优先级越高, 应先被调度.
这是抢占式的.
最早截止时间优先(Earliest Deadline First, EDF)
动态优先级实时调度, 不需要预知执行时间和任务周期.
每次调度截止时间最近的任务, 在任务可调度的情况下能够实现最优调度.
EDF可调度的必要条件也是U<=1, 如果U>1的话, EDF会造成多数任务都错过截止时间.
调度总结
