《计算机操作系统》第三章：处理机的调度与死锁

这是一篇关于《计算机操作系统》第三章：处理机的调度与死锁的思维导图。分支内容包括：处理机调度的层次和调度算法的目标、作业与作业调度、进程调度、实时调度、死锁概述。

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

• 3.1 处理机调度的层次和调度算法的目标
  • 3.1.1 处理机调度的层次
    • 高级调度
      • 别名：长程调度、作业调度
      • 对象：作业
      • 位置：外存的后备队列调入内存中
    • 低级调度
      • 别名：短程调度、进程调度
      • 对象：进程
      • 位置：内存的就绪队列分配到处理机
    • 中级调度
      • 别名：内存调度
      • 对象：进程
      • 位置：内存不够时，将处理机中暂时不允许的进程调至外存等待；内存有空闲的时候，将暂停的进程调至内存中
  • 3.1.2 处理机调度算法的目标
    • 1、调度算法的共同目标
      • 资源利用率、公平性、平衡性、策略强制执行
    • 2、不同系统带有不同的设计要求
      • 1、批处理系统目标
        • 平均周转时间短：作业的周转时间包括--外存上后备队列的等待时间、进程再就绪队列等待的时间、进程在CPU运行时间、进程等待IO操作的时间
        • 系统吞吐量：只单位i时间系统完成的作业数
        • 处理机利用率
      • 2、分时系统目标：响应时间快、均衡性
      • 3、实时系统目标：截至时间的保证、可预测性
• 3.2 作业调度（高级调度）
  • 3.2.1 作业的相关概念
    • 作业：作业比程序的概念更广泛，它=程序+数据+作业说明书
    • 作业步：指作业运行期间，每个作业必须经过若干个相对独立的步骤完成，这些步骤就是作业步
    • 作业控制块：JCB，唯一的标志一个作业。JCB的具体内容差不多与PCB类似
    • 作业阶段和状态：收容阶段（后备状态）、运行阶段（运行状态）、完成阶段（完成状态）
  • 3.2.2 作业调度的任务：将作业从外存的后备队列调度到内存，然后为其创建进程、分配资源，再将进程安排到内存上的就绪队列上等待进程调度
    • 关键决定
      • 1、一次接纳多少作业
      • 2、选择哪些作业接纳进来
  • 3.2.3 调度算法
    • 1、先来先服务FCFS
      • 优先级依据：作业的等待时间越长，优先级越高
    • 2、短作业优先SJF
      • 优先级依据：作业的运行时间越短，优先级越高
    • 3、优先级调度PSA算法
      • 优先级依据：作业的情况越紧急，优先级越高
    • 4、高响应比优先调度HRRN算法
      • 优先级依据：结合作业的等待时间和运行时间的动态优先级（随着时间的推迟，动态优先级会变大）
• 3.3 进程调度（低级调度）
  • 3.3.1 进程调度的任务、机制和方式
    • 任务：保存处理机的现场信息、按某种算法选择进程、把处理机分配给进程
    • 机制
      • 排队器：事先将系统中所有的就绪进程按照一定的策略排成一个或多个队列
      • 分派器：依据调度算法选择进程，将其从就绪队列中选出
      • 上下文切换器
        • 1、保存当前进程的上下文，再装入分派程序的上下文
        • 2、移出分派程序的上下文，将新选进程的CPU现场信息装回
    • 调度方式
      • 抢占式：进程运行期间可以被其他高优先的进程抢占
      • 非抢占式：一旦将处理机分配给进程，就一直让他运行到结束，除非发送异常事件、提出IO请求、执行了某些原语操作而停止下来
      • 针对其他进程能否抢占
  • 3.3.2 调度算法
    • 1、轮转调度算法RR
      • 基于每个进程运行相同的时间片
    • 2、优先级调度算法PSA
      • 引入优先级
      • 优先级调度算法的类型
        • 非抢占式优先级调度算法
        • 抢占式优先级调度算法：进程执行期间出现优先级比它高的进程，调度程序就会将处理机分配给对方
      • 优先级分类
        • 静态优先级：在创建进程时确定的，在进程的整个运行期间保持不变
        • 动态优先级：能够随着进程的推进或等待时间的增加而改变
    • 3、多队列调度算法
      • 概念：一种能够融合多种调度算法的方式
      • 调度机制：将系统中的就绪进程分为多个队列，每个队列可以采用不同的具体的调度算法
    • 4、多级反馈队列调度算法
      • 概念:：不需要事先知道各种进程的执行时间，通过反馈来进行调度
      • 调度机制
        • 1、设置多个就绪队列，每个队列拥有不同的优先级，优先级高的队列，时间片越小
        • 2、每个队列都采用FCFS算法，对于新进程进入内存后，将其置于优先级第一的队列，当采用FCFS轮到该程序执行时，若未在规定时间片完成，调度程序回将其剩余部分置于优先级第二队，一直如此操作。
        • 3、按队列优先级调度，即调度程序每次都会运行高优先级队列，且支持抢占式
    • 5、基于公平原则的调度算法
      • 保证调度算法
        • 公平对象：进程
      • 公平共享调度算法
        • 公平对象：用户
