3-操作系统思维导图第3章

这是一篇关于3-操作系统思维导图第3章的思维导图，对于3-操作系统感兴趣的小伙伴可以收藏起来观看哦，希望对大家有所帮助。

第3章：处理机调度与死锁

• 3.1处理机调度的层次与目标
  • 层次
    • 高级调度
      • 又称长调度、作业调度
      • 目标
        • 作业
      • 场所
        • 多道批处理系统
    • 低级调度
      • 又称进程调度、短调度
      • 目标
        • 进程
      • 场所
        • 多道批处理系统、分时、实时系统
    • 中级调度
      • 又称内存调度
      • 目的
        • 提高内存利用率和系统吞吐量
    • 以上三种调度方式，进程调度运行频率最高，内存调度次之，作业调度最低
  • 目标
    • 处理机调度算法
      • 资源利用率、公平性、平衡性、策略强制执行
    • 批处理系统
      • 周转时间：从作业被提交到系统开始，到作业完成为止的时间间隔
      • 平均周转时间短、系统吞吐量高、处理及利用率高
    • 分时系统
      • 响应快、均衡性
    • 实时系统
      • 可预测性、截止时间保障
• 3.2作业与作业调度
  • 批处理系统中的作业
    • 作业
      • 批处理系统中以作业为基本单位从外存调入内存
    • 作业控制块JCB
  • 算法
    • 先来先服务 FCFS
      • 等待时间越长优先级越高，先来先服务
    • 短作业优先 SJF
      • 作业运行时间越短优先级越高
    • 优先级调度算法 PSA
      • 基于作业的紧迫程度，由外部赋予优先级
    • 高响应比优先调度算法 HRRN
      • 即考虑作业等待时间，也考虑其运行时间
      • 优先权=（等待时间+运行时间）/运行时间
      • 响应时间=等待时间+运行时间
• 3.3进程调度
  • 方式
    • 非抢占式
    • 抢占式
      • 高优先级抢占
      • 短进程优先抢占
      • 时间片原则
  • 算法
    • 轮转调度算法 RR
      • 到达时间、服务时间、完成时间、周转时间、带权周转时间
      • 完成时间需要画图得出
      • 周转时间=完成时间-到达时间
      • 带权周转时间=完成时间/服务时间
      • 位置
        • 一个时间片结束还未完的放到队尾
        • 新加入的放到队尾
• 最低松弛度
  • 松弛度=必须完成时间-运行时间-当前时间

第3章：处理机调度与死锁

• 3.5死锁概述
  • 死锁的定义
    • 如果一组进程中的每个进程都在等待仅由该组其他进程才能引发的事件，那么该组进程是死锁的
  • 必要条件
    • 互斥条件
    • 请求和保持条件
    • 不可抢占条件
    • 循环等待条件
  • 处理方法
    • 预防死锁
      • 通过破坏四个必要条件来预防死锁
    • 避免死锁
      • 资源团分配时防止进入不安全状态
    • 检测死锁
    • 解除死锁
• 3.6预防死锁
  • 由于互斥条件是非共享设备必须的需要加以保证，所以主要破坏产生死锁的后三个条件
  • 破坏请求和保持条件
    • 当一个进程在请求资源时，它不能持有不可抢占资源
    • 第一种协议
      • 一次性分配其运行所需全部资源
    • 第二种协议
      • 先分配初期所需资源，然后边释放已完成的资源，边申请需要的资源
  • 破坏不可抢占条件
    • 当一个保持了某些不可抢占资源的进程提出新的资源请求而得不到满足时，释放其所有资源，待以后需要是重新申请。
  • 破坏循坏等待条件
    • 对系统中所有资源进行线性排序，并赋予不同序号。
• 3.7避免死锁
  • 银行家算法
    • 资源分配表
      • Max
      • Allocation
      • Need
      • Available
    • 安全序列
      • Work
      • Need
      • Allocation
      • Work+Allocation
      • Finish
    • 安全性判断
      • Request()<Need()
      • Request()>Available()
        • 等待
      • Request()<Available()
        • 先分配在计算安全序列
• 3.8死锁检测与解除
  • 死锁检测
    • 资源分配图
      • 节点
        • 进程用圈表示
        • 节点用框表示
      • 边
        • 进程指向资源
          • 资源请求边，表示请求一个单位的资源
        • 资源指向进程
          • 资源分配边，表示分配一个单位的资源给进程
      • 简化过程
        • 找出不阻塞又不独立得进程节点，然后去掉该进程节点得所有边
        • 反复执行上述过程，直到资源分配图中全部进程节点全部孤立为止，为完全简化
      • S为死锁的充分条件，又称死锁定理
        • 当且仅当S得资源分配图时不可完全简化的
  • 死锁解除
    • 抢占资源
      • 从一个或多个进程中抢占足够多的资源分给死锁进程
    • 终止或撤销进程
      • 终止系统中的死锁进程，直到打破死锁循环