第三章:处理机调度与死锁

处理机调度算法的目标

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

• 资源利用率:CPU的利用率=CPU有效工作时间/(CPU有效工作时间+CPU空闲等待时间)
• 公平性
• 平衡性
• 策略强制执行

批处理系统的目标

• 平均周转时间短
• 系统吞吐量高
• 处理机利用率高

分时系统的目标

• 响应时间快
• 均衡性

实时系统目标

• 截止时间的保证
• 可预测性

处理机调度的层次

• 高级调度（作业调度）
  • 分时系统无需作业调度，因为需要交互
  • 批处理系统需要作业调度
• 中级调度（和挂起有关）
• 低级调度（进程调度）
  • 进程调度是最基本的调度，任何操作系统都有进程调度。
  • 低级调度的三个基本机制
    • 排队器
    • 分派器
    • 上下文切换
  • 进程调度方式
    • 非抢占方式
    • 抢占方式
      • 优先权原则
      • 短进程优先原则
      • 时间片原则
  • 进程调度的任务
    • 保存处理机的现场信息
    • 按某种算法选取进程
    • 把处理器分配给进程
  • 进程调度的算法
    • 优先级调度算法
      • 优先级调度算法的类型
        • 非抢占式优先级调度算法
          • 等当前进程执行完以后，再执行另一个优先权最高的进程
          • 这种调度算法主要用于批处理系统中；也可用于某些对实时性要求不严的实时系统中。
        • 抢占式优先级调度算法
          • 不等当前进程结束，直接抢处理机
          • 常用于要求比较严格的实时系统中， 以及对性能要求较高的批处理和分时系统中。
      • 优先级的类型
        • 静态优先级
          • 优先权是在创建进程时确定的，且在进程的整个运行期间保持不变。一般地，优先权是利用某一范围内的一个整数来表示的，例如，0_7或0255中的某一整数， 又把该整数称为优先数。
          • 可以参考BIOS系统中设置boot的优先级
        • 动态优先级
          • 在创建进程时所赋予的优先权，是可以随进程的推进或随其等待时间的增加而改变的，以便获得更好的调度性能。
    • 轮转调度算法
      • 基本原理:在轮转(RR)法中，系统根据FCFS策略，将所有的就绪进程排成一个就绪队列，并可设置每隔一定时间间隔(如30ms)即产生一次中断，激活系统中的进程调度程序，完成一次调度，将CPU分配给队首进程，令其执行
      • 进程切换时机
        • 时间片未用完，进程完成
        • 时间片到，进程未完成
      • 时间片大小的确定
        • 太小利于短作业，增加系统切换开销
        • 太长就退化为FCFS算法
        • 一般选择: q略大于一次交互所需要的时间，使大多数进程在一个时间片内完成
      • 一般来说，平均周转时间将比SJF长，但是有较好的响应时间
    • 多队列调度算法
    • 多级反馈队列调度算法
      • 调度机制
        • 设置多个就绪队列
        • 每个队列都采用FCFS算法
        • 按照队列优先级调度，在第n队列中采取按时间片轮转的方式运行
      • 调度算法的性能
        • 对于终端型用户，由于作业小，感觉满意
        • 对于短批处理作业用户，周转时间也较小
        • 长批处理作业用户，也能够得到执行
    • 基于公平原则的调度算法
      • 保证调度算法
      • 公平分享调度算法

作业与作业调度

作业

• 作业不仅包含程序和数据，还配有一份作业说明书，系统根据说明书对程序的运行进行控制。批处理系统是以作业为单位从外存掉入内存的。

作业控制块JCB

• 为每个作业设置一个JCB，保存了对作业管理调度的全部信息。是作业存在的标志。

作业步

• 作业步，每个作业都必须经过若干相对独立，有相互关联的顺序步骤才能得到结果。每一个步骤就是一个作业步。

作业运行的三个阶段

• 收容阶段
• 运行阶段
• 完成阶段

作业运行的三个状态

• 后备状态
• 运行状态
• 完成状态

作业调度的主要任务

• 接纳多少个作业
• 接纳哪些作业

先来先服务(first–come first–served，FCFS)调度算法

