4.0 KiB
4.0 KiB
一、调度基本思想
前提假设：操作系统可以看到程序执行的未来
- 知道进程执行时间
- 了解进程执行过程
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，则会降低优先级
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的队列，比自己多的就窃取一部分过来，迁移一部分任务