进程调度
一、进程调度的基本概念
进程调度是操作系统的核心功能之一,负责决定哪个进程获得CPU执行权。根据调度层次,进程调度可分为三类:
- 高级调度(作业调度):决定把后备作业调入内存运行
- 中级调度:在虚拟存储器中引入,在内、外存对换区进行进程对换
- 低级调度(进程调度):决定把就绪队列的某进程获得CPU
二、进程调度的分类
1. 按系统类型分类
- 实时系统:FIFO(先进先出)、SJF(最短作业优先)、SRTF(最短剩余时间优先)
- 交互式系统:RR(时间片轮转)、HPF(最高优先级)、多级队列、最短进程优先等
2. 按调度方式分类
- 非抢占式调度:进程一旦获得CPU,将一直运行至完成或主动放弃
- 抢占式调度:高优先级进程可以抢占当前运行进程的CPU
三、常见进程调度算法详解
1. 先来先服务(FCFS)
- 原理:按照进程到达的先后顺序执行
- 特点:非抢占式,实现简单,公平
- 优缺点:
- 优点:公平,实现简单
- 缺点:不利于短作业,平均等待时间较长,可能导致"大作业阻塞小作业"
- 适用场景:批处理系统
2. 时间片轮转(RR)
- 原理:为每个进程分配固定的时间片,执行完成后让出CPU
- 特点:抢占式调度,适用于分时系统
- 优缺点:
- 优点:兼顾长短作业,响应时间较好
- 缺点:平均等待时间较长,上下文切换较费时
- 时间片选择:过长导致响应时间增加,过短增加CPU开销
3. 优先级调度(HPF)
- 原理:在就绪队列中选择优先级最高的进程执行
- 特点:可分为非抢占式和抢占式
- 优缺点:
- 优点:可以优先处理紧急任务
- 缺点:可能导致低优先级进程饥饿
- 动态优先级:可根据等待时间、CPU使用情况等动态调整优先级
4. 短作业优先(SJF)
- 原理:从后备队列中选择估计运行时间最短的作业运行
- 特点:非抢占式(非抢占式SJF)或抢占式(SRTF)
- 优缺点:
- 优点:减少等待时间,提高系统吞吐量
- 缺点:可能导致长作业等待,需要预先估计运行时间
5. 最短剩余时间优先(SRTF)
- 原理:是SJF的抢占式版本,允许新进入且运行时间更短的进程抢占当前运行进程
- 特点:抢占式调度
- 优缺点:
- 优点:确保及时响应用户需求,响应时间更好
- 缺点:需要额外系统开销保存进程状态
6. 高响应比优先调度
- 原理:响应比 = (进程执行时间 + 进程等待时间) / 进程执行时间
- 特点:兼顾长短作业,避免饥饿
- 优缺点:
- 优点:兼顾长短作业,避免饥饿现象
- 缺点:计算响应比开销大
7. 多级反馈队列调度
- 原理:将时间片轮转与优先级调度相结合,把进程按优先级分成不同队列
- 特点:优先级相同,按时间片轮转
- 优缺点:
- 优点:兼顾长短作业,有较好的响应时间,可行性强
- 缺点:实现相对复杂
- 适用场景:各种作业环境
8. CFS(Completely Fair Scheduler)完全公平调度器
- 原理:Linux内核2.6.23引入,每个进程有vruntime,优先级越高vruntime增加越慢
- 特点:
- 使用红黑树作为调度队列数据结构
- 保证高优先级进程得到更多调度,同时低优先级进程也不会饿死
- 多核平台每个core一个调度队列,保证负载均衡
- 优势:无需预先知道进程运行时间,自动适应系统负载
四、Linux进程调度机制
1. Linux调度策略
- SCHED_FIFO:实时调度策略,先到先服务
- SCHED_RR:实时调度策略,时间片轮转
- CFS:默认调度策略,保证公平性
2. CFS调度器特点
- 每个进程有vruntime,优先级越高vruntime增加越慢
- 使用红黑树管理调度队列,左侧节点对应运行时间少的任务
- 保证高优先级进程获得更多CPU时间,同时避免低优先级进程饥饿
- 交互式任务因使用CPU时间少,vruntime小,会优先被调度
五、进程调度算法的优化措施
- 多级反馈队列调度算法:动态调整进程优先级和时间片大小
- 实时调度算法:针对实时系统优化,满足任务时限要求
- 自适应调度算法:根据系统负载和任务特性动态调整调度策略
- 负载均衡:实现CPU负载均衡,避免某些CPU过载
- 公平性调度:确保所有进程公平获得CPU时间
- 预测调度:基于历史数据预测进程行为,提前进行调度决策
- 能耗优化:在移动系统中考虑能耗,优化任务分配
- 混合调度:结合多种调度算法,根据任务类型选择最合适的策略
- 参数动态调整:根据系统性能反馈调整时间片大小、优先级阈值等
- 并行化和分布式处理:在多核和分布式系统中优化调度算法
六、调度算法选择原则
- 响应时间:交互式系统优先考虑时间片轮转、多级反馈队列等
- 系统吞吐量:批处理系统可考虑短作业优先、高响应比优先
- 公平性:需要保证所有进程公平获得CPU资源
- 实时性:实时系统需采用抢占式调度,确保关键任务及时执行
- 资源利用率:平衡CPU利用率和I/O设备利用率
七、总结
进程调度算法的选择需根据系统类型和应用场景进行权衡。在现代操作系统中,CFS等自适应调度算法已成为主流,能够自动平衡系统性能、响应时间和公平性。随着多核处理器和实时系统的发展,进程调度算法也在不断演进,以满足日益复杂的计算需求。
了解各种调度算法的原理、优缺点及适用场景,对于操作系统设计和性能优化具有重要意义。
- 感谢你赐予我前进的力量
赞赏者名单
因为你们的支持让我意识到写文章的价值🙏
本文是原创文章,采用 CC BY-NC-ND 4.0 协议,完整转载请注明来自 软件从业者Hort
评论
匿名评论
隐私政策
你无需删除空行,直接评论以获取最佳展示效果