处理机调度与死锁

计算机操作系统之处理机调度与死锁笔记，包括处理机调度的层次和调度算法的目标、作业和作业调度、进程调度和死锁等内容。

处理机调度与死锁

• 处理机调度的层次和调度算法的目标
  • 处理机调度的层次
    • 高级调度
      • 调度对象：作业
      • 功能
        • 接纳多少个作业
        • 接纳哪些作业
      • 主要用于多道批处理系统
    • 低级调度
      • 调度对象：进程
      • 功能
        • 根据某种算法，决定就绪队列中的哪个进程获得处理机
      • 多道批处理、分时、实时系统都必须配置
    • 中级调度
      • 目的
        • 提高内存利用率和系统吞吐量
  • 处理机调度算法的目标
    • 处理机调度算法的共同目标
      • 资源利用率
        • CPU利用率=CPU有效工作时间/（CPU有效工作时间+CPU空闲等待时间）
      • 公平性
      • 平衡性
      • 策略强制执行
    • 批处理系统的目标
      • 平均周转时间短
      • 系统吞吐量高
      • 处理机利用率高
    • 分时系统的目标
      • 响应时间快
      • 均衡性
    • 实时系统的目标
      • 截止时间的保证
      • 可预测性
• 作业与作业调度
  • 批处理系统中的作业
    • 作业和作业步
      • 作业
        • 程序+数据+作业说明书
      • 作业步
        • 作业中相对独立又关联的操作步骤
    • 作业控制块JCB
    • 作业运行的三个阶段和三种状态
      • 收容阶段、运行阶段、完成阶段
      • 后备状态、运行状态、完成状态
  • 作业调度的主要任务
    • 接纳多少个作业
      • 取决于多道程序度
    • 接纳哪些作业
      • 取决于调度算法
  • 作业调度算法
    • 先来先服务调度算法FCFS
      • 可用于作业调度/进程调度
      • 对短作业不利
    • 短作业优先SJF/短进程优先SPF调度算法
      • 短作业优先SJF
        • 从后备队列中选择一个或若干个估计运行时间最短的作业，调入内存运行
      • 短进程优先SPF
        • 从就绪队列中选出一个估计运行时间最短的进程，将处理机分配给它
    • 优先级调度算法PSA
      • 基于作业的紧迫程度，由外部赋予作业相应的优先级，调度算法根据优先级进行调度
    • 高响应比优先调度算法HRRN
      • 优先权=（等待时间＋要求服务时间）/要求服务时间
• 进程调度
  • 进程调度的任务、机制和方式
    • 任务
      • 保护处理机的现场信息
      • 按某种算法选取进程
      • 把处理机分配给进程
    • 机制
      • 排队器
      • 分派器
      • 上下文切换器
    • 进程调度方式
      • 非抢占式方式
        • 主要用于批处理系统
        • 实时性要求不严的实时系统
      • 抢占方式
        • 用于
          • 对性能要求较高的批处理和分时系统
          • 要求比较严格的实时系统
        • 抢占必须遵循的原则
          • 优先权原则
          • 短进程优先原则
          • 时间片原则
  • 轮转调度算法
    • 轮转法的基本原理
    • 进程切换时机
      • 进程运行完，时间片未用完
      • 时间片用完，进程未执行完
    • 时间片大小的确定
  • 优先级调度算法
    • 优先级调度算法的类型
      • 非抢占式优先级调度算法
      • 抢占式优先权调度算法
    • 优先级类型
      • 静态优先级
      • 动态优先级
  • 多队列调度算法
    • 设置若干个就绪队列，将不同性质或类型的进程固定分配在不同的就绪队列
    • 不同的就绪队列采用不同的调度算法
    • 系统可以提供多种调度策略
  • 多级反馈队列调度算法
    • 调度机制
      • 设置多个就绪队列，赋予不同优先级
      • 每个队列都采用FCFS算法
      • 按队列优先级调度
    • 调度算法的性能
• 实时调度
  • 实现实时调度的基本条件
    • 提供必要的信息
      • 就绪时间
      • 开始截止时间和完成截止时间
      • 处理时间
      • 资源要求
      • 优先级
    • 系统处理能力强
    • 采用抢占式调度机制
    • 具备快速切换机制
      • 对外部中断的快速响应能力
      • 快速的任务分派能力
  • 实时调度算法的分类
    • 非抢占式调度算法
      • 非抢占式轮转调度算法
      • 非抢占式优先调度算法
    • 抢占式调度算法
      • 基于时钟中断的抢占式优先权调度算法
      • 立即抢占的优先权调度算法
  • 最早截止时间优先EDF算法
    • 非抢占式调度方式用于非周期实时任务
    • 抢占式调度算法用于周期实时任务
  • 最低松弛度优先LLF算法
    • 空闲时间越短，优先级越高
  • 优先级倒置
    • 优先级倒置的形成
    • 解决方法
      • 优先级继承
      • 优先级天花板
• 死锁概述
  • 资源问题
    • 可重用性资源
      • 重复多次使用的 CPU、内存、外设、文件
    • 可消耗性资源
      • 临时性的 共享缓冲区中的数据
    • 可抢占性资源
    • 不可抢占性资源
  • 计算机系统中的死锁
    • 竞争不可抢占性资源引起死锁
    • 竞争可消耗资源引起死锁
    • 进程推进顺序不当引起死锁
  • 死锁的定义、必要条件和处理方法
    • 定义
      • 在一组进程中的每一个进程，都在等待仅由该组进程中的其他进程所占有的资源，那么该组进程是死锁的（Deaklock）。
    • 产生死锁的必要条件
      • 互斥条件
      • 请求和保持条件
      • 不可抢占条件
      • 循环等待条件
    • 处理死锁的方法
      • 预防死锁
      • 避免死锁
      • 检测死锁
      • 解除死锁
• 预防死锁
  • 破坏“请求和保持”条件
  • 破坏“不可抢占”条件
  • 破坏“循环等待”条件
• 避免死锁
  • 系统安全状态
    • 只要能使系统始终都处于安全状态，便可避免发生死锁
    • 避免死锁的实质是：系统在进行资源分配时，设法使系统不进入不安全状态
  • 利用银行家算法避免死锁
    • 银行家算法中的数据结构
      • 可利用资源向量Available
      • 最大需求矩阵Max
      • 分配矩阵Allocation
      • 需求矩阵Need
    • 银行家算法
      • Requesti[ j ]<= Need[i, j]
      • Requesti[ j ]<= Available[ j ]
      • 尝试分配
      • 安全性检查
      • 安全则分配资源，否则不分配资源，进程等待
• 死锁的检测与解除
  • 死锁的检测
    • 资源分配图
    • 死锁定理
      • 可以证明：S状态为死锁状态的充分条件是当且仅当S状态的资源分配图是不可完全简化的。
    • 死锁检测中的数据结构
  • 死锁的解除
    • 剥夺资源
    • 撤销进程