操作系统（16）-- 进程间的调度算法

先来先服务

核心思想：按到达顺序排队，先来的进程优先获得CPU，运行直至完成或主动阻塞。

调度方式：非抢占式

优点：算法简单易于实现，对所有进程“公平”。

缺点：一个长进程会阻塞后面所有的短进程，导致平均等待时间较长。对io密集型进程不太友好

短作业优先

核心思想：从就绪队列中选择预计运行时间最短的进程运行。

调度方式：通常是指非抢占式版本

优点：理论最优，能给出最短的平均等待时间和平均周转时间

缺点：无法准确获知进程的“作业长度”，长作业可能因不断有短作业到达而无限期等待。

最短剩余时间优先

核心思想：短作业优先的抢占式版本。当新进程到达时，比较其总运行时间与当前进程的剩余运行时间。若新进程更短，则抢占CPU。

调度方式：抢占式

优点：比SJF更能优化平均等待时间，响应性更好。

缺点：同样需要预知运行时间，且实现和上下文切换开销更大。

优先级调度

核心思想：为每个进程分配一个优先级（通常数字越小优先级越高）。调度时，选择优先级最高的进程。

调度方式：可分为非抢占式和抢占式

轮转法

核心思想：为每个进程分配一个固定的CPU时间片。进程用完时间片后，被抢占并放到就绪队列末尾，然后调度队列中的下一个进程。

调度方式：抢占式

核心参数：时间片大小。

• 时间片过大-> 退化为FCFS，响应性变差。

• 时间片过小-> 上下文切换过于频繁，系统开销巨大，吞吐量下降。

优点：绝对公平，响应性好，适合交互式系统。

缺点：平均等待时间通常不是最优。

多级反馈队列调度

• 综合了优先级、时间片轮转，并能根据进程的历史行为动态调整，是现代操作系统最接近实际使用的算法。

• 规则：

  1. 设置多个不同优先级的就绪队列，优先级从高到低。

  2. 每个队列有自己的时间片大小（高优先级队列时间片通常更小）。

  3. 新进程进入最高优先级队列。

  4. 进程用完当前队列的时间片后，若未完成，则被降级到下一级队列（时间片可能增大）。

  5. 进程因I/O主动放弃CPU，则其优先级保持不变或提升（奖励交互式进程）。

  6. 调度时，总是先运行高优先级队列中的进程，仅当高优先级队列为空时，才运行下一级队列。

• 优点：

  • 能自动区分进程类型：短作业（很快完成）、交互式/I/O密集型（频繁放弃CPU，保持高优先级）、CPU密集型（逐步降级）。

  • 兼具多项优点：对短作业和交互式进程响应快，同时不让长作业饿死。

• 缺点：实现复杂，需要配置多个参数（队列数量、时间片大小、优先级调整策略）。

• 类比：机场多级安检通道。VIP/头等舱通道（队列少，检查快但时间片短），经济舱通道（队列多，检查慢但时间片长）。如果一个旅客总在通道里磨蹭（用光时间片），会被请到更慢的队列；而快速完成安检又返回拿东西的旅客（类似I/O），可能被允许回到更快队列。

总结