104 lines
4.0 KiB
Markdown
104 lines
4.0 KiB
Markdown
## 一、调度基本思想
|
||
|
||
> 前提假设：操作系统可以看到程序执行的未来
|
||
>
|
||
> 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的队列，比自己多的就窃取一部分过来，迁移一部分任务 |