操作系统进程调度算法详解

操作系统中的进程调度算法用于决定就绪队列中的进程如何分配CPU时间。常见的调度算法可分为以下几类：

一、基础调度算法

1. 先来先服务（FCFS, First-Come-First-Served）

   • 原理：按进程到达顺序分配CPU。
   • 特点：
     • 非抢占式，适合批处理系统。
     • 可能导致“护航效应”（短作业等待长作业完成）。
   • 示例：进程顺序为 P1（24ms）、P2（3ms）、P3（3ms），平均等待时间较高。

2. 短作业优先（SJF, Shortest Job First）

   • 原理：优先运行预计运行时间最短的进程。
   • 变种：
     • 非抢占式（SJF）：一旦开始，直到完成。
     • 抢占式（SRTN, Shortest Remaining Time Next）：新短作业到达时抢占当前进程。
   • 特点：
     • 最小化平均等待时间，但需预知运行时间（实际中难以实现）。
     • 可能导致长作业饥饿。

3. 时间片轮转（RR, Round Robin）

   • 原理：每个进程分配固定时间片（如10-100ms），用完则放回队列尾部。
   • 特点：
     • 抢占式，适合交互式系统。
     • 时间片过大退化为FCFS；过小增加上下文切换开销。

4. 优先级调度（Priority Scheduling）

   • 原理：为每个进程分配优先级，按优先级高低执行。
   • 变种：
     • 静态优先级：可能导致低优先级进程饥饿。
     • 动态优先级：根据等待时间调整（如老化机制）。
   • 特点：可抢占或非抢占。

二、高级调度算法

1. 多级反馈队列（MLFQ, Multilevel Feedback Queue）

   • 原理：
     • 设置多个优先级队列，新进程进入最高优先级队列。
     • 若进程用完时间片未完成，则降级到下一队列。
     • 低优先级队列的时间片通常更大。
   • 特点：
     • 综合了FCFS、RR和优先级调度。
     • 平衡响应时间和吞吐量（如UNIX、Windows使用变种）。

2. 高响应比优先（HRRN, Highest Response Ratio Next）

   • 原理：选择响应比最高的进程，响应比 = ( \frac{\text{等待时间} + \text{预计运行时间}}{\text{预计运行时间}} )
   • 特点：避免饥饿，但需预估运行时间。

三、实时系统调度算法

1. 最早截止时间优先（EDF, Earliest Deadline First）
   • 原理：优先执行截止时间最早的实时任务。
2. 速率单调调度（RMS, Rate-Monotonic Scheduling）
   • 原理：周期性任务按周期频率分配优先级（周期越短，优先级越高）。

四、算法对比

五、实际系统中的应用

• Linux：采用完全公平调度器（CFS），基于红黑树跟踪进程的虚拟运行时间。
• Windows：使用多级反馈队列，结合优先级和时间片调整。
• 实时系统（如VxWorks）：常用EDF或RMS保证任务截止时间。

总结

选择调度算法需权衡：

• 公平性（如RR）
• 吞吐量（如SJF）
• 响应时间（如MLFQ）
• 实时性（如EDF）

实际系统中常采用混合策略（如MLFQ）以平衡不同需求。