3.第三章 进程调度与死锁

这是一篇关于3.第三章 进程调度与死锁的思维导图。操作系统：是一种复杂的系统软件，是不同程序代码、数据结构、数据初始化文件的集合，可执行。

第三章 进程调度与死锁：

• 进程调度的功能与时机：
  • 功能：
    • 进程调度的功能由操作系统的【进程调度程序】完成
    • 按照某种策略和算法【从就绪态进程】中为【空闲的CPU】选择在其上运行的【新进程】
  • 时机：
    • 进程正常结束
    • 进程异常结束
    • 进程阻塞
    • 有更高优先级进程到来
    • 时间片用完
• 进程调度算法：
  • 几种算法：
    • 先来先服务调度算法（FCFS）
    • 短进程优先调度算法（PSW）
    • 优先权调度算法
    • 时间片轮转调度算法
    • 【略】多级队列调度算法
    • 【略】多级反馈队列调度算法
  • 【背】好算法的标准：
    • 周转时间短
      • 外存等待时间
      • 就绪队列等待时间
      • 等待I/O操作完成
      • 等待时间
      • 执行时间
    • 响应时间短
    • 截止时间的保证
    • 系统吞吐量高
    • 处理机利用率好
  • 相关解释：
  • 【算】公式及算法：
    • 算法：
      • 周转时间 = 服务时间 + 等待时间
      • 开始运行时间 = 进入系统时间 + 周转时间
      • 开始运行时间 = 服务时间 + 等待时间
      • 上一个进程的时间
      • 等待时间 = 开始运行时间 - 进入系统时间
    • 【算】：
      • 平均周转时间：
      • 带权平均周转时间：
  • 六种算法：
    • 【算】先来先服务调度算法（FCFS）：
      • 含义：从就绪队列的队首选择最先到达就绪队列的进程，为该进程分配CPU
      • 按先来后到的顺序
    • 【算】短进程优先调度算法（SPF）：
      • 含义：从就绪队列中【选择估计运行时间最短的进程】，为该进程分配CPU
      • 按进程的长短顺序排序，短的进程先
      • 优缺点：
        • 优点：
          • 与FCFS算法相比，短进程优先算法能有效【降低进程的平均等待时间，提高系统吞吐量】
        • 缺点：
          • 对长进程不利
          • 不能保证紧迫进程的处理
          • 进程长短由用户估计，不一定准确
    • 优先权调度算法：
      • 含义：
        • 该算法中，系统将CPU分配给就绪队列中【优先权最高的进程】
      • 算法类型：
        • 抢占式：
          • 运行期间，有更高优先权的进程到来，也【不能剥夺CPU】
        • 非抢占式：
          • 运行期间，有更高优先权的进程到来，就可以【抢占CPU】
      • 抢占式&非抢占式：
        • 非抢占式：
        • 抢占式：
      • 优先权类型：
        • 静态优先权：
          • 创建时确定，运行期间保持【不变】
        • 动态优先权：
          • 创建时确定，随着进程推进或等待时间增加而【改变】
      • 问题与方法：
        • 存在的问题：无穷阻塞（饥饿问题）
        • 动态优先权（老化技术）
    • 时间片轮转调度算法：
      • 时间：
        • 时间片大小：
          • 10-100ms
        • Linux2.4:
          • 50ms
      • 两只情况：
        • 如果程序需要的时间<时间片大小，执行下一个进程
        • 如果程序需要的时间>时间片大小，进程转换为就绪态
      • 时间片大小的确定：
      • 性能评价：
        • 时间片很大=先来先服务算法
        • 时间片很小：增大cpu对进程切换和调度的开销
      • 【背】时间片轮转调度算法：
        • 按照先来先服务的原则排成队列
        • 每次调度首进程先执行一个时间片
        • 时间片用完后，终止运行的程序并将其送至就绪队列队尾
      • 系统允许的【最大进程数一定时】，系统要求的【响应时间越短】，【时间片取值应该越小】
    • 多级队列调度算法（RR）：
      • 将就绪队列分成多个【独立队列】
      • 每个队列有自己的【调度算法】
    • 多级反馈队列调度算法：
      • 建立多个优先权不同的【就绪队列】
      • 每个队列有大小不同的【时间片】
      • 低优先权的进程不存在饥饿问题
• 实现实时调度的基本条件：
  • 【背】提供必要的调度信息：
    • 就绪时间
    • 开始截止时间和完成截止时间
    • 处理时间
    • 资源要求
    • 优先级
    • 口诀：初九开完会就自由了
  • 系统处理能力强
  • 采用抢占式调度机制
  • 快速的进程切换能力
  • 对外部中断的快速响应能力
• 进程切换：
  • 最早截止时间优先算法（EDF）：
    • 开始截止时间越早，进程优先级越高，越优先获得CPU(优先级)
  • 【算】最低松弛度优先算法（LLF）:
    • 公式：L=T-Tc-Ts
    • 解释：
      • T：完成截止时间
      • Tc：当前时间
      • Ts：处理完该任务还需要的时间
  • 进程切换的含义：
    • 当前正在执行的进程成为被替换进程，让出其所使用的CPU，以运行被进程调度程序选中的新进程，这个过程称为【进程切换】
  • 进程切换的步骤:
    • 保存CPU上下文环境
    • 更新进程1控制块
    • 修改进程状态（执行态——>就绪态&阻塞态）
    • 移动进程控制块到就绪队列或阻塞队列
    • 调度新程序，更新进程2控制块
    • 更新内存管理的数据结构
    • 恢复进程的硬件上下文
