7.3 进程调度
进程调度是操作系统的核心功能之一，负责选择下一个要运行的进程/线程，分配CPU时间。调度算法的好坏直接影响系统的性能和用户体验。
调度的基本概念
什么是调度
在多任务操作系统中，同时运行的进程/线程数量通常多于CPU核心数量，操作系统需要决定哪个进程/线程获得CPU的使用权，这个决策过程就是调度。
调度的目标
不同的系统有不同的调度目标：
- 高CPU利用率：让CPU尽可能保持忙碌，减少空闲时间
- 高吞吐量：单位时间内完成的任务数量尽可能多
- 短响应时间：交互式任务的响应时间尽可能短，用户体验好
- 短周转时间：任务从提交到完成的时间尽可能短
- 公平性：每个进程/线程都能获得公平的CPU时间，避免饥饿
- 实时性：实时任务能在规定的时间内完成
这些目标之间往往是冲突的，比如要提高吞吐量可能会牺牲响应时间，调度算法需要在多个目标之间权衡。
调度的层次
调度分为三个层次：
- 长程调度（作业调度）：选择哪些作业可以进入系统，分配资源，创建进程，现在的操作系统通常没有长程调度
- 中程调度（交换调度）：负责进程在内存和磁盘之间的换入换出，平衡内存使用
- 短程调度（进程调度）：选择下一个要运行的进程/线程，是最频繁的调度，我们通常说的调度就是指短程调度
抢占式调度 vs 非抢占式调度
- 非抢占式调度：进程一旦获得CPU就一直运行，直到主动让出CPU（阻塞或者执行完成），实现简单，但是响应时间长，不适合交互式系统
- 抢占式调度：操作系统可以强制剥夺当前进程的CPU使用权，分配给其他进程，响应时间短，用户体验好，是现在主流操作系统的调度方式
- 抢占时机：时间片用完、更高优先级进程就绪、系统调用返回、中断返回时
常见的调度算法
1. 先来先服务（FCFS, First Come First Served）
- 原理：按照进程到达就绪队列的顺序调度，先到的先运行
- 优点：实现简单，公平
- 缺点：平均周转时间长，短任务可能会被前面的长任务阻塞，出现“护航效应“，不适合交互式系统
- 适用场景：批处理系统，任务执行时间比较平均的场景
2. 短作业优先（SJF, Shortest Job First）
- 原理：优先选择估计运行时间最短的进程运行
- 优点：平均周转时间最短，吞吐量高
- 缺点：
- 需要提前知道进程的运行时间，实际中很难估计
- 长作业可能会一直被短作业抢占，出现饥饿现象，永远得不到运行
- 是非抢占式的，不适合交互式系统
- 抢占式版本：最短剩余时间优先（SRTF），新的短作业到达时，如果剩余运行时间比当前运行的进程短，就抢占CPU，性能更好，但复杂度更高
3. 时间片轮转（RR, Round Robin）
- 原理：每个进程分配一个固定大小的时间片，进程运行完时间片就被抢占，放到就绪队列末尾，轮流执行
- 时间片大小的选择：
- 时间片太大：退化为FCFS算法，响应时间长
- 时间片太小：上下文切换太频繁，浪费CPU时间，吞吐量下降
- 合适的时间片：通常是10-100ms，让大部分交互式任务能在一个时间片内完成
- 优点：公平，响应时间短，适合交互式系统，是分时系统的经典调度算法
- 缺点：平均周转时间比SJF长，上下文切换开销大
4. 优先级调度（Priority Scheduling）
- 原理：每个进程有一个优先级，优先选择优先级最高的进程运行
- 优先级分类：
- 静态优先级：进程创建时确定优先级，运行过程中不变
- 动态优先级：运行过程中调整优先级，比如等待时间长的进程优先级升高，运行时间长的进程优先级降低，避免饥饿
- 抢占式版本：高优先级进程到达时可以抢占低优先级进程的CPU
- 优点：可以给重要的任务分配高优先级，保证关键任务的响应时间
- 缺点：低优先级进程可能会一直得不到运行，出现饥饿，需要动态调整优先级或者老化机制解决
- 适用场景：需要区分任务优先级的场景，比如实时系统、服务器系统
5. 多级反馈队列（Multilevel Feedback Queue）
- 原理：结合了RR和优先级调度的优点，是现在最通用的调度算法
- 实现方式：
- 设置多个就绪队列，每个队列有不同的优先级，最高优先级队列时间片最短，越低的队列时间片越长
- 新进程首先进入最高优先级队列，按RR调度
- 如果进程在时间片内完成，就退出系统
- 如果时间片用完还没完成，就降到下一级低优先级队列
- 低优先级队列的进程如果等待时间太长，可以升到高优先级队列（老化机制，避免饥饿）
- 调度时优先选择高优先级队列中的进程，只有高优先级队列为空时才调度低优先级队列
- 优点：
- 兼顾短作业和长作业，短作业在高优先级队列很快完成，长作业在低队列慢慢运行
- 响应时间短，适合交互式任务
- 不需要提前知道进程的运行时间，适应性强
- 适用场景：通用操作系统，比如Windows、Linux、macOS的调度算法都是基于多级反馈队列改进的
6. 实时调度算法
实时系统对任务的完成时间有严格要求，调度算法需要保证任务在截止时间前完成：
- 速率单调调度（RMS）：静态优先级调度，周期越短优先级越高，适合硬实时系统
- 最早截止时间优先（EDF）：动态优先级调度，截止时间越早优先级越高，利用率更高
Linux的调度机制
Linux的调度器经历了几次演变：
- O(1)调度器：Linux 2.6内核使用，调度时间复杂度O(1)，适合大服务器，但对交互式任务支持不好
- CFS调度器（完全公平调度器）：Linux 2.6.23之后使用，是现在的默认调度器
CFS调度器的原理
CFS的核心思想是“完全公平“，给每个进程公平的CPU时间：
- 每个进程有一个虚拟运行时间（vruntime），进程运行的时间越长，vruntime越大
- 调度器总是选择vruntime最小的进程运行
- 优先级高的进程运行相同的物理时间，vruntime增长更慢，相当于获得更多的CPU时间
- 用红黑树来管理就绪队列，找到最小vruntime的进程效率很高
- 自动适应不同的负载，根据进程数量动态调整时间片大小
- 支持组调度、带宽控制等高级特性
Linux的进程优先级
- 实时进程优先级：0-99，数值越大优先级越高，用实时调度算法（FIFO、RR）
- 普通进程优先级：100-139，对应nice值-20到+19，nice值越低优先级越高，默认nice值是0
Windows的调度机制
Windows也是基于多级反馈队列的抢占式调度：
- 共32个优先级，0-31
- 0级：系统使用，用于零页线程
- 1-15级：普通优先级，动态调整
- 16-31级：实时优先级，固定不变
- 优先级提升：前台窗口进程、IO完成的进程、等待事件的进程会提升优先级
- 时间片大小：根据版本不同，时间片通常是20ms左右，前台进程的时间片更长
调度的性能指标
衡量调度算法性能的常用指标：
- CPU利用率：CPU处于忙状态的时间比例，越高越好
- 吞吐量：单位时间内完成的进程数量，越高越好
- 周转时间：进程从提交到完成的总时间，越短越好
- 周转时间 = 完成时间 - 提交时间
- 带权周转时间 = 周转时间 / 服务时间，衡量单位服务时间的等待时间
- 等待时间：进程在就绪队列中等待的总时间，越短越好
- 响应时间：从用户提交请求到系统第一次响应的时间，对于交互式系统越短越好
调度优化建议
对于应用开发者，我们可以通过一些方式配合调度器提升程序性能：
- 合理设置线程数量：不要创建太多线程，避免频繁上下文切换，CPU密集型任务线程数≈CPU核心数，IO密集型任务可以适当多一点
- 合理设置优先级：给关键任务设置更高的优先级，但不要滥用高优先级，避免优先级反转
- 避免忙等待：等待事件时使用阻塞等待，不要占着CPU空转，浪费CPU资源
- CPU亲和性：把进程/线程绑定到特定的CPU核心上运行，提高缓存命中率，减少上下文切换开销
- 避免不必要的优先级调整：不要频繁修改线程优先级，会干扰调度器的正常调度
思考问题
- 调度算法的主要目标是什么？这些目标之间有什么冲突？
- 时间片轮转算法中，时间片太大或太小会有什么问题？如何选择合适的时间片？
- 多级反馈队列调度算法有什么优点？为什么它是现在主流操作系统的首选调度算法？
- 什么是优先级反转？如何解决优先级反转问题？