王道408处理机调度（下）

王道408处理机调度（下）--经典的调度算法，内容有：先来先服务(FCFS)、短作业优先(SF)、优先级调度算法、高响应比调度算法、时间片轮转调度算法、多级队列调度算法、多级反馈队列调度算法。

处理机调度（下）

• 经典的调度算法
  • 先来先服务(FCFS)
    • 调度步骤
      • 每次从后备作业队列中选择最先进入就绪队列的作业。
      • 直到运行完成或因某种原因阻塞，才释放处理机。
    • 优点
      • 算法简单
      • 对长作业有利
      • 有利于CPU繁忙型作业
    • 缺点：
      • 效率低
      • 对短作业不利
      • 不利于I/O繁忙型作业
  • 短作业优先（SJF）
    • 调度步骤
      • 优先选择预计运行时间最短的进程分配处理机
      • 直到运行完成或因某种原因阻塞，才释放处理机
    • 优先
      • 平均等待时间和平均周转时间最短
    • 缺点
      • 对长作业不利，造成“饥饿”现象
      • 不考虑作业的紧迫程度
  • 优先级调度算法
    • 调度步骤
      • 每次从后备作业队列中选择一个优先级最高的一个作业，给他分配处理机
    • 分类
      • 非剥夺式
        • 等待当前进程运行完成，然后讲处理机分配给更高优先级进程
      • 剥夺式
        • 如果有更高优先级的进程到了就绪进程，则立即停止当前运行进程
    • 优先级分类
      • 静态优先级：进程创建后，无法对其优先级进行修改
      • 动态优先级：可以根据进程运行状态，对其进程的优先级进行动态调整。
      • 优先级设置原则
        • 系统进程>用户进程
        • 交互型进程>非交互型进程
        • I/O型进程>计算型进程
  • 高响应比调度算法
    • 调度步骤
      • 每次作业调度时，先计算后备作业队列中每个作业的响应比
      • 响应比=（等待时间+要求服务时间）/要求服务时间
      • 选出响应比最高的作业运行
    • 优点
      • 等待时间相同情况下，要求服务时间越短，响应比越大，有利于短作业进程
      • 作业的响应比可以随等待时间的增加而提高，等待时间足够长时，其响应比可以升到很高，所以有利于长作业
      • 不会导致饥饿，非抢占式算法
  • 均为优先选择优先级数值较高的进程
  • 时间片轮转调度算法
    • 调度步骤
      • 在就绪进程队列按照到达的先后顺序排成队列
      • 给最前面的就绪进程分配时间片
      • 时间片结束后，将该进程调入队尾，然后，给新的队头进程分配处理机。
    • 时间片大小队系统性能的影响
      • 时间片选择过大时，就变成了先来先服务
      • 时间片选择过小时，就变成了短作业优先
  • 多级队列调度算法
    • 调度步骤
      • 在系统中设置了多个就绪队列，将不同类型或性质的进程固定分配到不同的就绪队列
      • 同一个队列的进程可以设置不同的优先级，不同的队列本身也可以设置不同的优先级
  • 多级反馈队列调度算法
    • 调度步骤
      • 设置多个就绪队列，每个队列赋予不同的优先级，一级最高，往后越低
      • 赋予每个就绪队列的时间片不同，优先级越高，时间片越少。
      • 队列之间，采用优先级调度。即优先级高的队列执行完毕后，才会执行优先级低的队列的进程。
      • 每个队列内部，采用先来先服务（FCFS）调度
      • 当进程被迫降入最后一级队列时，在最后一级采用时间片轮转。
    • 优点
      • 对于，终端型作业用户：短作业优先。
      • 对于，短批处理作业用户：周转时间短
      • 对于，长批处理作业用户：经过前面几个队列得到部分执行，不会长期得不到处理。
    • 缺点：可能会产生“饥饿”现象，因为是抢占式算法。