进程调度

进程调度的时机

• 进程调度(低级调度) : 按照一定的算法从就绪队列中选择一个进程为其分配处理机
• 什么时候需要进行进程调度和切换
  • 当前运行的进程主动放弃了处理机
    • 进程正常终止
    • 运行过程中发生异常而终止
    • 进程主动请求阻塞
  • 当前运行的进程被动放弃了处理机
    • 分配的时间片使用完
    • 有更紧急的事情需要处理(I/O中断)
    • 有更高优先级的进程进入就绪队列
• 不能进行进程调度的情况
  • 处理中断的过程. 中断处理过程复杂, 和硬件紧密相关, 很难做到在中断处理过程中进行进程切换
  • 进程在操作系统内核程序临界区中
  • 在原子操作中, 原子操作不可中断, 一气呵成(比如之前的修改PCB中进程状态标识, 并把PCB转移相应的队列中)

进程的切换与过程

• 狭义的进程调度 和 进程切换

  • 狭义的进程调度 : 从就绪队列中选择一个要运行的进程
  • 进程切换 : 一个进程让出处理机, 另一个进程占用处理机的过程

• 广义的进程调度包含了 选择一个进程 和 进程切换两个步骤

• 进程切换的过程主要完成了

  • 对原来运行进程的各种数据进行保存
  • 对新的进程的数据进行恢复
  • (程序计数器, 程序状态字, 各种数据寄存器等信息. 这些信息一般保存在PCB中)

进程切换是有代价的, 如果过于频繁的进程调度, 切换, 必然会使整个系统的效率降低. 因为系统大部分时间都花在了进程切换上, 而真正用于执行进程的时间减少

进程的调度方式

• 非剥夺调度方式 (非抢占式)
  • 只允许进程主动放弃该处理机. 运行过程中即便有更紧迫的任务到达, 当前进程依然会继续使用处理机. 知道该进程终止或主动要求进入阻塞态.
  • 实现简单, 系统开销小. 但是无法及时处理紧急任务, 适合于早期的批处理系统
• 剥夺调度方式 (抢占式)
  • 当一个进程正在处理机上执行时, 如果又一个更重要或更紧迫的进程需要使用处理机. 则立即暂停正在执行的进程, 将处理机分配给更重要更紧迫的那个进程.
  • 可以优先处理更紧急的进程, 也可以实现让各进程按时间片轮流执行的功能 (通过时钟中断). 适合于分时操作系统, 实时操作系统

总结

调度算法的评价指标

CPU利用率

• 由于早起的CPU造价及其昂贵, 因此人们会希望让CPU尽可能多的工作 (物尽其用)
• CPU利用率 : 指CPU “忙碌” 的时间占总时间的比例
• 利用率 = 忙碌的时间 / 总时间

系统吞吐量

• 对于计算机来说, 希望用尽可能少的时间处理尽可能多的作业
• 系统吞吐量 : 单位时间内完成的作业数量
• 系统吞吐量 : 总共完成了多少道作业 / 总共花了多少时间

周转时间

• 对于计算机用户来说, 关心自己的作业从提交到完成花了多少时间

• 周转时间 : 从作业被提交给系统开始, 到作业完成为止的这段时间间隔

  • 包括四部分
    • 作业在外存的后备队列上, 等待作业调度的时间
    • 进程在就绪队列上等待进程调度的时间
    • 进程在CPU上运行的时间
    • 进程等待IO操作的时间
    • (后三项在一个作业的整个处理过程中可能发生多次)

• (对用户来说)周转时间 = 作业完成时间 - 提交时间

