CPU调度调度算法

1. 先来先服务（FCFS）调度算法

• 原则：按进程/作业到达顺序调度（先到先服务），非抢占式。
• 适用场景：作业调度、进程调度（辅助其他算法处理同优先级进程）。
• 优点：算法简单，公平（对长作业有利）。
• 缺点：
  • 短作业可能因长作业先到而长期等待（短作业吃亏）。
  • 效率低，平均周转时间长。
• 特点：有利于CPU繁忙型作业（如科学计算），不利于I/O繁忙型作业（如频繁读写文件）。

2. 短作业优先（SJF）/短进程优先（SPF）调度算法

• 原则：选择估计运行时间最短的作业/进程优先执行。
• 分类：
  • 非抢占式：一旦开始执行，直至完成或阻塞。
  • 抢占式（最短剩余时间优先，SRTF）：新进程到达时，若剩余时间更短则抢占CPU。
• 优点：平均等待时间、平均周转时间最优（对短作业友好）。
• 缺点：
  • 长作业饥饿（长期等待）。
  • 依赖用户估计运行时间（可能不准确）。
  • 未考虑作业紧急程度（实时任务无法保证）。

3. 高响应比优先调度算法

• 原则：综合考虑等待时间和运行时间，选择响应比最高的作业。
• 
• 优点：
  • 短作业：等待时间相同时，服务时间短→响应比高（类似SJF）。
  • 长作业：等待时间增长→响应比提高，避免饥饿（类似FCFS）。
• 适用场景：作业调度（平衡FCFS和SJF的优缺点）。

4. 优先级调度算法

• 原则：按进程/作业优先级高低调度，优先级高者优先。
• 调度方式：
  • 非抢占式：运行进程主动放弃CPU后才调度高优先级进程。
  • 抢占式：高优先级进程就绪时立即剥夺当前CPU。
• 优先级类型：
  • 静态优先级：创建时确定，运行中不变（简单但可能饥饿）。
  • 动态优先级：随等待时间/运行状态变化（如等待时间越长优先级越高，避免饥饿）。
• 优先级设置依据：系统进程 > 用户进程；交互进程 > 非交互进程；I/O型进程 > 计算型进程。

5. 时间片轮转（RR）调度算法

• 原则：所有就绪进程按FCFS排队，轮流分配CPU时间片（如30ms），时间片用完后剥夺CPU，放入就绪队列末尾。
• 适用场景：分时系统（如Unix/Linux终端交互）。
• 时间片大小影响：过大→退化为FCFS；过小→上下文切换频繁，CPU开销大。

• 优点：公平性好，响应时间可控；缺点：平均周转时间较长。

6. 多级队列调度算法

• 原则：设置多个就绪队列（如按进程类型/优先级划分），每个队列采用不同调度算法（如 foreground队列用RR，background队列用FCFS）。
• 优点：灵活，可针对不同进程类型优化（如实时进程用高优先级队列+抢占调度）。

7. 多级反馈队列调度算法（最高级综合算法）

• 核心思想：结合优先级调度和时间片轮转，动态调整进程优先级和时间片。
• 实现机制：
  • 多个队列：优先级从高到低（Q1 > Q2 > ... > Qn），时间片逐级加倍（如Q1=10ms，Q2=20ms）。
  • 调度规则：
    • 新进程入Q1，按FCFS调度，时间片内完成则退出；否则降入Q2末尾。
    • 仅当高优先级队列为空时，才调度低优先级队列（抢占式：高优先级进程就绪时立即剥夺低优先级进程）。
• 优点：
  • 短作业：在高优先级队列快速完成（类似SJF）。
  • I/O型进程：频繁阻塞后重回高优先级队列（响应快）。
  • 长作业：逐次降入低优先级队列，最终按RR执行（避免饥饿）。

8. 基于公平原则的调度算法

• 保证调度算法：保证每个进程获得1/n的CPU时间（n为进程数），跟踪实际CPU时间与应得时间的比率，优先调度比率最小的进程。
• 公平分享调度算法：保证每个用户获得公平的CPU份额（而非进程），如2个用户则各占50% CPU时间，无论用户启动多少进程。

各类算法对比表

核心考点 📌

1. SJF的最优性：平均等待时间和平均周转时间最短（仅限非抢占式，且已知运行时间）。
2. 多级反馈队列的优势：综合多种算法优点，动态调整优先级，是“最优的通用调度算法”。
3. 饥饿与死锁的区别：饥饿是调度策略导致（如SJF中的长作业），死锁是资源竞争导致的循环等待。
4. 时间片轮转的时间片设置：过小→切换开销大，过大→退化为FCFS。

        ✨ 一句话总结：调度算法需平衡公平性、效率与响应时间，FCFS简单、SJF高效、优先级支持紧急任务、多级反馈队列兼顾多方，是现代OS的核心选择！ ✨