进程的调度算法有哪些?

# 常见调度算法 **按是否可抢占** * 非抢占：一次拿到 CPU 直到阻塞/退出（简单但响应差） * 抢占：可被更高优/时间片用完的进程打断（交互友好） **经典/通用** * **FCFS（先来先服务）**：队头先跑；实现简单；易“队头阻塞”，交互差。 * **SJF（短作业优先）**：估计运行时最短者先跑；平均等待/周转最小；易饿长作业；需预测作业时间。 * **SRTF（最短剩余时间优先）**：SJF 的抢占版；响应最好；更容易饿长作业。 * **HRRN（最高响应比优先）**：响应比 = (等待+服务)/服务；兼顾短作业与防饥饿，非抢占常见于批处理。 * **优先级调度**（可抢/非抢）：按优先级挑；需**老化(aging)** 防饥饿。 * **RR（时间片轮转）**：固定时间片轮转；交互好；时间片太小→切换开销大，太大→响应变差。 * **多级队列（MLQ）**：不同类型进程分队列（前台/后台），队列间有优先级。 * **多级反馈队列（MLFQ）**：新进程从高优队列开始，时间片用完则降级，长期等待可升级；**无需显式估计作业长短**，交互/混合场景常用。 * **彩票/比例公平（Lottery/Fair-share）**：按“票数/权重”随机/配额分配，面向公平和配额隔离。 **实时系统** * **RM（Rate Monotonic）**：周期短→优先级高，固定优先级。 * **EDF（Earliest Deadline First）**：最早截止期先跑；理论上处理器利用率高。 * Linux 实际类：`SCHED_FIFO`、`SCHED_RR`（实时固定优先级）、`SCHED_DEADLINE`（近 EDF）。 **现代通用 OS（Linux）** * **CFS（完全公平调度）**：按权重/虚拟运行时间分配 CPU，基于红黑树；普通进程类 `SCHED_OTHER/SCHED_NORMAL` 的默认实现，兼顾公平与吞吐。 # 什么时候用哪种？ * **批处理/离线**： * 追求最短平均周转 → **SJF/SRTF**（有时长估计时）；怕饿死长作业 → **HRRN**。 * **交互式/桌面/在线服务**： * 通用首选 **RR（合适时间片）**、**MLFQ** 或现代系统的 **CFS**（默认）。 * **混合负载（既有短交互又有长批处理）**： * **MLFQ** 或 **CFS + nice/权重** 调权重。 * **需要显式优先级控制**： * **优先级调度**（配**老化**）；Linux 下用 `nice`/`chrt`。 * **硬实时/软实时**： * 硬实时 → **RM/EDF**（Linux 用 `SCHED_DEADLINE`）； * 软实时 → `SCHED_FIFO`/`SCHED_RR`（注意不可饿死普通任务）。 # 关键指标与注意点 * 指标：**吞吐量**、**平均等待/周转时间**、**响应时间**、**公平性**、**切换开销**。 * 常见问题： * **饥饿**（优先级/短作业偏置）→ 用**老化**或反馈队列缓解。 * **时间片选择**：过小→上下文切换开销大；过大→响应差。 * **SJF/SRTF 的“服务时间未知”**：用**指数平滑**预测 CPU burst（经验预测）。 * **实时类会压制普通任务**：务必限额与隔离，避免系统不可响应。 # 面试一句话记忆 * 批处理看 **SJF/HRRN**，交互看 **RR/MLFQ/CFS**，实时看 **RM/EDF/SCHED\_DEADLINE**；饥饿用**老化**，公平靠**权重**，响应调**时间片**。