Untitled

基本概念

CPU-I/O 执行周期

进程执行包括周期进行 CPU 执行和 I/O 等待

CPU 执行和 I/O 执行的交替序列

CPU 执行和 I/O 执行的交替序列

CPU 执行时间的直方图

CPU 执行时间的直方图

I/O 密集型程序具有大量短 CPU 执行，CPU 密集型程序可能只有少量长 CPU 执行。

CPU 调度程序

进程选择采用短期调度程序（short-term scheduler）或 CPU 调度程序

抢占调度

  • 需要进行 CPU 调度的情况可以分为四种：
    1. 当一个进程从运行状态切换到等待状态时
    2. 当一个进程从运行状态切换到就绪状态时
    3. 当一个进程从等待状态切换到就绪状态时
    4. 当一个进程终止时

1 和 4 必须要调度，2 和 3 还有其它选择。

如果调度只发生在 1、4 情况下，则调度方案时非抢占的（nonpreemptive）或协作的（cooperative），否则是抢占的（preemptive）。

Dispather

  • Dispatcher 是一个模块，用来将 CPU 控制交给由短期调度程序选择的进程，这个功能包括：
    • 切换上下文
    • 切换到用户模式
    • 跳转到用户程序的合适位置，以便重新启动程序

调度准则

  • CPU 利用率：应使 CPU 尽可能忙碌
  • 吞吐量：一个时间单元内进程完成的数量
  • 周转时间（turnaround time）：从进程提交到进程完成的时间段
  • 等待时间：在就绪队列中等待所花时间之和
  • 响应时间：从提交请求到产生第一响应的时间

希望最大化 CPU 使用率和吞吐量，且最小化周转时间、等待时间和响应时间。

调度算法

先到先服务调度（First-Come First-Served, FCFS）

先请求 CPU 的进程首先分配到 CPU

FCFS 策略的缺点是平均等待时间长

最短作业优先调度（Shortest-Job-First, SJF）

将每个进程与其下次 CPU 执行的长度关联，当 CPU 空闲时，赋给具有最短 CPU 执行的进程

如果两个进程具有相同长度的 CPU 执行，可以由 FCFS 来处理

  • SJF 调度的两种模式：

    • 抢占 SJF：最短剩余时间优先调度（shortest-remaining-time-first）

      Untitled

    • 非抢占 SJF：允许当前运行进程以先完成 CPU 执行

      Untitled

可以证明 SJF 调度算法是最优的，但不能在短期 CPU 调度级别上实现，因为无法预知下次 CPU 执行的长度。

一种方式是近似 SJF 调度，即预测下次 CPU 执行的长度，通常预测为以前 CPU 执行的测量长度的指数平均（exponential average）。

设 tnt_n 为第 nn 个 CPU 的执行长度，设 τn+1\tau_{n+1} 为下次 CPU 执行预测值，定义：

τn+1=αtn+(1−α)τn(0≤α≤1)=αtn+(1−α)tn−1+⋯+(1−α)jαtn−j+⋯+(1−α)n+1τ0\tau_{n+1}=\alpha t_n+(1-\alpha)\tau_n\quad(0\leq\alpha\leq1)\\=\alpha t_n+(1-\alpha)t_{n-1}+\cdots+(1-\alpha)^j\alpha t_{n-j}+\cdots+(1-\alpha)^{n+1}\tau_0

优先级调度（Priority Scheduling）

每个进程都有一个优先级与其关联，具有最高优先级的进程会分配到 CPU

具有相同优先级的进程按 FCFS 顺序调度

SJF 算法是通用优先级调度算法的一个特例

优先级调度算法的主要问题是无穷堵塞（infinite blocking）或饥饿（starvation），即某个低优先级进程可能无穷等待 CPU。

低优先级进程的无穷等待问题的解决方案之一是老化（aging），即逐渐增加在系统中等待很长时间的进程的优先级。

  • 进程优先级的设置可以参照以下原则：
    • 系统进程 > 用户进程
    • 交互型进程 > 非交互型进程
    • I/O 型进程 > 计算型进程

轮转调度（Round-Robin, RR）

轮转调度算法是专门为分时系统设计的

将一个较小时间单元定义为时间量或时间片（10~100ms），CPU 调度程序循环整个就绪队列，为每个进程分配不超过一个时间片的 CPU。

新进程添加到就绪队列的尾部

Untitled

若时间片长度过大，则 RR 调度退化为 FCFS 调度；若时间片长度过小，则需要更多的上下文切换，平均周转时间会增加。

高响应比优先调度

在每次进行调度时，先计算后备作业队列中每个作业的响应比，从中选择响应比最高的作业投入运行

响应比Rp=等待时间+要求服务时间要求服务时间响应比R_p=\frac{等待时间+要求服务时间}{要求服务时间}

要求服务时间越短响应比越高

等待时间越长响应比越高

多级队列调度（Multilevel Queue）

将就绪队列分为多个单独队列，根据进程属性一个进程永久分到一个队列，每个队列有自己的调度算法。

队列之间应有调度，通常采用固定优先级抢占调度

多级反馈队列调度（Multilevel Feedback Queue）

设置多个就绪队列，为各个队列赋予不同的优先级，优先级逐渐降低

允许进程在队列之间迁移

根据不同 CPU 执行的特点来区分进程，如果进程使用过多的 CPU 时间，则会被移到更低的优先级队列。

优先级越高的队列中没和进程的运行时间篇越小

一个新进程进入内存后先放入第一级队列的末尾，按 FCFS 原则排队等待调度，若未在时间片内完成则转入下一级队列末尾

仅当上级队列为空时才会调度本级队列中的进程运行

多处理器调度

非对称多处理（asymmetric multiprocessing）：一个处理器处理所有调度决定、I/O 处理以及其他系统活动，其他处理器只执行用户代码

对称多处理（Symmetric Multiprocessing, SMP）：每个处理器自我调度

实时 CPU 调度

软实时系统（soft real-time system）：不保证会调度关键实时进程，而只保证这类进程会优先于非关键进程

硬实时系统（hard real-time system）：一个任务必须在它的截止期限之前完成

线程调度

进程竞争范围（Process-Contention Scope, PCS）：对于多对一和多对多模型的系统线程库会调用用户级线程，以便在可用 LWP 上运行

系统竞争范围（System-Contention Scope, SCS）：内核采用 SCS 来决定哪个内核级线程调度到一个处理器上，发生在系统的所有线程之间。采用一对一模型的系统只采用 SCS 调度