进程调度算法 描述 进程调度算法是操作系统用来决定哪个就绪状态的进程可以获得CPU时间的方法。它的核心目标包括提高CPU利用率、保证公平性、减少响应时间等。不同的调度算法适用于不同的场景（如批处理系统、交互式系统等）。 关键概念 CPU-I/O 执行周期 ：进程的执行由CPU计算和I/O等待交替组成。 调度队列 ：就绪队列（存放等待CPU的进程）、设备队列（等待I/O的进程）。 抢占式与非抢占式 ： 非抢占式：进程主动释放CPU前一直运行。 抢占式：调度器可强制暂停当前进程，分配CPU给其他进程。 常见调度算法详解 1. 先来先服务（FCFS） 规则 ：按进程到达就绪队列的顺序分配CPU，非抢占式。 举例 ：假设进程P1、P2、P3的到达时间分别为0、1、2，所需CPU时间分别为24、3、3。 时序图： P1运行0→24（P2、P3在队列等待） P2运行24→27 P3运行27→30 平均等待时间 ：(0 + 23 + 25) / 3 = 16 缺点 ：短进程可能因长进程而长时间等待（"护航效应"）。 2. 最短作业优先（SJF） 规则 ：选择预估运行时间最短的进程，可分为非抢占式与抢占式。 非抢占SJF示例 ：进程到达时间/运行时间：P1(0,6)、P2(2,4)、P3(4,2) 在时间0，只有P1，运行0→6 在时间6，就绪队列有P2(运行时间4)、P3(运行时间2)，优先选P3→运行6→8，最后P2运行8→12 平均等待时间 ：P1(0)、P2(8-2=6)、P3(6-4=2)，均值=(0+6+2)/3≈2.67 抢占式SJF（最短剩余时间优先） ： 时间0，P1运行。 时间2，P2到达，剩余时间(4) < P1剩余时间(4)，P1被抢占，P2运行。 时间4，P3到达，剩余时间(2)最短，P2被抢占，P3运行至6结束。接着选剩余时间最短的P2(剩余2)运行至8，最后P1运行至14。 平均等待时间 ：P1(0+8-2=6)、P2(2-2=0)、P3(4-4=0)，均值=2。 3. 优先级调度 规则 ：每个进程有优先级，选择优先级最高的进程（数字小可能表示高优先级）。 问题 ：低优先级进程可能"饥饿"（永远得不到CPU）。 解决 ：使用"老化"技术，逐渐增加等待进程的优先级。 4. 时间片轮转（RR） 规则 ：为每个进程分配固定时间片（如10ms），超时后放回就绪队列尾部，抢占式。 示例 ：进程P1(0,5)、P2(1,3)、P3(2,2)，时间片=2： 时间0：P1运行2单位（剩余3） 时间2：队列P2(3)、P3(2)，P2运行2单位（剩余1） 时间4：队列P3(2)、P1(3)，P3运行2单位（结束） 时间6：队列P1(3)、P2(1)，P1运行2单位（剩余1） 时间8：队列P2(1)、P1(1)，P2运行1单位（结束） 时间9：P1运行1单位（结束） 特点 ：时间片过大退化为FCFS；过小则上下文切换开销大。 5. 多级队列调度 场景 ：将就绪队列分为多个独立队列（如前台交互队列、后台批处理队列），每个队列可使用不同调度算法（如前台用RR，后台用FCFS）。 调度 between queues ： 固定优先级：先处理前台队列，可能导致后台饥饿。 时间片分配：例如前台队列分80%CPU时间，后台分20%。 6. 多级反馈队列（MLFQ） 目标 ：综合优化周转时间与响应时间，无需预知进程运行时间。 规则示例 ： 设置多个队列Q0、Q1、Q2...，优先级递减，时间片递增（如Q0时间片=8ms，Q1=16ms）。 新进程进入最高优先级队列Q0。 若进程在时间片内未完成，降级到下一优先级队列。 可定期将所有进程重新提到最高队列，防止饥饿。 优点 ：短作业快速完成，长作业不会完全饿死。 总结 CPU密集型进程 ：适合用SJF减少平均等待时间。 交互式进程 ：适合用RR或优先级调度保证响应性。 通用系统 ：多级反馈队列是平衡多种指标的实用方法。 选择算法时需权衡公平性、效率、开销与实现复杂度。