CPU调度程序 CPU调度准则 调度算法

１.　CPU调度程序

基本概念

  • 多道程序设计的目的将CPU的利用率最大化
  • 多个进程同时存在于内存（并发），当一个进程暂时不用CPU时，系统调度另一个进程占用CPU

  • 进程执行由CPU执行周期和I/O等待周期组成。进程在这两个状态之间切换(CPU burst—I/O bust)。

    抢占调度

  • 非抢占调度：一旦某个进程得到CPU。就会一直占用到终止或等待状态

  • 抢占调度：~~

    CPU的调度准则

  1. CPU利用率
  2. 响应时间：从提交任务到第一次响应的时间
  3. 等待时间：进程累积在就绪队列中等待的时间
  4. 周转时间：从提交到完成的时间
  5. 吞吐率：每个时钟单位处理的任务数
  6. 以合理的方式让各个进程共享CPU

    调度性能指标

  • 作业（job）=进程（process）
  • 假设作业i提交给系统的时刻是ts。完成的时刻是tf，所需运行时间为tk，那么：
  • 平均等待时间：
  • 平均周转时间T（ti是单个作业的周转时间）

  • 2.调度算法

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

  • 定义：先请求CPU的进程先分配到CPU。FCFS策略可以用FIFO队列来容易实现。当一个进程进入就绪队列，其PCB链接到队列的尾部。当CPU空闲时，CPU分配给位于队列头的进程，接着运行进程从队列中删除。

  • FCFS策略的代码编写简单且容易理解，不过采用FCFS策略的平均等待时间通常比较长。当进程CPU区间时间变化很大，平均等待时间会变化很大。

    比如以下例子
    进程 区间时间
    P1 24
    P2 3
    P3 3 如果按照P1 P2 P3 顺序到达，Gantt图如下: image.png 平均等待时间：0+24+273=17 如果按P2 P3 P1 顺序到达， 平均等待时间：0+3+63=3 image.png image.png 从上述两个例子可以发现，FCFS策略和进程顺序有关系

  • 非抢占式算法

  • FCFS的优缺点
    • 简单易行（+）
    • 如果短作业处在长作业的后面将导致周围时间变长。

      护航效果：当所有进程都等待一个大进程释放CPU，称为护航效果

2. 时间片轮转（ROUND ROBIN）

  • 解释：每个进程都可以得到相同的CPU时间（CPU时间片，time slice），当时间片到达，进程将被剥夺CPU并加入就绪队列的尾部。主要是为分时操作系统设计，增加了已抢占以切换进程
  • 抢占式调度算法

  • n个就绪队列中的进程和时间片q =>

    • 每个进程获得1/n的CPU时间，大约是q个时间单位
    • 没有进程等待时间会超过(n-1)q

      image.png

  • 算法分析

    • 时间片的选取：
      • 取值太小：进程切换开销显著增大（不能小于进程切换时间）
      • 取值较大：响应速度下降（取值无穷大将退化成FCFS）
      • 一半时间片的选取范围为10ms~100ms
      • 上下文切换的时间大概为0.1ms~1ms
  • RR算法的优缺点：
  • 公平算法（+）
  • 对长作业带来额外的切换开销（-）

  • RR由于FCFS吗？

    3. 最短作业优先(SJF)算法

  • 解释：下一次调度总是选择需要CPU时间最短的那个作业（进程）。如果两个进程具有同样长度，那么可以按照FCFS调度来处理。

  • image.png
  • 这是一个非抢占式算法，也可以改成抢占式SRTF（最短剩余时间优先调度）。（加入时间片）
  • SJF/SRTF算法分析
    • 该算法总是将短进程移到长进程之前执行，因为平均等待时间最小，该算法被证明式最优的
    • 饥饿现象：长进程可能长时间无法获得CPU（存在大量的短进程）
    • 预测技术：
      • 该算法需要提前知道进程所需的CPU时间
      • 预测一个进程的CPU时间并非易事。

  • 算法的优缺点：

    • 优化了响应时间（+）
    • 难以预测作业CPU时间（-）
    • 不公平算法（-）

      4. 优先级调度

  • 优先级通常为固定区间的数字，预先设定好的优先级规则

    • 数字大小与优先级高低的关系在不同系统中实现不一样，以Linux为例，0为最高优先级
    • 调度策略：下一次调度总是选择优先级最高的进程
    • SJF可以看作优先级调度的一个特例
    • 优先级调度可以是抢占式也可以是非抢占式

      主要问题：容易出现无穷阻塞或饥饿现象 可以运行但是缺乏CPU的进程可认为是阻塞的，一直处于等待CPU。但是对于优先级调度算法会使某个低优先级进程无穷等待CPU。 解决方法：老化（aging），老化是一种技术，已逐渐增加在系统中等待时间长的进程的优先级

5 多级队列调度(Multilevel Queue Scheduling)

系统中不同类型的进程对响应时间和吞吐量有着不同的要求。例如：前台（交互）进程和后台（批处理）进程。这两种不同各类型的进程具有不同响应时间要求，也有不同调度需要。与后台进程相比，前台进程要有更高（或外部定义）的优先级。

  • 解释：

多级队列调度算法将就绪队列分成多个独立队列。根据进程的属性，如内存大小等，一个进程被永久地分配到一个队列(低调度开销但是不够灵活)，每个队列有自己的调度算法。前台队列可能采用RR算法调度，而后台调度可能采用FCFS算法调度。

另外，队列之间必须有调度，通常采用固定优先级抢占调度，例如前台队列可以比后台队列具有绝对优先值。另一种可能在队列之间划分时间片例如，前台队列可以有80%的时间用于在进程之间进行RR调度，而后台队列可以有20%的CPU时间采用FCFS算法调度进程。

6 多级反馈队列调度(Multilevel Feedback-Queue Scheduling)

与多级队列调度相反，多级反馈队列调度允许进程在队列之间移动。主要思想是根据不同CPU区间的特点以区分进程。如果进程使用过多CPU时间，那么它可能被转移到较低优先级队列。这种方案将I/O约束和交互进程留在更高优先级队列。此外，在较低优先级队列中等待时间过长的进程会被转移到更高优先级队列。这种形式的老化组织饥饿的发生。

通常，多级反馈队列调度程序可由下列参数来定义：

  1. 队列数量。<br />    每个队列的调度算法。<br />    用以确定何时升级到更高优先级队列的方法。<br />    用以确定何时降级到更低优先级队列的方法。<br />    用以确定进程在需要服务时应进入哪个队列的方法。

3.线程调度

3.1 scope

系统范围内的竞争（PTHREAD_SCOPE_SYSTEM） SCS
进程范围内的竞争（PTHREAD_SCOPE_PROCESS） PCS
image.png
在Linux中用的是SCS，不支持PCS。1对1模型

调度策略

  1. 正常（normal）调度策略：SCHED_OTHER, SCHED_IDLE, SCHED_BATCH 调度优先级：0（默认优先级）
  2. 实时（real-time）调度策略：SCHED_FIFO, SCHED_RR 调度优先级：1-99（优先级递增）
    1. 实时优先级总是会比normal策略优先级要高

image.png
image.png

调度策略的过程

NORMAL：SCHED_OTHER
分时调度
针对于分时系统
动态优先级（加入了NICE值，PR=20+NICE,PR值越小，优先级越高）
REAL_TIME:
优先级永远高于NORMAL线程（由PR计算方式决定了）
同优先级的线程遵循FIFO