• 比较有利于长作业，而不利于短作业。
• 有利于CPU繁忙的作业，而不利于I/O繁忙的作业。

短作业优先(short job first，SJF)的调度算法

• 优点
  • 比FCFS改善平均周转时间和平均带权周转时间，缩短作业的等待时间；
  • 提高系统的吞吐量；
• 缺点
  • 必须预知作业的运行时间
  • 对长作业非常不利，长作业的周转时间会明显地增长
  • 在采用SJF算法时，人–机无法实现交互
  • 该调度算法完全未考虑作业的紧迫程度，故不能保证紧迫性作业能得到及时处理

优先级调度算法(priority–scheduling algorithm，PSA)

高响应比优先调度算法(Highest Response Ratio Next,HRRN)

• 原理
  • 在每次选择作业投入运行时，先计算此时后备作业队列中每个作业的响应比RP然后选择其值最大的作业投入运行
  • 优先权=(等待时间+要求服务时间)/要求服务时间=响应时间/要求服务时间=1+等待时间/要求服务时间
• 特点
  • 如果作业的等待时间相同，则要求服务的时间愈短，其优先权愈高，因而类似于SJF算法，有利于短作业
  • 当要求服务的时间相同时，作业的优先权又决定于其等待时间，因而该算法又类似于FCFS算法
  • 对于长时间的优先级，可以为随等待时间的增加而提高，当等待时间足够长时，也可获得处理机

实时调度(HRT和SRT任务)

实现实时调度的基本条件

• 提供必要信息
  • 就绪时间
  • 开始截止时间和完成截止时间
  • 处理时间
  • 资源要求
  • 优先级
• 系统处理能力强
  • ∑(Ci/Pi)≤1
  • N个处理机:∑(Ci/Pi)≤N
• 采用抢占式调度机制
• 具有快速切换机制
  • 对中断的快速响应能力
  • 快速的任务分派能力

实时调度算法的分类

• 非抢占式调度算法
  • 非抢占式轮转调度算法
  • 非抢占式优先调度算法
• 抢占式调度算法
  • 基于时钟中断的抢占式优先级调度算法
  • 立即抢占的优先级调度算法

最早截止时间优先EDF(Earliest Deadline First)算法

• 根据任务的开始截至时间来确定任务的优先级
  • 截至时间越早，优先级越高
• 非抢占式调度方式用于非周期实时任务
• 抢占式调度方式用于周期实时任务

最低松弛度优先LLF(Least Laxity First)算法

• 类似EDF
• 算法根据任务紧急(或松弛)的程度，来确定任务的优先级。任务的紧急程度愈高，为该任务所赋予的优先级就愈高， 以使之优先执行。
• 松弛度例子
  • 例如，一个任务在200ms时必须完成，而它本身所需的运行时间就有100ms，因此，调度程序必须在100 ms之前调度执行，该任务的紧急程度(松弛程度)为100 ms

优先级倒置(Priority inversion problem)

• 优先级倒置的形成
  • 高优先级进程被低优先级进程延迟或阻塞。
• 优先级倒置的解决方法
  • 简单的:假如进程P3在进入临界区后P3所占用的处理机就不允许被抢占
  • 实用的:建立在动态优先级继承基础上的

死锁概述

资源问题

• 可重用性资源
  • 计算机外设
• 消耗性资源
  • 数据，消息
• 可抢占性资源
  • 不引起死锁
  • CPU，内存
• 不可抢占性资源
  • 光驱，打印机

计算机系统中的死锁

• 竞争不可抢占性资源引起死锁
• 竞争可消耗资源引起死锁
• 进程推进顺序不当引起死锁

死锁的定义，必要条件和处理方法

• 定义:如果一组进程中的每一个进程都在等待仅由该进程中的其他进程才能引发的事件，那么该组进程是死锁的
• 产生死锁的必要条件
  • 互斥条件
  • 请求和保存条件
  • 不可抢占条件
  • 循环等待条件
    • 如果每个资源只有一个实例，则环路等待条件是死锁存在的充分必要条件