• 多处理器调度：
  • 多处理器系统的类型：
    • 处理机的耦合程度：
      • 紧密耦合：共享主存储器和I/O设备
      • 松弛耦合：有各自的存储器和I/O设备
    • 是否对称：
      • 对称（同构）：处理单元功能和结构相同
      • 非对称：有多种类型的处理单元一个主处理器，多个从处理器
  • 多处理器系统中进程的分配方式：
    • 对称处理机分配：
      • 静态分配：
        • 就绪队列的进程【只能在与就绪队列对应的处理器】上运行
      • 动态分配：
        • 进程【随机地分配】到当时处于【空闲状态】的某一处理器上执行
    • 非对称处理机分配：
      • 主—从式操作系统：
  • 进程（线程）的调度方式：
    • 自调度：
      • 内容：
        • 最常用最简单的方式
        • 任何一个空闲处理器都可以从就绪队列中选取一个进程或线程运行
        • 先来先服务调度算法（FCFS）
      • 优缺点：
        • 优点：
          • 易移植
          • 有利于提高CPU的利用率
        • 缺点：
          • 瓶颈问题
          • 低效性
          • 线程切换频繁
    • 成组调度：
      • 内容：
        • 系统将一组【相互合作】的进程或线程，【同时分配到一组】处理器上运行
        • 进程或线程与处理器【一一对应】
      • 优点：
        • 减少线程的切换
        • 减少调度开销
    • 专用处理器分配：
      • 内容：在程序执行期间，【专门】为该程序分配一组处理器，每个线程一个
      • 优缺点：
        • 优点：
          • 加快程序运行速度
          • 避免进程切换
        • 缺点：
          • 处理器资源严重浪费
• 死锁：
  • 死锁的定义：
    • 定义：
      • 由于【多个进程竞争共享资源】而引起的【进程不能向前推进】的僵死状态称为【死锁】
    • 产生的原因：
      • 【竞争】共享资源且分配资源的【顺序不当】
  • 产生死锁的必要条件：
    • 互斥条件
    • 请求和保持条件
    • 不剥夺条件
    • 环路等待条件
    • 四个条件全部发生才会发生死锁
  • 【背】处理死锁的基本方法：
    • 死锁的预防：
      • 【破坏死锁的产生条件】保证不发生死锁
    • 死锁的避免：
      • 【算法合理分配资源】保证不发生死锁
    • 死锁的检测：
      • 检测当前系统【是否出现死锁】
    • 死锁的解除：
      • 检测到有死锁后进行【解除】
  • 死锁的三种预防：
    • 摒弃请求和保持条件：
      • 进程【执行前一次性申】请全部资源，【申请其他资源前】释放占用的资源
      • 对某些进程在【申请其他资源前】要求该进程【释放】已经分配给它的【所有资源】
    • 摒弃不剥夺条件：
      • 一个保持了某些资源的进程【需要申请其他资源得不到满足时】，必须释放所有资源
      • 缺点：
        • 实现复杂
        • 代价高
    • 摒弃环路等待条件：
      • 进程必须【按规定的顺序申请资源】
      • 缺点：
        • 限制了新设备的增加
        • 资源浪费
        • 用户编程麻烦
  • 死锁的避免：
    • 不安全状态与死锁：
      • 不安全状态可能是死锁状态
      • 死锁状态一定是不安全状态
    • 通过资源合理分配使系统处于安全状态
    • 安全状态：
      • 定义：找到一个【进程执行序列】，保证资源按需分发，【避免死锁】
      • 安全状态：找到进程执行序列
      • 不安全状态：找不到进程执行序列
      • 图1如图所示：
        • K=3,P1—P2,(4-2)<3,TRUE,K=(3-2)+4=5
        • K=5,P2-P1,(10-5)<=5,TRUE,K=(5-5)+10=10
        • K=10,P1-P3,(9-2)<10,TRUE,K=(10-7)+9=12
      • 图2如图所示：
        • K=2,P1-P2,(4-2)<=2,TRUE,K=(4-2)+2=4
        • K=4,P2-P1,(10-5)>4,FALSE
        • K=4,P2-P3,(9-3)>4,FALSE
    • 银行家算法：
      • 定义：一个进程提出资源请求后，系统先进行资源的试分配，分配后检测系统是否安全
      • 银行家算法的实质是避免系统进入【不安全】状态
      • 注：K表示可用，N表示还需要，A表示已分配
      • 推演：
        • P0.N(7 4 3)>K(3 3 2),FALSE
        • P1.N(1 2 2)<K(3 3 2),TRUE,K=P1.A+K=(2 0 0)+(3 3 2)=(5 3 2)
        • P2.N(6 0 0)>K(5 3 2),FALSE
        • P3.N(0 1 1)<K(5 3 2),TRUE,K=P3.A+K=(2 1 1)+(5 3 2)=(7 4 3)
        • P4.N(4 3 1)<K(7 4 3),TRUE,K=P4.A+K=(0 0 2)+(7 4 3)=(7 4 5)
        • 第一轮
        • P0.N(7 4 3)<K(7 4 5),TRUE,K=P0.A+K=(0 1 0)+(7 4 5)=(7 5 5)
        • P2.N(6 0 0)<K(7 5 5),TRUE,K=P2.A+K=(3 0 2)+(7 5 5)=(10 5 7)
        • 第二轮
        • 【END】，循环结束，该进程是一个安全进程
  • 死锁的检测：
    • 何时调用检测算法：
      • 死锁可能发生的频率
      • 死锁发生时受影响的进程数量
    • 资源分配图：
  • 死锁的解除：
    • 进程终止：
      • 终止所有死锁进程
      • 一次只终止一个处于死锁的进程，直到死锁解除
    • 资源抢占：
      • 逐步从进程中抢占资源给其他进程使用直到死锁被打破为止
      • 抢占要点：
        • 抢占代价最小
        • 回滚
        • 饥饿