兰斯小窝

Appearance

ch5 CPU调度 ​

5.1 基本概念 ​

  1. CPU-I/O区间周期
    • CPU成功调度依赖于进程执行的如下特性：进程执行由CPU执行和I/O等待周期组成，进程在这两个状态之间切换。最终，最后的CPU区间通过系统请求终止执行
    • CPU约束程序（CPU-bound process）：I/O请求并不频繁，花费更多的时间在计算上
    • I/O约束程序（I/O-bound process）：相比于计算，花费更多时间在I/O上
  2. CPU调度程序
    • CPU调度程序（也称之为短期调度程序）负责在CPU空闲的时候，从就绪队列中选择合适的进程分给CPU，就绪队列中等待的记录通常是进程控制块（PCB）
  3. 调度的时机和抢占的时机
    • 调度时机可以发生在如下几种情况：
      1. 当一个进程从运行状态切换到等待状态（例如I/O请求，或者等待子进程结束）
      2. 当一个进程从运行状态切换到就绪状态（例如，当出现中断）
      3. 当一个进程从等待状态切换到就绪状态（例如，当I/O完成）
      4. 当一个进程结束
    • CPU的调度策略分为抢占（preemptive）和非抢占（non-preemptive），在CPU调度实际2、3时可以发生抢占，不难看出就是由新进程添加进就绪队列的时候，可以发生抢占，不难看出就是有新进程添加进入就绪队列的时候，可以发生抢占
    • 抢占对于共享数据是有代价的，可能造成数据的不一致，这就涉及到第六章的内容
  4. 分派程序（dispatcher）
    • 分派程序时CPU调度的一个部分，他负责将CPU的控制权交给由CPU调度程序选择的进程，包括：
      1. 切换上下文
      2. 切换用户模式
      3. 跳转到用户程序的合适位置，以重新启动程序

5.2 调度的准则 ​

  1. 准则:
    1. CPU使用率：需要使CPU尽可能地忙碌
    2. 吞吐量（Throughput）：指一个单位时间内完成的进程的数量
    3. 周转时间：从进程提交到进程完成的时间
    4. 等待时间：在就绪队列中等待花费的时间的总和
    5. 响应时间：从提交请求到产生第一响应的时间
  2. 关于准则的声明
    • 需要使CPU的使用率和系统的吞吐量最大化，周转时间、等待时间、响应时间最小化。
    • 为了使吞吐量最大化，系统要平衡CPU约束程序和I/O约束程序，不能让CPU一直忙碌，或者一直空闲
    • 周转时间 = 等待时间 + 执行时间 = 结束时间 - 进入就绪队列时间

5.3 调度算法 ​

  1. 先到先服务调度算法（first-come first-serve, FCFS）
    • 这个算法很容易理解，也很容易实现，但是平均等待时间通常会较长 alt text
    • FCFS的弊端从甘特图中就能看出来，如果先调度p2和p3就能大幅减少平均等待时间
    • 所以FCFS调度算法的平均等待时间和进入队列的顺序有关，平均等待时间较长
    • 而且当执行一个大进程时，所有的进程都要等待大进程释放CPU，称之为护航效应
  2. 最短作业优先调度算法（Shortest-job first, SJF）
    • SJF调度就是从就绪队列中调度最短的CPU区间进程执行，如果有多个满足条件的进程则按照FCFS的策略调度 alt text
    • SJF算法的平均等待时间时最小的，同时系统吞吐量增加
    • 有利于短进程，但是不利于长进程，长进程可能会导致饥饿
    • 困难在于很难知道下一个CPU区间的长度，很难实现
    • 适用于长期调度
  3. 抢占的SJF调度算法——最短剩余时间优先调度算法（Shortest-remaining-time-first, SRTF）
    • 当前面介绍的CPU抢占的时机发生时，这个时候进程调度的时候就要考虑新添加进来的pi的CPU区间时间和当前正在执行pj的剩余时间的大小，如果pi < pj，则发生抢占 alt text
    • 实例说明：2.0时刻，p2进入就绪队列，满足抢占的条件，这个时候p1的剩余时间是5，p2的CPU区间时间是4，所以p2抢占p1。4时刻p3进入就绪队列满足抢占的条件，这个时候p2的剩余时间是2，p3的CPU区间时间是1，所以p3抢占p2。后面的分析如上
  4. 优先级调度算法（priority）
    • 每个进程都和一个优先级对应，高优先级的进程比低优先级的进程更早得到CPU的调度。具有相同优先级的进程，按照FCFS调度。我们可以将SJF调度视为一种简单的优先级调度，他的优先级同CPU区间时间成反比。（小数字优先级高） alt text
    • p4的CPU区间最短，但是由于优先级时最低的，所以最后才会被调度，这就造成了很长时间的等待。这就是优先级调度的一个问题——饥饿现象
    • 饥饿现象：可以运行但是一直得不到CPU调度
    • 解决饥饿问题：可以采用老化（aging）技术，逐渐增加在系统中等待很长时间的进程的优先级
  5. 轮转调度法（round-robin，RR）
    • 类似于FCFS，但是增加了抢占以切换进程
    • 抢占的机制是定义一个较小的时间单元称之为时间片，当分配给一个进程的时间片结束以后，切换进程。如果进程在时间片内运行结束，那么多余的时间片回收然后切换进程 alt text
    • 实例说明：p1执行完4个单位的时间片后，切换到进程p2，p2运行3个时间单位结束，剩余的时间片自动释放。p3运行3个时间单位后结束，释放剩余的时间片。
    • RR算法性能很大程度上取决于时间片的大小。RR算法在FCFS基础上改进，改进了”护航效应“，但是仍然存在平均等待时间较长的缺点
  6. 多级队列调度算法和多级反馈队列调度
    • 多级队列调度算法：将就绪队列分为多喝独立队列，每个队列都有自己的调度算法，每个队列与更低队列想必都哦哟绝对的优先级
    • 多级反馈队列：允许进程在队列之间进行移动，在优先级较低的队列中等待时间过长的进程会被转移到更高优先级的队列里，这种形式的老化可以组织饥饿

5.4 多处理器调度 ​

  • 多处理器分为对称多处理（SMP）和非对称多处理（AMP）
  • 处理器亲和性：努力让一个进程在同一个处理器上运行，避免进程在处理器之间转移
  • 负载平衡：设法将工作负载平均的分配到SMP系统中的所有处理器上

5.5 例题 ​