操作系统中的调度算法

操作系统中的调度算法用于决定进程或线程的执行顺序，以优化 CPU 利用率、吞吐量、响应时间等。以下是常见的调度算法，分为非抢占式和抢占式两类：

1. 非抢占式调度算法

进程一旦获得 CPU，将运行至完成或主动让出 CPU。

先来先服务（First-Come, First-Served, FCFS）：
- 按进程到达顺序执行。
- 优点：简单，易实现。
- 缺点：可能导致“短进程等待长进程”问题（护送效应），平均等待时间长。
- 时间复杂度：队列操作 ( O(1) )。
短作业优先（Shortest Job First, SJF）：
- 选择预计运行时间最短的进程优先执行。
- 优点：最小化平均等待时间（理论上最优）。
- 缺点：需预知运行时间，难以实现；长进程可能饥饿。
- 时间复杂度：选择最短进程 ( O(n) )，可用优先队列优化。
优先级调度（Priority Scheduling）：
- 根据进程优先级调度，优先级高的先执行。
- 优点：支持重要进程优先。
- 缺点：低优先级进程可能饥饿。
- 时间复杂度：取决于优先级队列实现，通常 ( O(\log n) )。

2. 抢占式调度算法

运行中的进程可能被更高优先级的进程中断。

短剩余时间优先（Shortest Remaining Time First, SRTF）：
- SJF 的抢占式版本，选择剩余运行时间最短的进程。
- 优点：进一步优化平均等待时间。
- 缺点：需预知剩余时间，上下文切换开销大。
- 时间复杂度：选择进程 ( O(n) ) 或用优先队列优化。
抢占式优先级调度（Preemptive Priority Scheduling）：
- 优先级高的进程可抢占 CPU。
- 优点：适合实时系统。
- 缺点：低优先级进程可能长期等待。
- 时间复杂度：优先级队列操作 ( O(\log n) )。
轮转调度（Round-Robin, RR）：
- 每个进程分配固定时间片（quantum），超时后切换到下一进程。
- 优点：公平，响应时间短，适合分时系统。
- 缺点：时间片设置不当可能导致性能下降。
- 时间复杂度：队列操作 ( O(1) )。
多级队列调度（Multilevel Queue Scheduling）：
- 进程按优先级分为多个队列，每个队列可使用不同调度算法（如高优先级用 RR，低优先级用 FCFS）。
- 优点：灵活，适合异构进程。
- 缺点：复杂，低优先级队列可能饥饿。
- 时间复杂度：取决于队列实现。
多级反馈队列调度（Multilevel Feedback Queue, MLFQ）：
- 类似多级队列，但进程可根据行为动态调整优先级（如 I/O 密集型进程优先级提升）。
- 优点：自适应，平衡响应时间和吞吐量。
- 缺点：实现复杂，需调优参数。
- 时间复杂度：队列操作 ( O(\log n) ) 或更高。

3. 其他调度算法

最早截止时间优先（Earliest Deadline First, EDF）：
- 实时系统中，按任务截止时间排序，截止时间近的先执行。
- 优点：适合硬实时系统，保证截止时间。
- 缺点：需知道截止时间，计算复杂。
- 时间复杂度：排序 ( O(n \log n) ) 或优先队列 ( O(\log n) )。
速率单调调度（Rate Monotonic Scheduling, RMS）：
- 实时系统中，周期短的任务优先级高，固定优先级分配。
- 优点：简单，适合周期性任务。
- 缺点：不适合非周期任务。
- 时间复杂度：优先级分配 ( O(1) )。

4. 总结

非抢占式：FCFS、SJF、优先级调度，适合简单或批处理系统。
抢占式：SRTF、抢占式优先级、RR、MLQ、MLFQ，适合分时或实时系统。
实时调度：EDF、RMS，专为满足时间约束设计。
选择依据：
- FCFS 和 RR 适合公平性要求。
- SJF 和 SRTF 优化等待时间。
- 优先级调度和 MLFQ 适合混合负载。
- EDF 和 RMS 用于实时系统。