• 3.4 实时调度（实时系统的调度）
  • 3.4.1 实时调度的基本条件
    • 1、提供必要的信息：截止时间、就绪时间、处理时间、资源要求、优先级
    • 2、系统处理能力强处理机能力不够强，很容易到导致处理机忙不过来，出现部分实时任务超过截止时间
    • 3、采用抢占式调度方式：主要是非抢占式很容易导致超过截止时间
    • 4、快速切换机制：保证实时任务及时运行，具有快速切换
      • 对中断快速响应
      • 快速的任务分派能力
  • 3.4.2 实时调度算法的分类
    • 1、按实时任务性质任务分类
      • 硬实时调度算法
      • 软实时调度算法
    • 2、按调度方式的分类
      • 非抢占式调度算法
        • 非抢占式轮转调度算法
        • 非抢占式优先级调度算法
      • 抢占式掉调度算法
        • 基于时钟中断的抢占式优先级调度算法
        • 立即抢占的优先级调度算法
  • 3.4.3 调度算法
    • 1、最早截止时间优先EDF算法
      • 优先级依据：任务的截止时间越早，其优先级越高
      • 分类
        • 非抢占式
        • 抢占式
    • 2、最低松弛度优先LLF算法
      • 优先级依据：任务的紧急（松弛）程度，任务越紧急（弛），优先级越高
      • 松弛度的计算：必须完成的时间-其本身运行的时间-当前时间
      • 关键：算法会全程计算所有进程的松弛度，并支持抢占式的
  • 3.4.4 优先级倒置问题
    • 优先级倒置问题的描述
      • 概念：指低优先级的进程比高优先级的进程先执行完毕
      • 出现的基本条件：必须采用优先调度算法和支持抢占方式，才有可能导致优先级倒置
      • 原因：低优先级和高优先级进程共享“临界资源”，低优先级先占用临界资源，又被中间优先级的进程抢占了低优先级，延长了结束临界资源的时间，高优先级抢占中间优先级后发现，临界资源被占用，只能先让中间优先级完成，再让低优先级完成后释放资源
    • 优先级倒置的解决方法
      • 1、简单规定：进程进入临界资源后就不允许被抢占，直到临界资源被释放
      • 2、动态优先级继承：高优先级进程发现临界资源被阻塞的低优先级所使用，于是将高优先级继承给低优先级，使它先运行完毕。释放临界资源并返回优先级
• 3.5 死锁概述
  • 3.5.1 资源问题
    • 讨论一下资源的种类，其中引起死锁得主要是不可抢占式资源和消耗性资源
    • 可重用资源与消耗性资源
      • 可重用资源：可供用户重复多次使用得资源，特征
        • 1、该资源的每一个单位仅能分配给一个单位
        • 2、系统中每一类可重用资源的单元数目都是固定的，进程运行期间不能创建和删除它
      • 可消耗性资源：又称临时资源，在进程运行期间动态的创建和删除的，特征
        • 1、资源的单元数目不固定
        • 2、进程可以创建资源单元，放进该资源的缓冲区
        • 3、进程可以请求资源单元，且使用完后不用返回资源
    • 抢占式与非抢占式资源（见之前的描述）
  • 3.5.2 计算机系统的死锁
    • 死锁的产生的原因
      • 竞争资源引起的死锁
        • 竞争不可抢占式资源引起的死锁：双方都占有对方想要的资源，同时又想要使用对方的资源，进入死循环
        • 竞争消耗性资源引起的死锁：双方都请求对方进程还未执行的创建的资源
      • 进程推进顺序不当引起的死锁
  • 3.5.3 死锁的定义、必要条件和处理方法
    • 死锁的定义：一组进程中每一个进程都在等待仅有该组进程中的其他进程才能引发的事件，那么该组进程就是死锁的
    • 死锁的必要条件
      • 互斥条件：指占用的资源是互斥使用，只能被一个进程使用，其余进程只能等待
      • 请求和保持：进程已经保持了一个资源，又一直请求另一个资源
      • 不可抢占条件：资源在未使用完之前不能被抢占，仅能自己释放掉
      • 循环等待条件：发生死锁时间，一定存在一个进程-资源的循环链路
    • 死锁的处理方法：预防、避免、检测和解除
      • 从预防到最后的解除，对死锁的防范程度逐渐减弱，但是对于的资源利用率提高，以及进程因资源因素而阻塞的频度下降
