面试官：请问常见的进程调度算法有哪些？各有什么优缺点？
面试回答
“常见的进程调度算法主要有以下几种：
首先是先来先服务（FCFS），顾名思义就是谁先来就先调度谁。它实现最简单，但缺点是对短作业很不友好，如果前面有个长作业，后面的短作业就会被饿死。
为了解决这个问题，有了短作业优先（SJF），它会优先调度运行时间最短的进程。这种算法能最大程度降低平均等待时间，但缺点是长作业可能会被饿死，而且在实际中很难准确预估进程的运行时间。
前面两种主要用于批处理系统。在交互式系统中，最常用的是时间片轮转（RR）。系统给每个进程分配一个固定的时间片，时间一到就切换给下一个进程。它保证了公平性和响应速度，但时间片的大小很难把控：太大了退化成先来先服务，太小了频繁上下文切换会带来很大的性能开销。
此外还有优先级调度，给每个进程分配优先级，优先级高的先执行。为了防止低优先级进程饿死，通常会结合动态优先级，随着等待时间的增加提高优先级（也就是老化机制）。
最后是现代操作系统（如 Linux）常用的多级反馈队列调度。它结合了前面的优点，设置多个不同优先级的队列，优先级越高的队列时间片越小。新进程先进入最高优先级队列，如果时间片用完还没执行完，就降级到下一个队列。这种算法既能快速响应短作业，又能兼顾长作业，是目前公认比较理想的调度算法。”
系统讲解
进程调度算法的核心目标是在吞吐量、周转时间、响应时间和公平性之间寻找平衡。不同的操作系统环境（批处理、交互式、实时）对这些指标的侧重点不同。
核心算法对比
| 调度算法 | 英文简称 | 核心思想 | 优点 | 缺点 | 适用场景 |
|---|---|---|---|---|---|
| 先来先服务 | FCFS | 按照进程到达的先后顺序进行调度 | 实现简单，公平（对到达顺序而言） | 护航效应（长作业阻塞短作业），平均周转时间长 | 批处理系统、后台任务 |
| 短作业优先 | SJF | 优先调度估计运行时间最短的进程 | 平均等待时间和平均周转时间最短 | 长作业容易饿死，难以准确预估运行时间 | 批处理系统 |
| 时间片轮转 | RR | 每个进程分配一个时间片，轮流执行 | 响应快，公平，不会有进程饿死 | 时间片大小难以确定，上下文切换开销大 | 交互式系统、分时系统 |
| 优先级调度 | Priority | 优先调度优先级最高的进程 | 可以优先处理紧急任务 | 低优先级进程可能饿死（需引入老化机制） | 实时系统、通用系统 |
| 多级反馈队列 | MFQ | 多个优先级队列，时间片随优先级降低而增大 | 兼顾长短作业，响应快，无需预知运行时间 | 实现复杂 | 现代通用操作系统（如 Linux） |
算法详解与演进逻辑
进程调度算法的演进是一个不断解决痛点、权衡利弊的过程：
- FCFS (First Come First Serve)：最直观的做法。
- 痛点：一个耗时 10 秒的进程排在前面，后面 100 个只需 0.1 秒的进程都要等它，导致平均等待时间极长（护航效应）。
- SJF (Shortest Job First)：为了解决 FCFS 的痛点，让短作业先走。
- 痛点：如果有源源不断的短作业到来，长作业将永远得不到 CPU（饥饿问题）。
- RR (Round Robin)：为了解决饥饿问题和提高交互响应速度，大家平分时间。
- 痛点：时间片大小（Quantum）的选择是门艺术。通常时间片设为 10ms - 100ms 比较合理。
- 多级反馈队列 (Multilevel Feedback Queue)：集大成者。
- 规则 1：如果 A 的优先级 > B 的优先级，运行 A。
- 规则 2：如果 A 和 B 优先级相同，轮转运行。
- 规则 3：新任务进入最高优先级队列。
- 规则 4：任务用完时间片后，优先级降一级。
- 规则 5：经过一段时间，将所有任务提升到最高优先级队列（防止饿死）。
亮点与深度
Linux 的完全公平调度器 (CFS)
现代 Linux 系统（2.6.23 版本之后）默认使用的是 CFS (Completely Fair Scheduler)。
CFS 并没有使用传统的时间片和多级队列，而是基于虚拟运行时间 (vruntime) 的概念。
- 每个进程都有一个 vruntime，记录了它已经运行的虚拟时间。
- CFS 总是选择 vruntime 最小的进程来运行。
- 进程的优先级（nice 值）会影响 vruntime 的增长速度：优先级高的进程 vruntime 增长慢，从而能获得更多的 CPU 时间；优先级低的进程 vruntime 增长快。
- CFS 使用红黑树来维护所有可运行的进程，以 vruntime 为键值，这样查找最小 vruntime 进程的时间复杂度仅为
O(log N)。
常见追问
追问 1：什么是上下文切换？它包含哪些开销？
上下文切换是指 CPU 从一个进程（或线程）切换到另一个进程（或线程）时，保存当前进程状态并恢复目标进程状态的过程。 开销主要包括：
- 直接开销：保存和恢复寄存器、程序计数器、栈指针等硬件上下文；切换页表（如果是进程切换）。
- 间接开销：CPU 缓存（L1/L2/L3 Cache）失效，TLB（快表）失效。这是上下文切换最大的性能惩罚。
追问 2：进程调度和线程调度有什么区别？
在支持内核级线程的操作系统中，调度的基本单位是线程而不是进程。关于进程、线程和协程的更多区别，可以参考 进程、线程与协程的区别。
- 如果切换的两个线程属于同一个进程：只需要切换线程的私有上下文（如寄存器、栈），不需要切换页表，因此开销较小，Cache 和 TLB 大部分仍然有效。
- 如果切换的两个线程属于不同进程：不仅要切换线程上下文，还要切换进程的地址空间（页表），开销等同于进程切换。