## 一、调度基本思想

> 前提假设：操作系统可以看到程序执行的未来
>
> 1. 知道进程执行时间
> 2. 了解进程执行过程

### 1. 先进先出

- First In First Out
- 先到先服务调度方式 First Come First Served
- 缺点：耗时较少的进程被排在耗时较长的进程的后边，造成进程执行效率不高

### 2. 最短作业时间优先

- Shortest Jon First
- 执行时间短的任务先执行
- 需要知道任务执行时间且短的任务先到达

### 3. 最短完成时间优先

- Short Time to Completion FIrst
- 抢占式最短作业时间优先  Preemptive Shortest Job First
- 有新工作加入时，会先确定剩余工作和新工作中谁的时间短
- 调度执行时间短的那个工作

### 4. 轮转

- Round Robin
- 在一个时间片内运行一个工作，时间片结束后运行任务队列中的下一个工作，知道任务队列全部结束
- 时间片长度是时钟周期的整数倍

### 5. 小结

- 最短作业和最短完成时间可以做到最快调度（进程的平均调度时间短），但是进程的响应时间会变长
- 轮转可以提高进程的响应时间，但是平均每个进程的调度时间会变长



## 二、单处理器调度方法

### 1. 多级反馈队列

- Multi-level Feedback Queue
- 从历史经验预测未来
- 在进程执行过程中学习其行为，进而预测未来的行为

#### 1.1 基本规则

- MLFQ有许多队列，每个队列的优先级范围不同
- 总是先执行优先级较高的队列中的任务
- 同一个队列中的任务如果优先级相同，采用轮转的方式调度执行
- MLFQ会动态的调整每个任务的优先级
  - 如果进程使用IO操作，可以理解为是交互行为，需要提高响应时间，从而调高该任务的优先级
  - 如果进程一直都是CPU操作，长时间的占用CPU，则会降低优先级

<img src="http://blog-heysq-1255479807.cos.ap-beijing.myqcloud.com/blog/note/image-20230720153314626.png" alt="image-20230720153314626" style="zoom:50%;" />

> C和D的优先级最低，如果A和B一直调度执行，则C和D一直不会被执行

#### 1.2 如何改变优先级

- 进程开始执行时放入最高优先级
- 程序使用完一个优先级队列中的一个时间分片配额（多个时间分片）时，就会降低一个优先级
  - 防止进程在使用99%时间分片时调用IO操作，保留优先级，从而造成进程一直在高优先级执行
  - 其他低优先级得不到有效调度
- 进程在一个时间分片内主动释放CPU，则优先级保持不变
- 每隔一定时间将所有任务都加到最高优先级队列
  - 确保CPU交互密集且长时间运行的任务不会被饿死
  - 确保CPU密集变成IO交互的可以快速执行
- 不同优先级队列的时间片配额不相同
  - 高优先级队列，时间片配额短，确保交互行为快速响应
  - 低优先级队列，时间片分配额长，CPU密集进程也能长时间执行



### 2 比例份额

- 有时也称为公平份额
- 确保每个工作获得一定比例的CPU时间
- 采用随机抽选的方式
- 工作执行时间越长，获得CPU时间片比例越公平

## 三、多队列调度

### 1.单队列多处理器调度

- Single Queue Multiprocessors Scheduling SQMS
- 一个队列存储任务
- 多个处理器加锁从队列中获取执行任务
- 主要问题：
  - 为了确保多处理器取任务不会冲虚，需要加锁，加锁性能损耗，争抢锁的成本，CPU越多损耗越高
  - 缓存亲和性较差，多个工作轮流在不同的处理器上执行，缓存数据每次都要重新获取

### 2.多队列多处理器调度

- Multi-Queue Multiprocessors Scheduling MQMS
- 包含多个队列，每个队列可以使用不同的调度算法
- 解决了加锁同步的问题
- 主要问题：
  - 负载不均衡，造成一个CPU空闲，其他的可能满载
- 解决负载不均衡
  - 迁移任务到其他CPU
  - work stealing 工作窃取机制，空闲的CPU主动监控其他CPU的队列，比自己多的就窃取一部分过来，迁移一部分任务