操作系统中的进程调度算法：先来先服务（FCFS）与短作业优先（SJF） 1. 问题描述 进程调度是操作系统的核心功能之一，负责从就绪队列中选择一个进程分配CPU资源。 先来先服务（FCFS） 和 短作业优先（SJF） 是两种经典的调度算法，分别基于进程到达时间和预估执行时间进行决策。它们的差异直接影响系统的吞吐量、响应时间和公平性。 2. 先来先服务（FCFS）调度算法 核心思想 按照进程到达就绪队列的顺序分配CPU，类似排队机制，先到的进程先被调度。 调度过程 数据结构 ：维护一个先进先出（FIFO）队列，新到达的进程加入队尾。 调度时机 ： CPU空闲时，从队头取出第一个进程执行。 进程执行期间不会被抢占（非抢占式）。 示例分析 ： 假设三个进程到达时间和执行时间如下： P1：到达时间=0，执行时间=5 P2：到达时间=2，执行时间=3 P3：到达时间=4，执行时间=2 调度顺序 ：P1（0~5）→ P2（5~8）→ P3（8~10） 周转时间 = 完成时间 - 到达时间 P1: 5-0=5 P2: 8-2=6 P3: 10-4=6 平均周转时间 = (5+6+6)/3 ≈ 5.67 特点与问题 优点 ：实现简单，保证公平性。 缺点 ： 护航效应（Convoy Effect） ：长进程先运行时，短进程需等待较长时间，导致平均周转时间较长。 对I/O密集型进程不友好（进程执行时可能阻塞I/O，但CPU仍被占用）。 3. 短作业优先（SJF）调度算法 核心思想 优先选择预估执行时间最短的进程，以最小化平均等待时间。 调度方式 非抢占式SJF ：进程开始执行后持续运行到完成，调度时选择当前就绪队列中执行时间最短的进程。 抢占式SJF（又称最短剩余时间优先，SRTF） ：新进程到达时，若其执行时间比当前运行进程的剩余时间更短，则抢占CPU。 示例分析（非抢占式SJF） 使用同一组进程： P1：到达时间=0，执行时间=5 P2：到达时间=2，执行时间=3 P3：到达时间=4，执行时间=2 调度顺序 ： 时间0：只有P1就绪，执行P1（0~5）。 时间5：P2和P3已到达，选择执行时间更短的P3（执行时间2）→ P3（5~7）。 时间7：执行P2（7~10）。 周转时间： P1: 5-0=5 P2: 10-2=8 P3: 7-4=3 平均周转时间 = (5+8+3)/3 ≈ 5.33（优于FCFS的5.67）。 特点与问题 优点 ：理论上最小化平均等待时间。 缺点 ： 饥饿问题 ：长进程可能因持续有短进程到达而无法执行。 需要预知进程执行时间（实际中需通过历史数据预测）。 抢占式SJF调度开销较大（频繁上下文切换）。 4. FCFS与SJF的对比 | 维度 | FCFS | SJF | |----------------|---------------------------|-----------------------------| | 调度依据 | 到达时间 | 执行时间 | | 公平性 | 高 | 低（长进程可能饥饿） | | 平均周转时间 | 较长 | 较短（理论最优） | | 实现复杂度 | 低（仅需FIFO队列） | 高（需排序或预测时间） | | 适用场景 | 批处理系统 | 理论优化或短任务优先场景 | 5. 实际应用与优化 SJF的变种（如 最高响应比优先，HRRN ）通过动态计算优先级（优先级=等待时间+执行时间）/执行时间），缓解饥饿问题。 现代操作系统（如Linux CFS）结合时间片轮转与优先级机制，平衡响应时间和吞吐量。 通过理解FCFS和SJF的机制与权衡，可以深入掌握调度算法设计中的核心矛盾（公平vs效率），并为学习更复杂的调度策略奠定基础。