处理机调度与死锁

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

处理机调度与死锁

• 处理机调度的层次和调度算法的目标
  • 处理机调度的三个层次
    • 高级调度
      • 又称为作业调度，调度对象是作业
    • 低级调度
      • 又称为进程调度，调度对象是进程
    • 中机调度
      • 又称为内存调度，引入的目的主要是提高内存利用率和系统吞吐量
  • 处理机调度算法的目标
    • 处理机调度算法的共同目标
      • 资源利用率
      • 公平性
      • 平衡性
      • 策略强制执行
    • 批处理系统的目标
      • 平均周转时间短
        • 周转时间：从作业被提交给系统开始，到作业完成为止的这段时间间隔 平均周转时间 带权周转时间：W=T/Ts T为周转时间，Ts为服务时间 平均带权周转时间
      • 系统吞吐量高
        • 系统吞吐量：单位时间内系统所完成的作业数
      • 处理机利用率高
    • 分时系统的目标
      • 响应时间快
        • 响应时间：指从用户通过键盘提交一个请求开始，直到屏幕上显示出的处理结果为止的一段时间。
      • 均衡性
        • 均衡性：指系统响应时间的快慢应与用户所请求服务的复杂性相适应
    • 实时系统的目标
      • 截至时间的保证
      • 可预测性
• 作业和作业调度
  • 多道程序度
    • 内存中允许多少个进程在内存中运行
      • 作业调度每次从后备队列中选取多少个作业装入内存取决于多道程序度
  • 四种调度算法
    • 先来先服务调度算法（FCFS）
      • • 按作业到达的先后次序进行调度，既可以用于作业调度也可以用于进程调度
    • 短作业优先（SJF）的调度算法
      • 以作业的长短来计算优先级，分为非抢占式和抢占式两种 缺点： 1.必须预知作业的运行时间，估计执行不客观 2.对长作业（进程）不利 3.人机无法实现交互 完全未考虑作业的紧迫程度
    • 优先级调度算法（PSA）
      • 系统从若干个优先级最高的装入内存，优先级调度算法可以作为进程调度算法
    • 高响应比优先调度算法（HRRN）
      • 引入动态优先级 优先权=等待时间+要求服务时间/要求服务时间 由于等待时间与要求服务时间之和就是系统对该作业的响应时间，故优先级相当于响应比Rp Rp=等待时间+要求服务时间/要求服务时间=响应时间/要求服务时间
• 死锁
  • 死锁概述
    • 起因
      • 竞争资源
      • 进程间的推进顺序非法
    • 产生死锁的四个必要条件
      • 必须同时具备以下四个条件，只要有一个不成立，死锁就不会发生
      • 互斥条件
        • 不能破坏，因为互斥条件是由设备固有条件所决定的，不仅不能改变，还应加以保证。
      • 请求和保持条件
      • 不可抢占条件（不可剥夺）
      • 循环等待条件
    • 处理死锁的基本方法
      • 预防死锁到解除死锁，对于死锁的防范程度逐渐减弱，但对应的资源利用率会提高，以及进程间因资源因素而阻塞的频率下降（并发程度提高）
      • 预防死锁
        • 可能导致系统资源利用率和系统吞吐量降低
      • 避免死锁
        • 在资源分配过程中，防止进入不安全状态
      • 检测死锁
      • 解除死锁
  • 预防死锁
    • 破坏请求和保持条件
      • 第一种协议 第二种协议
    • 破坏不可抢占条件
      • 释放已经占有的
    • 破坏循环等待条件
      • 采用资源有序分配法，按编号进行
  • 避免死锁
    • 系统安全状态
      • 找安全序列，并非所有的不安全状态都必然会转换为死锁状态
    • 利用银行家算法避免死锁
  • 死锁的检测和解除
    • 死锁的检测
      • 资源分配图
      • 死锁定理
        • S为死锁状态的充分条件为：当且仅当S状态的资源分配图是不可完全简化的。该充分条件被称为死锁定理。
    • 死锁的解除
      • 中止进程的方法
      • 付出最小代价的死锁解除算法
• 进程调度
  • 进程调度的任务，机制和方式
    • 1.进程调度的任务主要有三： （1）保存处理机的现场信息； （2）按某种算法选取进程； （3）把处理机分配给进程。 2.进程调度机制 为了实现进程调度，应该具有如下三个基本部分：排队器，分配器，上下文切换器 3.进程调度方式 （1）非抢占式 （2）抢占式 遵循的原则有： 优先权原则，短进程优先，时间片原则
  • 轮转调度算法
    • 在分时系统中，基于时间片的轮转调度算法。
  • 优先级调度算法
  • 多队列调度算法
  • 多级反馈队列
  • 基于公平原则的调度算法