第五章：CPU调度

1. 基本概念

为什么要进行CPU调度？

• 目的：在多道程序环境中，当CPU空闲时（例如，一个进程进行I/O操作时），操作系统需要从就绪队列中选择另一个进程来执行，以最大化CPU利用率。

CPU-I/O 执行周期

• 进程的执行由一系列 CPU执行（CPU Burst） 和 I/O等待（I/O Burst） 交替组成。
  
• CPU密集型进程：CPU Burst时间长，I/O Burst时间短。
  
• I/O密集型进程：CPU Burst时间短，I/O Burst时间长。
  
• CPU调度器的目标是找到一个高效的方法，在多个进程间切换，使得CPU尽可能忙碌。

---

2. 调度时机与方式

CPU调度可能发生在以下四种情况：

1. 进程从运行状态切换到等待状态（如发起I/O请求）。
   
2. 进程从运行状态切换到就绪状态（如被中断）。
   
3. 进程从等待状态切换到就绪状态（如I/O完成）。
   
4. 进程终止。

调度方式

• 非抢占式调度：一旦CPU分配给一个进程，该进程会一直占用CPU直到它终止或主动进入等待状态。（对应上述情况1和4）
  
• 抢占式调度：操作系统可以强制暂停当前正在运行的进程，将CPU分配给另一个更重要的进程。（对应上述情况2和3）
  • 优点：能提供更好的响应性和系统吞吐量。
    
  • 缺点：需要更复杂的内核设计，可能产生竞态条件。

---

3. 调度器与调度准则

调度器

• 短期调度器：从就绪队列中选择下一个要执行的进程。
  
• 调度器：是一个内核模块，负责执行上下文切换、切换到用户模式并跳转到用户程序的正确位置以重启它。
  
• 调度延迟：调度器停止一个进程并启动另一个进程所需的时间。这个时间越短越好。

调度准则（评价指标）

1. CPU利用率：使CPU尽可能忙碌。
   
2. 吞吐量：单位时间内完成执行的进程数量。
   
3. 周转时间：从进程提交到进程完成的总时间（包括在就绪队列中等待、CPU执行和I/O时间）。
   
4. 等待时间：进程在就绪(必须是ready)队列中等待的总时间。
   
5. 响应时间：从提交请求到产生第一个响应（而非最终输出）的时间。这对交互式系统至关重要。

目标：最大化CPU利用率和吞吐量，最小化周转时间、等待时间和响应时间。

---

4. 调度算法

1. 先来先服务

• 思想：按照进程进入就绪队列的顺序分配CPU。
  
• 特点：
  • 实现简单。
    
  • 对短作业不利（护航效应）：一个长作业会使得后面所有的短作业长时间等待。
    
  • 非抢占式。
    
• 例子：队列 P1(24), P2(3), P3(3)，按此顺序执行。P2和P3需要等待很长时间。

2. 最短作业优先 / 最短剩余时间优先

• 思想：选择下一个CPU执行时间最短的进程运行。
  
• 特点：
  • 理论上是最优的，能给出最小的平均等待时间。
    
  • 非抢占式（SJF） 和 抢占式（SRTF） 两种。
    
  • 问题：可能导致长作业饥饿；需要预测下一个CPU Burst的长度（难以实现）。
    
• 预测下一个CPU Burst：使用指数平均法进行预测。
  • τ_{n+1} = α * t_n + (1 - α) * τ_n
    
  • α 决定了近期历史和过去历史在预测中的权重。

3. 优先级调度

• 思想：每个进程有一个优先级，CPU分配给优先级最高的进程。
  
• 特点：
  • SJF是优先级调度的一种特例（优先级 = 预测的CPU Burst时间）。
    
  • 可以是抢占式或非抢占式。
    
  • 问题：饥饿——低优先级进程可能永远得不到执行。
    
  • 解决方案：老化——随着进程等待时间的增加，逐渐提高其优先级。

4. 时间片轮转 RR

• 思想：为每个进程分配一个固定的时间片。进程在时间片用完后被抢占，并放回就绪队列的末尾。
  
• 特点：
  • 专为分时系统设计，注重响应时间。
    
  • 时间片 q 的大小是关键：
    • q 很大 → 退化为FCFS。
      
    • q 很小 → 上下文切换开销过大，系统效率低。
      
  • 优点：公平，每个进程都能定期获得CPU时间。
    
  • 缺点：平均周转时间通常比SJF差。

5. 多级队列

• 思想：将就绪队列划分为多个独立的队列，每个队列代表不同类型的进程（如前台（交互式） 和后台（批处理））。
  
• 特点：
  • 每个队列可以有自己的调度算法（如前台用RR，后台用FCFS）。
    
  • 队列之间也需要调度，通常采用固定优先级（如永远先调度前台队列，可能导致后台队列饥饿）或时间片划分（如80%的CPU时间给前台队列，20%给后台队列）。

6. 多级反馈队列

• 思想：这是最复杂、也最接近现代操作系统的调度算法。它允许进程在队列之间移动。
  
• 典型工作方式：
  1. 系统设有多个队列，优先级从高到低。
     
  2. 每个队列的时间片大小不同（高优先级队列时间片小，低优先级队列时间片大）。
     
  3. 新进程进入最高优先级队列。
     
  4. 如果一个进程在时间片内未完成，它会被降级到下一个优先级队列。
     
  5. 如果一个进程在较低优先级队列中等待了很长时间，可以将其升级到高优先级队列（防止饥饿）。
     
