typora/note/操作系统/进程调度策略.md

104 lines
4.0 KiB
Markdown
Raw Permalink Normal View History

2024-12-11 21:48:55 -05:00
## 一、调度基本思想
> 前提假设:操作系统可以看到程序执行的未来
>
> 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的队列比自己多的就窃取一部分过来迁移一部分任务