跳到主要内容

进程调度

进程调度决定就绪队列中哪个进程获得 CPU。本节介绍调度目标、经典调度算法以及实时调度的特点。

调度目标​

调度算法的设计目标包括:CPU 利用率、吞吐量(throughput)、周转时间(turnaround time)、等待时间、响应时间。在交互式系统中,响应时间往往被优先考虑;在批处理系统中,吞吐量和周转时间更受关注。

经典调度算法​

先来先服务(FCFS)​

按到达顺序调度。实现简单,但平均等待时间长,会产生「护航效应」(长进程之后的短进程长时间等待)。

最短作业优先(SJF)​

选择估计运行时间最短的进程。可使平均等待时间最小化,但需要预知运行时间,且可能导致长进程饥饿。

时间片轮转(Round Robin)​

为每个就绪进程分配固定时间片(time quantum),时间片用完即切换。适用于分时系统,响应时间可预测,但时间片过短会增加切换开销。

优先级调度​

每个进程附带优先级,调度器选取最高优先级进程运行。可能引发低优先级进程无限等待(优先级反转与饥饿),常用「老化」(aging)机制缓解。

多级反馈队列(MLFQ)​

将就绪队列分成多级,新进程进入最高级;用完时间片未结束则降至下一级。该算法兼顾响应时间和整体吞吐,是 CTSS、Linux 早期调度器的经典实现。

时间片: Q1 < Q2 < Q3 < ...
规则:
  1. 新进程进入 Q1。
  2. 在某级用完时间片未完成,降至下一级。
  3. 高优先级队列为空时,才调度低优先级队列。
  4. 经一段时间,将所有进程提升回 Q1(防止饥饿)。

实时调度​

实时系统要求任务在截止时间内完成,分为:

  • 硬实时(hard real-time):错过截止时间会导致系统失效(如工业控制)。
  • 软实时(soft real-time):偶尔错过可容忍(如视频播放)。

常见实时算法包括速率单调(Rate Monotonic)和最早截止时间优先(EDF),前者按周期分配固定优先级,后者按截止时间动态调度。