进程调度算法

比较准则

• CPU使用率：忙时间/总时间
• 吞吐量：完成的进程数/总时间
• 周转时间：结束时间 - 初始化时间
• 就绪等待时间：就绪进程在就绪队列中的时间
• 响应时间：第一次响应时间 - 提交时间
• 公平性：每个进程获得的CPU时间相对公平

调度算法

FCFS（先来先服务）

• 描述：依据进程进入就绪队列的顺序进行调度。
• 优点：简单
• 缺点
  • 平均等待时间波动大
  • 短作业可能被长作业阻塞（convoy effect）
  • IO和CPU利用率低

SJF（最短作业优先）

• 描述：选择预计运行时间最短的进程执行。
• 优点：平均周转时间最短
• 缺点
  • 需要准确预测作业长度
    • 简单方法：问用户，用户欺骗就杀死
    • 复杂方法：使用历史数据预测：$\tau_{n+1}=\alpha t_n + (1-\alpha)\tau_n$
  • 不允许抢占；长作业可能被饿死（starvation）

SRT（最短剩余时间优先）

• 描述：SJF的抢占式版本，选择剩余时间最短的进程。
• 优点：平均等待时间更短
• 缺点：同SJF，且抢占会增加上下文切换开销；也可能导致饿死

HRRN（最高响应比优先）

• 描述：计算响应比 $R = \frac{ \text{就绪等待时间} + \text{执行时间}}{\text{执行时间}}$，选择响应比最高的进程。
• 优点：平衡等待时间和执行时间，防止无限期推延，避免饿死
• 缺点：计算复杂度高，响应比可能不稳定

RR（轮转调度，Round-Robin）

• 描述：每个进程分配固定时间片，时间片用完后放回就绪队列。
• 优点：公平性高，响应时间短
• 缺点：时间片过小会增加上下文切换开销，过大则类似FCFS（经验规则：维持上下文切换开销在 1% 以内）

MQ（多级队列调度）

• 描述
  • 将就绪队列分为多个优先级队列，不同队列优先级不同
  • 每个队列有不同的调度策略（如FCFS、SJF等）。
  • 规则1：如果A优先级>B，则A队列的进程优先于B队列的进程
  • 规则2：如果A优先级=B，则A队列的进程和B队列的进程轮流执行
• 优点：适应不同类型的进程需求
• 缺点：队列间优先级固定，可能导致低优先级进程饿死

MLFQ（多级反馈队列调度）

• 描述
  • 类似MQ，但允许进程在不同优先级队列间移动
  • 规则1：新进程进入最高优先级队列
  • 规则2：如果进程在当前队列时间片用完，则降级到下一个低优先级队列
  • 规则3：过一段时间 $S$ 就提升所有进程到最高优先级
• 优点：适应性强，能根据进程行为调整优先级，防止饿死
• 缺点：实现复杂，可能导致优先级反转问题

FSS（公平共享调度）

• 描述
  • 控制用户对系统资源的访问
  • 不同用户拥有多个进程
  • 按用户优先级分配资源
  • 保证不重要的用户不会占用过多资源
  • 未使用的资源按比例分配

总结

调度算法	基本策略	抢占性	是否导致饿死	实现复杂度	主要优点	典型缺点
FCFS	按到达顺序执行	非抢占	不会	极低	简单、公平	护航效应明显；平均等待时间长；利用率低
SJF	执行时间最短的进程优先	非抢占	会（长作业）	中	平均周转时间最优	依赖执行时间预测；长作业可能无限期等待
SRT	剩余时间最短的进程优先	抢占	会（长作业）	高	平均等待时间优于SJF	上下文切换开销大；预测需求同SJF
HRRN	响应比最高优先（R=(等待+执行)/执行）	非抢占	不会	高	平衡等待与执行时间；避免饿死	计算开销大；响应比波动不稳定
RR	固定时间片轮转	抢占	不会	中	响应快、公平性强	时间片设置敏感：过大→FCFS；过小→切换开销高
MQ	多优先级队列+队列内独立策略	可选（依策略）	会（低优先级）	高	适应不同进程类型需求	队列间优先级固定；低优先级进程易饿死
MLFQ	动态调整进程优先级队列	抢占	不会（周期性重置）	极高	自适应进程行为；兼顾长短作业	实现复杂；可能优先级反转
FSS	按用户优先级分配资源配额	可选（依策略）	不会	极高	保障用户级公平；资源隔离性好	需维护用户资源配额；调度粒度复杂

实时调度

实时操作系统

• 描述：满足实时应用的时间约束，确保任务在规定时间内完成。
• 特点：高可靠性、可预测性、低延迟
• 分类
  • 硬实时系统：必须在严格时间限制内完成任务，否则可能导致灾难性后果。
  • 软实时系统：尽量在时间限制内完成任务，偶尔延迟可接受。

实时任务

周期实时任务

• 描述：在固定周期内重复执行的任务。
• 周期 $p$：任务请求间隔
• 执行时间 $e$：任务实际执行所需时间
• 使用率 $U = \frac{e}{p}$：任务在周期内占用CPU的比例
• 可调度：
  • 单任务：如果 $U \leq 1$，则任务可调度。
  • 多任务：如果所有任务的总使用率 $\sum U_i \leq 1$，则可调度。

实时调度算法

静态优先级调度：速率单调调度（RM, Rate Monotonic）

• 描述：周期越短的任务优先级越高，抢占式。

动态优先级调度：最早截止时间优先（EDF, Earliest Deadline First）

• 描述：任务截止时间越近优先级越高，抢占式。

动态优先级调度：最早松弛时间优先（LLF, Least Laxity First）

• 描述：任务松弛时间（必须完成时间-当前时间-本身还需要运行时间）最小的优先级最高，抢占式。（最做不完的先做）

优先级反置

• 描述：低优先级任务持有资源，导致高优先级任务无法执行。
• 解决方法：
  • 优先级继承：低优先级任务持有资源，且请求相同资源的高优先级进程被阻塞时，低优先级进程提升到高优先级进程相同的优先级。
  • 优先级天花板：所有任务在访问共享资源前提升到可能访问该共享资源所有进程的最高可能优先级，避免反转。