• 优点：
  • 能同时兼顾短作业（能在高优先级队列快速完成）、交互式作业（获得频繁的CPU时间片，响应快）和长作业（最终也能在后台完成）。
    
  • 非常灵活，可配置。

---

5. 其他调度主题

多处理器调度

• 当有多个CPU时，调度变得更复杂。
  
• 负载均衡：将工作负载均匀地分配到所有处理器上。
  
• 对称多处理：所有处理器是同质的，都可以执行内核代码并进行调度。
  
• 非对称多处理：只有一个主处理器负责调度和系统任务，其他处理器只执行用户代码。

实时调度

• 硬实时系统：必须在绝对截止时间前完成任务，否则会导致灾难性后果。
  
• 软实时系统：希望关键任务能得到优先处理，偶尔错过截止时间是可以接受的。

线程调度

• 本地调度：用户级线程库决定将哪个用户线程映射到可用的轻量级进程上。
  
• 全局调度：内核决定调度哪个内核线程执行。

---

6. 实际操作系统示例

Windows

• 使用基于优先级的、抢占式的调度算法。
  
• 支持32个优先级（16-31为实时优先级，0-15为可变优先级）。
  
• 采用多级反馈队列的思想，动态调整线程的优先级（例如，I/O操作完成后会临时提升优先级，以改善交互性）。

Linux

• 在2.6版本之后，采用了效率很高的 CFS（完全公平调度器）。
  
• 核心思想：不是严格分配时间片，而是记录每个进程的虚拟运行时间，总是选择虚拟运行时间最少的进程来执行，从而实现“完全公平”。
  
• 也支持实时调度策略（FIFO和RR），这些实时进程的优先级高于普通进程。

---

7. 算法评估

如何判断一个调度算法好不好？
1. 确定性建模：使用一个预定义的、典型的工作负载，计算并比较不同算法在该负载下的性能指标（如平均等待时间）。
2. 队列模型：使用数学理论和概率论来分析算法的性能。
3. 模拟：编写程序来模拟进程的执行和调度过程，收集性能统计数据。这是最常用和灵活的方法。
4. 实现：直接将算法实现在真实操作系统中，测量其真实性能（代价最高）。

---

本章核心总结

1. CPU调度的目标是在多个进程间高效、公平地分配CPU时间。
   
2. 核心算法：
   • FCFS：简单，但护航效应严重。
     
   • SJF/SRTF：平均等待时间最优，但难以实现，可能导致饥饿。
     
   • 优先级调度：灵活，但也需要处理饥饿问题。
     
   • RR：公平，响应时间好，是分时系统的基石。
     
   • 多级反馈队列：综合性强，是现代操作系统的通用选择。
     
3. 实际系统（如Windows， Linux）采用的都不是单一算法，而是结合了优先级、时间片、反馈等思想的复杂混合算法。
   
4. 评价调度算法需要从CPU利用率、吞吐量、周转时间、等待时间、响应时间等多个维度综合考虑。

---

【补充】第五章：甘特图画法详解

甘特图是用于说明项目进度或进程调度计划的条形图。在CPU调度中，它直观地展示了进程的开始时间、结束时间以及执行顺序。

绘制步骤与规则

1. 确定坐标轴：
   • 横轴（X轴）：代表时间。从0开始，按时间单位（如毫秒）递增。
     
   • 纵轴（Y轴）：代表进程。每个进程占据一行。
2. 绘制条形块：
   • 为每个进程在时间轴上画一个矩形条。
     
   • 条的起点：对应进程开始执行的时间点。
     
   • 条的长度：对应进程本次占用CPU的时间长度（即CPU Burst的长度）。
     
   • 条的终点：对应进程本次执行结束的时间点。
3. 标注信息：
   • 在条的内部或上方，可以标注进程名。
     
   • 在时间轴的关键点（如条的起点和终点）标注具体时间。
     
   • 有时也会在条内标注本次执行的实际时间长度。

经典示例

问题：有三个进程P1、P2、P3，它们的CPU Burst时间分别为24、3、3。它们同时到达（到达时间为0）。使用FCFS算法进行调度。

甘特图绘制：

进程: P1     |======================|  
时间: 0      24                     (P1结束)  

进程: P2            |===|  
时间: 0            24  27           (P2结束)  

进程: P3               |===|  
时间: 0               27  30        (P3结束)  

         |------|-----|-----|  
         0      24    27    30  
          P1    P2    P3  

（更常见的画法是合并成一个图）

甘特图：  

|------|-----|-----|  
| P1   | P2  | P3  |  
|------|-----|-----|  
0      24    27    30  

解释：
* 从0到24时刻，CPU执行P1。
* P1完成后，从24时刻开始执行P2，P2需要3个单位时间，因此在27时刻完成。
* P2完成后，从27时刻开始执行P3，P3需要3个单位时间，因此在30时刻完成。

通过甘特图，我们可以一目了然地看到进程的执行顺序和关键时间点，从而方便地计算周转时间、等待时间等性能指标。例如，P1的等待时间是0，P2的等待时间是24，P3的等待时间是27。