• (对操作系来说, 更关心系统的整体表现, 因此更关心所有作业周转时间的平均值)平均周转时间 = 各作业周转时间之和 / 作业数`

周转时间相同的情况下, 运行时间不同, 给用户的感受是不一样的

• 带权周转时间 : 作业周转时间 / 作业实际运行时间 = ( 作业完成时间 - 作业提交时间 ) / 作业实际运行时间

  • 带权周权时间 >=1
  • 带权周转时间与周转时间都是越小越好
    • (周转时间一定, 运行时间越长越好. 运行时间一定, 周转时间越小越好)

• 平均带权周转时间 = 各个作业带权周转时间之和 / 作业数量

等待时间

• 计算机的用户希望自己的作业尽可能少的等待处理机

• 等待时间 : 进程 / 作业 处于等待处理机状态的时间之和, 等待时间越长, 用户满意度越低

• 对于进程来说, 等待时间就是指继承建立后等待被服务的时间总和, 在等待I/O完成的期间起始进程也在被服务, 所以不计入等待时间

• 对于作业来说, 不仅要考虑建立进程后等待的时间, 还要加上作业在外存后备队列中等待的时间

一个作业总共要被CPU服务多久, 被I/O设备服务多久一般是确定不变的, 因此调度算法其实只会影响作业/进程 的等待时间, 当然, 与前面指标类似, 也有平均等待时间来评价整体性能

响应时间

• 对于计算机用户来说, 会希望自己提交的请求尽早地开始被系统服务, 回应.
• 响应时间 : 指从用户提交请求到首次产生响应所用的时间.

总结

调度算法 (早期的三种)

• 学习思路
  • 算法思想 (为什么提出, 想解决什么问题)
  • 算法规则
  • 用于作业调度 还是 进程调度
  • 抢占式? 非抢占式?
  • 优缺点
  • 是否会导致 饥饿 (某进程/ 作业长期得到不服务)

先来先服务(FCFS, First Come First Serve)

• 算法思想
  • 主要从“公平”的角度考虑, 类似于排队买东西
• 算法规则
  • 按照作业/进程到达的先后顺序进行服务
• 作业调度 / 进程调度
  • 用于作业调度时, 考虑的是哪个作业先到达外存的后备队列; 用于进程调度时, 考虑的是哪个进程先到达内存的就绪队列
• 是否可抢占
  • 非抢占式算法
• 优缺点
  • 优点 : 公平 , 算法实现简单
  • 缺点 : 排在长作业(进程) 后的短作业需要等待很长时间, 带权周转时间大, 对短作业用户体验不好. FCFS算法对长作业有利, 对短作业不利. ( 好比买奶茶的时候, 你只买一杯, 前面一个人一次性买20杯, 你需要等好久才能买到那一杯)
• 是否会导致饥饿
  • 不会

短作业优先(SJF, Shortest Job First)

• FCFS对带权周转时间, 平均等待时间这些指标是不优秀的

• 算法思想

  • 追求最少的平均等待时间, 最 少的平均周转时间, 最少的带权平均周转时间.

• 算法思想

  • 最短的作业/进程优先得到服务( 最短 : 要求服务的时间最短) (已经到达的进程中选择服务时间最短)

• 用于作业/进程调度

  • 既可用于作业调度, 也可用于进程调度. 用于进程调度时, 短进程优先(SPF) 算法

• 是否可抢占

  • SJF 和 SPF都是非抢占式的算法, 但是也有抢占式的版本 – 最短剩余时间优先算法 (SRTN, Shortest Remaining Time Next)

• 优缺点

  • 优点 : “最短的” 平均等待时间, 平均周转时间
  • 缺点 : 不公平. 对短作业有利, 对长作业不利. 另外, 作业/进程的运行时间是由用户提供的, 并不一定真实(本来是长作业, 提交的数据却标记成短作业), 不一定能做到真正的短作业优先

• 是否饥饿

  • 可能产生饥饿现象, 如果一直源源不断来进程, 可能会导致长作业长时间得不到服务. 如果一致得不到服务. 就称为饿死

高响应比优先(HRRN)

• FCFS算法在每次调度的时候选择一个等待时间最长的作业(进程)服务. 没有考虑到作业的运行时间, 因此导致了对长作业友好, 短作业不友好

• SJF算法是选择一个执行时间最短的作业服务. 又完全不考虑各个作业的等待时间, 因此造成了对长作业不友好的问题, 甚至会造成饥饿
  问题

• 需要一个算法, 既考虑等待时间, 也兼顾运行时间 ---- 高响应比优先算法

• 算法思想

  • 要综合考虑作业/进程的等待时间和要求服务的时间

• 算法规则

  • 在每次调度时计算已到达的各个作业/进程的响应比, 选择响应比最高的作业/进程服务
  • 响应比 = (等待时间 + 要求服务时间) / 要求服务时间 (>=1)

• 是否可抢占

  • 非抢占式算法, 因此只有当前运行的作业/进程主动放弃处理机时, 才需要调度, 才需要计算响应比

• 优缺点

  • 优点 : 综合考虑了等待时间和运行时间(要求服务时间)
    • 等待时间相同时, 要求服务时间短的优先.(SJF的特点)
    • 要求服务时间相同时, 等待时间长的优先 (FCFS的特点)
    • (计算式也可以从这两个要求中退出来, 为什么是除以服务时间而不是等待时间)
    • 对于长作业来说, 随着等待时间越来越久, 其响应比也会越来越大, 从而避免了饥饿问题

• 是否饥饿

  • 不会
    

总结

• 上述三种算法, 用户交互性基本为0, 不关心响应时间, 一般适合于早期的批处理系统
  

调度算法

• 学习思路
  • 算法的提出背景
  • 算法的规则
  • 作业 or 进程
  • 优缺点
  • 是否可抢占
  • 是否饥饿

时间片轮转调度算法(RR, Round-Robin)

• 算法思想

  • 公平, 轮流地为各个进程服务, 让每个进程在一定时间间隔内都可以得到响应. 分时操作系统阶段提出的算法

• 算法规则

  • 按照各进程到达就绪队列的顺序, 轮流让各个进程执行一个时间片. 若进程未在一个时间片内执行外, 则剥夺处理机. 将进程重新放到就绪队列的末尾

• 作业?进程?

  • 用于进程调度. (只有作业从外存后备队列)

• 是否可抢占

  • 若进程未在指定时间内运行完, 将被强行剥夺处理机使用权, 因此时间片轮转算法属于抢占式的算法. 由时钟装置发出的时钟中断来通知CPU时间片已到

• 优缺点

  • 优点 : 公平, 响应快, 适用于分时操作系统
  • 缺点 : 由于高频的切换, 因此有一定的开销; 不区分任务的紧急程度

• 是否饥饿

  • 不会

• 时间片太大, 会导致每个进程都在自己的时间片内完成任务, RR退化成了FCFS; 时间片太小, 会导致频繁进行进程切换, 开销较大

优先级调度算法

• 算法思想

  • 随着计算机的发展, 特别是实时操作系统的出现, 出现越来越多的场景需要根据任务的紧急程度来决定处理顺序

• 算法规则

  • 每个作业/进程有各自的优先级, 调度时优先选择优先级最高的作业/进程

• 作业 or 进程

  • 都可以, 甚至还会用于之后的I/O调度

• 是否抢占

  • 都有. 非抢占式的只需要在进程主动放弃处理机时进行调度即刻; 抢占式的需要在就绪队列每次变化的时候, 检查是否发生抢占

• 优缺点

  • 优点 : 使用优先级区分紧急程度, 重要程度. 适用于实时操作系统. 可灵活地调整对各种作业/进程的偏好程度
  • 缺点 : 若源源不断有高优先级进程到来, 则可能导致低优先级进程饥饿

• 饥饿

  • 可能导致

• 补充

  • 就绪队列未必只有一个, 可以按照不同的优先级来组织. 另外, 也可以把优先级高的进程排在更靠近队头的位置
  • 根据优先级是是否可以动态改变, 可将优先级分为静态优先级 和 动态优先级
    • 静态优先级 : 创建进程时确定, 之后一直不变
    • 动态优先级 : 创建进程时有一个初始值, 之后会根据情况动态地调整优先级

• 如何设置各类型进程优先级

  • 系统进程 优先级 高于 用户进程
  • 前台进程 优先级 高于 后台进程
  • 操作系统更偏好I/O型进程 (或称I/O繁忙型进程), 与I/O繁忙型进程相对应的是计算型进程(或称CPU繁忙进程)
    • I/O设备可以和CPU并行工作. 如果I/O繁忙型进程优先级更高, 更有可能让I/O设备尽早投入工作, 和CPU并行工作, 则资源利用率, 系统吞吐量会得到提升

• 如果采用动态优先级, 什么时候应该调整

  • 从追求公平, 提升资源利用率的角度考虑
  • 如果进程在就绪队列中等待了过长时间, 可以适当提升 (类比于之前的高响应比优先)
  • 如果进程占用处理机很长时间, 可以适当降低优先级
  • 如果发现一个进程是频繁进行I/O操作, 则可适当提升优先级
    
    

多级反馈队列调度算法

• 算法思想
  • FCFS : 公平
  • SJF : 尽快处理完短作业, 平均等待时间, 平均周转时间等参数优秀
  • RR : 各个进程得到及时响应
  • 优先级 : 灵活调整各个进程被服务的机会
  • 对上述算法进行折中权衡
• 算法规则
  • 设置多级就绪队列, 各级队列优先级从高到低, 时间片从小到大
  • 新进程到达时先进入第1级队列, 按FCFS原则排队等待被分配时间片, 若用完时间片还未结束, 则进程进入下一级就绪队列队尾. 如果此时已经在最后一级队列, 则重新放回该队列队尾
  • 只有第k级队列为空时, 才会为k+1级对头的进程分配时间片
• 作业 or 进程
  • 用于进程调度
• 是否抢占
  • 抢占式算法. 在k级队列运行过程中, 若更上级的队列中进入了一个新进程, 说明该新进程优先级更高, 因此会抢占CPU, 原来运行的进程放回k级队列队尾
• 优点
  • 对各类型进程相对公平(FCFS的优点)
  • 每个新到达的进程都能很快得到响应(RR的优点)
  • 短进程只用较少的时间就可以完成(SJF的优点)
  • 不必实现估计进程的运行时间(避免用户作家)
  • 可灵活地调整对各类型进程的偏好程度: 比如CPU密集型进程, I/O密集型进程 (可以将因I/O阻塞的进程重新放回原队列, 这样I/O型进程就可以保持较高的优先级)
• 是否饥饿
  • 会. 如果有源源不断的短进程到达, 进入第一级就绪队列, 那些降级的队列可能一直得不到服务
    

总结

• Unix系统 : 多级反馈队列调度算法