• 3.6 预防死锁
  • 互斥条件：是非共享资源所必须的，不能破坏，还必须加以保证
  • 3.6.1 破坏”请求和保持“条件
    • 第一种协议：系统有足够的资源时，进程一次将需要的资源全部请求过来，这样就不会有请求的机会。代价过大
    • 第二种协议：允许进程按阶段逐步分配一批所需资源。
  • 3.6.2 破坏”不可抢占“条件
    • 协议规定：当一个进程保持某些不可抢占资源时，提出新的资源请求没有满足时，它必须释放已经保持的资源
  • 3.6.3 破坏”循环等待“条件
    • 协议规定：所有资源类型都进行线性排序，规定每个进程都必须按序号的递归请求资源。由于序号是线性排序的，所以是无法构成循环的状态
• 3.7 避免死锁
  • 基本思想：系统计算分配此次资源，系统能否有进入安全状态的机会，没有则拒绝本次资源的分配
  • 3.7.1 系统安全状态
    • 安全状态：指计算机按照某个进程推进顺序分配资源，直至满足每个进程的最大需求，是每个进程都可以顺利完成，那么这样的顺序就是安全状态
    • 安全状态举例：主要是通过进程推进顺序，能满足一个进程的资源需要，就分配资源，在完成该进程后，释放所有的资源，然后再分配给下一个进程满足其最大需求
  • 3.7.2 避免死锁算法
    • 银行家算法
      • 1、数据结构：可利用资源向量、最大需求矩阵、已分配矩阵、尚需求矩阵
      • 2、银行家算法的过程
        • a、如果请求向量小于对应的尚需求资源，便转向下一步骤，否则出错
        • b、如果请求向量小于对应的可利用资源，便转向下一个资源，否则等待
        • c、尝试分配，并重新计算可利用资源、已分配资源、尚需求资源
        • d、系统执行安全算法，检查本次分配后系统是否处于安全状态
          • 若安全，则完成此次分配
          • 若不安全，本次的试探分配失效，恢复原来的数据结构，重新尝试分配
      • 3、安全算法
• 3.8 死锁的检测与解除
  • 3.8.1 死锁的检测
    • 检测的基本条件
      • 1、保存有关资源的请求和分配信息
        • 1、资源分配图：利用有向图来表示进程和资源之间的分配和请求
      • 2、提供算法来检查是否进入死锁
        • 1、检测的机制--死锁定理：将资源分配图中进行简化，找到一个不阻塞且非独立的进程结点，删除所有的边，一直循环所有进程结点，若到最后未能消除所有的边，则是不可完全简化的图，对应的就是死锁
  • 3.8.2 死锁的解除
    • 1、终止进程的方法
      • 1、终止所有死锁的进程，但是代价太大，因为有的进程已经运行很久了，已接近结束
      • 2、逐个终止进程：按照某个顺序终止进程，直至有足够的资源打破循环等待后，把系统从死锁中解除
        • 代价也可能很大：因为要常使用死锁检测算法确定系统死锁是否已经解说
        • 代价最大：优先级越大、执行时间越久、剩余执行时间越短、使用资源越多，还需资源越少，交互式的进程被终止，代价是很大的
    • 2、付出最小代价的死锁解除算法
      • 1、逐层的尝试解除：即从第一层开始到第n层尝试解除，在第一层采取只终止一个进程的方式，所有的可能的终止方式都尝试一下，记录解除死锁的方式和该方式下的代价，如果有解除死锁的多个方式，那比较代价，哪种方式代价下就采用那种方式。如果本层未有解除死锁的，尝试第二层下，终止两个进程的方式，一直循环到解除为止
      • 2、在逐层尝试解除的基础上添加最小代价队列