（二）CPU 调度与上下文切换

1. CPU 调度

1.1. 调度的基本概念

• 调度的实质是一种 资源分配

• 处理机调度具有对应的 算法

1.2. 处理机调度的层次

• 高级、中级、低级调度（High Level，Intermediate，Low Level）；

• 中级调度基本不考，其本质是进程的 挂起与激活

• 高级调度一般称为 “作业”，指要运行的程序所需的资源，存储在外存；

• 低级调度一般是 “进程” 层面的调度，在内存；

1.3. 调度的目标

• 处理机调度算法的共同目标

  • 提高处理机和资源的利用率

  • 公平性：各个进程都应获得 合理 的 CPU 时间；

    • 合理 ≠ 平均，其也取决于进程优先级和作业紧急程度等；

  • 平衡性：平衡 IO 型和计算型作业，使 CPU 和 IO 设备都尽可能忙碌；

  • 强制性策略：例如某些安全策略，必须按照要求执行（即使会影响其他工作）；

• 批处理系统的调度目标

  • 作业的平均周转时间短；

    • 作业的带权周转时间 $W$ ：$W=T_i/T_s$，其中 $T_i$ 为周转时间，$T_s$ 为 OS 为此作业提供服务的时间；

      • 注意带权周转时间不用乘上周转时间，就是 $W=T_i/T_s$ ！；

    • 平均带权周转时间；

  • 系统吞吐量高；

  • 处理机利用率高；

• 分时系统的调度目标：(1 )响应时间快，(2) 均衡性；

• 实时系统的调度目标：(1) 保证截止时间，(2) 可预测性；

1.4. 调度的实现

• 进程调度的 3 个任务

  • 保留现场信息；

  • 按照调度算法选取进程；

  • 将处理机分配给进程；

• 调度方式

  • 非抢占方式（Nonpreemtive Mode）：一旦分配完成，将让 当前进程一直运行下去，直到进程完成或阻塞，不会因为其他原因抢占进程执行；

  • 抢占式（Preemtive Mode）：可以根据规则，暂停某个正在运行的进程，将处理机重新分配；

    • 被暂停的进程要放回 就绪队列；

    • 现代 OS 基本采用抢占式，防止某进程长时间占用 CPU；

    • 分时系统中，只有抢占式能实现 人机交互；

    • 实时系统中，只有抢占式能满足 实时任务的需求；

    • 抢占式实现比较复杂，开销比较大

• 闲逛进程（Idle Process）：CPU 没有任务时就运行 Idle Process；

1.5. 典型调度算法

• 先来先服务算法（FCFS）

  • 可用于作业和进程调度；

  • 按照作业到达的先后次序调度，或优先调度 等待时间最长 的作业；

• 短作业优先算法（SJF）

  • 可用于作业和进程调度；

  • 作业所要求的运行时间越短，优先级越高；

  • 依据：实际情况中，短作业（进程）占有很大比例；

  • 缺点：(1) 必须事先知道作业的运行时间，而这个时间一般很难准确估算，(2) 长作业周转时间会明显增加，对长作业非常不利，(3) 没有考虑作业的 紧迫性；

• 高相应比优先调度算法

  • 可用于作业和进程调度；

  • 引入动态优先级：优先级 $P=$ (已等待时间 + 要求服务时间) / 要求服务时间；

    • 随等待时间延长，$P$ 必然增加，足够时间后进程必然可以获得处理机；

    • $P=R_p$，$R_p$ 是相应比，$R_p=$ 响应时间 / 要求服务时间；

  • 优点：

    • 有利于短作业优先处理，实现了 SJF；

    • 服务时间相同时，$P$ 取决于等待时间，实现了 FCFS；

    • 长作业等待足够时间后也能得到处理；

• 轮转调度算法（RR）

  • 可用于作业和进程调度；

  • 内容

    • 所有就绪进程按照 FCFS 形成一个就绪队列；

    • 每隔一定时间（如 30ms），OS 产生一次中断，激活调度程序，将 CPU 分配给队首进程，让其执行一个时间片，队首进程变为下一个，如此循环；

    • 能保证队列中所有进程在确定时间段内都能得到一定的 CPU 时间；

  • 进程切换机制

    • 若在时间片用完前，进程已完成，则立即激活调度程序进行切换；

    • 若时间片用完后，进程未完成，激活调度程序切换，将当前进程送至队尾；

• 优先级调度算法

  • 可用于作业和进程调度；

  • 将处理机分配给队列中优先级最高的进程，又可分为抢占式和非抢占式；

  • 优先级分类

    • 静态优先级：创建进程时决定，进程运行过程中不变；一个 0~255 的整数（优先数）；

      • 依据：(1) 进程类型，(2) 进程对资源的需求，(3) 用户需求；

    • 动态优先级：创建进程时给定，随进程推进或等待时间增加而改变；

• 多队列调度算法

  • 可用于作业和进程调度；

  • 设置多个就绪队列；

    

    • 每个队列都采用 FCFS，且就绪队列 1 到 n，优先级依次降低；

    • 每个就绪队列采用轮转调度方式，且时间片从 1 到 n 依次增大；

    • 除最后一个队列外，轮转作业的迁移是从队列 $i$ 队尾到 $i+1$ 队首；

  • 调度方式

    • 仅当优先级较高的队列空闲时，才调度低优先级队列运行；

    • 若低优先级队列的作业执行时遇到新作业进入高优先级队列，则立即暂停当前作业执行，并重新分配处理机（抢占式）；

  • 适用情况：当 队列 1 的时间片 $S_1$ 略大于大多数人机交互操作的时间 时，此调度方式能够较好地满足各类用户（终端型，短作业型，长作业型）的需要；

2. 上下文及其切换机制

• 进程调度机制的 3 个基本部分：(1) 排队器，(2) 分配器，(3) 上下文切换器；