• 处理死锁的方法
  • 预防死锁
    • 静态方法，在进程执行前采取的措施，通过设置某些限制条件，去破坏产生死锁的四个条件之一，防止发生死锁。
    • 预防死锁的策略
      • 破坏"请求和保存"条件
        • 第一种协议
          • 所有进程在开始运行之前，必须一次性地申请其在整个运行过程中所需的全部资源
          • 优点:简单，易行，安全
          • 缺点
            • 资源被严重浪费，严重地恶化了资源的利用率
            • 使进程经常会发生饥饿现象
        • 第二种协议
          • 它允许一个进程只获得运行初期所需的资源后，便开始运行。进程运行过程中再逐步释放已分配给自己的，且已用毕的全部资源，然后再请求新的所需资源
      • 破坏"不可抢占"条件
        • 当一个已经保存了某些不可被抢占资源的进程，提出新的资源请求而不能得到满足时，它必须释放已经保持的所有资源，待以后需要时再重新申请
      • 破坏"循环等待"条件
        • 对系统所以资源类型进行线性排序，并赋予不同的序号
        • 例如令输入机的序号为1，打印机序号为2，磁盘机序号为3等。所有进程对资源的请求必须严格按资源序号递增的次序提出。
  • 避免死锁
    • 动态的方法，在进程执行过程中采取的措施，不需事先采取限制措施破坏产生死锁的必要条件，而是在进程申请资源时用某种方法去防止系统进入不安全状态，从而避免发生死锁。如银行家算法
    • 避免死锁的策略
      • 系统安全状态
        • 安全状态
          • 某时刻，对于并发执行的n个进程，若系统能够按照某种顺序如<p1,p2…pn>来为每个进程分配所需资源，直至最大需求，从而使每个进程都可顺利完成，则认为该时刻系统处于安全状态，这样的序列为安全序列
        • 安全状态之例
        • 由安全状态向不安全状态的转换
      • 利用银行家算法避免死锁
        • 含义:每一个新进程在进入系统时，它必须申明在运行过程中，可能需要每种资源类型的最大单元数目，其数目不应超过系统所拥有的资源总量。当进程请求一组资源时，系统必须首先确定是否有足够的资源分配给该进程。若有，再进一步计算在将这些资源分配给进程后，是否会使系统处于不安全状态。如果不会，才将资源分配给它，否则让进程等待
        • 银行家算法中的数据结构
          • 可用资源向量 Available[m]：m为系统中资源种类数，Available[j]=k表示系统中第j类资源数为k个。
          • 最大需求矩阵 Max[n,m]：n为系统中进程数，Max[i,j]=k表示进程i对j类资源的最大需求数为中k。
          • 分配矩阵 Allocation[n，m]:它定义了系统中每一类资源当前已分配给每一进程资源数， Allocation[i,j] = k表示进程i已分得j类资源的数目为k个。
          • 需求矩阵 Need[n,m]：它表示每个进程尚需的各类资源数，Need[i,j]=k 表示进程i 还需要j类资源k个。Need[i,j]=Max[i,j] - Allocation[i,j]
        • 银行家算法
        • 安全性算法
        • 银行家算法之例
        • 解题
          • 矩阵
          • 列表
  • 检测死锁
    • 死锁的检测与解除
      • 死锁的检测
        • 资源分配图
          • 简化步骤
            • 选择一个没有阻塞的进程p
            • 将p移走，包括它的所有请求边和分配边
            • 重复步骤1，2，直至不能继续下去
        • 死锁定理
          • 若一系列简化以后不能使所有的进程节点都成为孤立节点
        • 检测时机
          • 当进程等待时检测死锁 （其缺点是系统的开销大）
          • 定时检测
          • 系统资源利用率下降时检测死锁
        • 死锁检测中的数据结构
      • 死锁的解除
        • 抢占资源
        • 终止(或撤销)进程
        • 终止进程的方法
          • 终止所有死锁进程
          • 逐个终止进程
            • 代价最小
              • 进程的优先级的大小
              • 进程已执行了多少时间，还需时间
              • 进程在运行中已经使用资源的多少，还需多少资源
              • 进程的性质是交互式还是批处理的
        • 付出代价最小的死锁解除算法
          • 是使用一个有效的挂起和解除机构来挂起一些死锁的进程
  • 解除死锁

第三章 处理机调度与死锁