Computer_Network-LinkLayer

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

• 处理机调度的层次
  • 高级调度（长程调度/作业调度） ： 调度对象 为作业； 主要职责 是从后备队列中选择新的进程，将它们调度到内存中准备执行； 调度时间尺度 较长，以分钟为单位，主要用于多道批处理系统中，在分时和实时系统中不设置高级调度
  • 中级调度（中程调度/内存调度） ： 调度对象 为内存中的进程； 主要职责 是管理内存中的进程，提高内存利用率和系统吞吐量，将不活跃的进程从内存中对换到磁盘上，以释放内存资源，实际上就是存储器管理中的 对换功能 ； 调度时间尺度 以秒级或分钟级
  • 低级调度（短程调度/进程调度） ： 调度对象 为进程或内核级线程； 主要职责 是决定在内存中就绪状态的进程中，哪一个进程将获得处理器的时间片以执行； 调度时间尺度 为毫秒级
• 调度队列模型
  • 仅有进程调度的调度队列模型
  • 具有高级和低级调度的调度队列模型
  • 具有三级调度的调度队列模型
• 调度算法若干准则
  • 面向用户的准则
    • 周转时间 （ 作业提交到系统开始到作业完成为止的这段时间 ）短（ 平均周转/带权周转时间 ）
      • 平均周转时间
      • 带权平均周转时间：平均周转时间 = 周转时间 / 处理机提供服务时间
    • 响应时间快
    • 截止时间的保证
    • 优先权准则
  • 面向系统 的准则
    • 系统吞吐量高
    • 处理机利用率高
    • 各类资源的平衡利用
• 各种调度算法
  • 作业调度
    • 先来先服务调度算法（First Come First Serve FCFS ）( 作业/进程调度 )
    • 短作业优先调度算法（Short Job First SJF ）( 作业/进程调度 )
    • 高优先权优先调度算法（Priority Schedule Algorithm PSA ）( 作业/进程调度 )： 基于作业的紧迫程度，由外部赋予作业相应的优先级，调度算法根据该优先级进行调度 。类型可分为： 非抢占式优先级调度算法/抢占式优先级调度算法； 静态优先级调度/动态优先级调度
    • 高相应比优先调度算法（Highest Response Ratio Next HRRN ） FCFS和SJF的折中
  • 进程调度
    • 时间片轮转调度算法： 按照FCFS的策略排队，用完时间片的进程送到就绪队列的末尾
    • 多级队列调度算法：设置 多个就绪队列 ， 不同的就绪队列采用不同的调度算法 ， 一个就绪队列中的进程可以设置不同的优先级，不同的就绪队列本身也可以设置不同的优先级
    • 多级反馈队列调度算法：前面各种进程调度算法都有一定的局限性，如果未指明进程长度，则短进程优先和基于进程长度的抢占式调度算法都无法使用； 多级反馈队列调度算法是目前公认的一种较好的进程，较好地满足各种类型用户的需要，调度算法不必事先知道各进程所需的执行时间，较好地满足各种类型进程的需要
      • 调度机制：设置多个就绪队列并赋予不同优先级
      • 优先级低的队列的时间片大
      • 非最后队列采用FCFS算法，最后队列采用RR算法
      • 队列间采用优先级调度算法
  • 实时调度算法
    • 实现实时调度的基本条件
      • 提供必要的信息：就绪时间 ; 开始/完成截止时间 ； 处理时间 ； 资源要求 ； 优先级
      • 系统处理能力强
      • 采用抢占式调度机制
      • 具有快速切换机制：快速响应中断，快速任务分派
    • 实时调度算法的分类
      • 根据实时任务性质的不同：
        • 硬实时调度算法： 硬实时系统中 ，每个任务都有 严格的截止时间 ，任务必须在其截止时间之前完成，否则可能导致系统失效或不可接受的结果；硬实时调度算法包括 最早截止时间优先（Earliest Deadline First，EDF）和最小松弛度优先（Least Slack Time First，LSTF） 等
        • 软实时调度算法： 在 软实时系统中 ，任务也有截止时间，但 违反截止时间不会导致系统的严重失败或崩溃 。任务的截止时间违约可能会降低系统性能，但通常不会引发灾难性的后果；常见的软实时调度算法包括 优先级调度和周期性调度
      • 根据调度方式的不同：
        • 非抢占式调度算法：在非抢占式调度中，一旦任务开始执行，它将一直执行到完成或主动释放CPU，而不会被其他任务中途打断； 执行顺序不可改变、简单、可预测性高，减少了上下文切换的开销。
        • 抢占式调度算法：在抢占式调度中，正在执行的任务可以在中途被更高优先级的任务抢占，以便更高优先级的任务立即获得CPU执行时间； 执行顺序可改变、更好的响应性、更高的灵活性，能够适应不同任务的优先级和变化
      • 根据调度面向实时任务组类型不同：
        • 静态调度算法：在 静态调度 中，任务的分配和调度是在编译或设计阶段确定的，也就是说， 任务的执行顺序和资源分配在程序编写之前就已经确定了
        • 动态调度算法：在动态调度中， 任务的分配和资源管理是在运行时根据系统状态和需求动态确定的 。 任务可以根据优先级、资源可用性等因素进行重新排序或重新分配。
      • 基本调度策略分类：
        • 时间片轮转调度算法： 时间片轮转调度算法 是一种 抢占式调度 算法。每个任务都被分配一个 固定的时间片 （时间量），当任务运行完其时间片后，调度器会将CPU资源分配给下一个任务，这样任务会依次轮流执行。
        • 优先级调度算法： 优先级调度算法 根据每个 任务的优先级 来决定哪个任务获得CPU时间。具有较高优先级的任务将优先于优先级较低的任务执行，分为静态/动态优先级
      • 多处理机环境：
        • 集中式调度：在集中式调度中， 有一个中心调度器或任务调度管理器， 负责协调和分配系统中的任务和资源。这个中心化的调度器决定哪个任务在什么时候执行，以及分配给每个任务的资源
        • 分布式调度：在分布式调度中， 任务调度的决策分散在系统的多个节点上，每个节点都可以独立地决定任务的执行和资源分配。 这种方式可以提高系统的并行性和可伸缩性。
    • 常用的实时调度算法
      • 最早截止时间优先调度算法 （Earliest Deadline First EDF ）
        • 非抢占式调度 用于 非周期实时任务
        • 抢占式调度 用于 周期实时任务
      • 最低松弛度优先调度算法 （Least Laxity First LLF ）： 松弛度(紧急程度)计算公式：任务结束截止时间 - 当前时间 - 任务尚需时间
