进程调度算法#

批处理（重吞吐）：

• FCFS：先来先服务，非抢占，简单但有”护送效应”（短任务被长任务堵住）
• SJF/SRTF：短作业优先 / 最短剩余时间优先，平均等待时间最优，但长任务可能饿死、需预知运行时间

交互式（重响应）：

• 时间片轮转 RR：每个进程跑一个时间片就换人，响应快；时间片太大退化成 FCFS，太小则切换开销占比高
• 优先级调度：高优先级先跑，需防低优先级饿死（老化 aging 提升等待者优先级）
• 多级反馈队列 MLFQ：多个不同时间片的队列，新任务进高优先级队列，用完时间片降级——无需预知运行时间，自动逼近 SJF

Linux 实战： 普通进程用 CFS（完全公平调度器，用红黑树按 vruntime 排序，谁跑得少谁先跑）；实时进程用 SCHED_FIFO / SCHED_RR。

进程调度算法解决的是就绪队列里多个进程竞争 CPU 时谁先执行的问题，按场景分两类。批处理系统追求吞吐量：FCFS 先来先服务最简单，但非抢占，一个长任务会把后面的短任务全堵住，叫护送效应；SJF 短作业优先让平均等待时间最短，但需要预先知道运行时间，而且长任务可能一直被插队导致饿死。交互式系统追求响应时间：时间片轮转给每个进程分配固定时间片，到点就切换，保证每个进程都能及时响应，时间片大小是关键，太大退化成 FCFS，太小则上下文切换开销占比过高，一般设几十毫秒；优先级调度让重要任务先跑，但要用老化机制定期提升长期等待进程的优先级防止饿死。工程上最经典的是多级反馈队列 MLFQ，设多个时间片递增的队列，新任务先进最高优先级队列，用完时间片就降到下一级，这样短任务能很快跑完、长任务沉到低优先级，既不用预知运行时间又能自动逼近 SJF 的效果。Linux 现在普通进程用的是 CFS 完全公平调度器，核心思想是用一棵红黑树按虚拟运行时间 vruntime 排序，每次挑 vruntime 最小的进程跑，谁占用 CPU 少谁就优先，通过 nice 值调整权重，实时任务则走 SCHED_FIFO 和 SCHED_RR 单独处理。

追问方向：

• “时间片设多大合适？”→ 一般 10~100ms。要远大于一次上下文切换的开销（微秒级），否则切换占比过高；又不能太大，否则交互响应变差、退化成 FCFS。Linux CFS 没有固定时间片，而是按权重动态分配运行时间
• “怎么避免饿死（starvation）？”→ 老化 aging：进程等待越久优先级越高，迟早会被调度；MLFQ 还会周期性把所有进程重新提到最高队列
• “CFS 为什么用红黑树不用普通队列？”→ 需要频繁取最小 vruntime（O(log n)）和插入删除，红黑树平衡且有序，取最左节点即最该运行的进程
• “抢占式和非抢占式区别？”→ 非抢占只在进程主动让出（阻塞/结束）时才切换；抢占式在时钟中断或更高优先级就绪时强制切换，现代 OS 基本都是抢占式

易错点：

• ❌ SJF 一定最优——只是”平均等待时间”最优，且需预知运行时间、会饿死长任务，实际用不了
• ❌ 优先级越高一定先跑完——抢占式下高优先级随时插队，但要防低优先级饿死
• ❌ 把进程调度和线程调度混为一谈——现代 OS 调度的实际单位是线程（内核线程）