• 死锁
  • 死锁的基本概念
    • 死锁的定义：在多道程序系统中，并发执行的多个进程因争夺资源而造成的一种若无外力作用有关进程都将永远不能向前推进的僵持状态。
    • 资源分类
      • 可重用性资源（ 永久性资源 ）： 每一个单元只能分配给一个进程使用，不允许多个进程共享 ；进程在使用可重用性资源时， 须按照如下顺序：请求、使用、释放 ； 资源的单元数目相对固定，进程在运行期间既不能创建也不能删除 ； 例子：CPU、I/O通道、主存储器和辅助存储器、设备、以及文件、数据库和信号量之类的数据结构
      • 可消耗性资源（ 临时性资源 ）： 进程运行期间动态地创建和消耗 ；每一类可消耗性资源的 单元数目在进程运行期间是可以变化 的； 进程在运行过程 中， 可以不断地创造 可消耗性资源的单元；进程在运行过程中， 可以请求 若干个可消耗性资源单元 。 例：进程间通信的消息
      • 可抢占性资源：指某进程在获得这类资源后，可以再被其它进程或系统抢占这类资源不会引起死锁， 例如CPU和内存
      • 不可抢占性资源：一旦系统把某资源分配给该进程后，就不能将它强行收回，只能在进程用完后自行释放 ， 例如打印机、磁带机
  • 死锁产生的原因
    • 竞争资源（ 不可抢占性资源/临时性资源 ）
    • 进程推进顺序不当： ①、②、③曲线均不会死锁；④则发生死锁
  • 死锁产生的必要条件
    • 互斥条件
    • 请求和保持条件
    • 不可抢占
    • 循环等待
  • 处理死锁的基本方法
    • 预防死锁： 设置某些限制前提 以破坏产生死锁必要条件
      • 破坏请求和保持条件 ， 一次性申请所有资源 ； 优点 ：简单、易行、安全； 缺点 ：资源被严重浪费，进程经常会发生饥饿现象
      • 破坏不可抢占条件，主动释放 ，进程在需要资源时才提出请求，且得不到满足时应释放其已占有资源； 缺点：实现复杂，代价很大 （反复地申请与释放资源、进程周转时间延长、系统吞吐量降低、系统开销增加）
      • 破坏环路等待条件，申请有序 ， 所有资源按类型进行线性排队，所有进程对资源的请求严格按资源序号递增次序提出 ； 缺点 ：资源次序的不灵活性（新设备、程序逻辑设计与编程限制及资源浪费）
    • 避免死锁： 资源动态分配过程中 ，利用某种方法防止系统进入不安全状态
      • 银行家算法
        • 算法描述： 只要保证系统处于安全状态，便可避免死锁，并非所有不安全状态都是死锁状态
          • 算法模拟
    • 检测死锁： 运行过程中 通过 系统设置的检测机构及时检测死锁的发生 ，并精确确定相关进程和资源，类似于银行家算法
    • 解除死锁： 撤销或挂起一些进程 以 回收资源和再分配
      • 基本方法：1、 抢占资源 ，由一个/多个进程抢占足够资源，分配给死锁进程，以解除死锁状态 ；2、 终止一个/多个死锁进程
      • 终止进程的方法：
        • 终止所有死锁进程： 最简单，代价可能很大
        • 逐个终止死锁进程：终止进程的策略： 为死锁解除付出的代价最小

---

转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 2542608082@qq.com