进程调度的概念

  • 内核决定将CPU分配给某个就绪进程的过程
    • 选择一个就绪的进程
      • 调度指标
      • 调度算法（策略）
    • 进程切换
      • 进程执行现场的切换（回顾进程）

一、进程调度的时机

  • 非抢占式/协作式(Non-preemptive)
    • 当一个进程从运行态切换到阻塞态（例如 发生I/O请求）
    • 当一个进程终止
  • 抢占式(Preemptive)
    • 当一个进程从运行态切换到就绪态（例如 出现时钟中断）
    • 当一个进程从阻塞态切换到就绪态（例如 I/O完成）

非抢占式情况下必须等待进程完成再考虑下一 步调度，抢占式可以在进程执行时切换进

二、进程调度的指标

  • CPU利用率（CPU utilization）
    • $\uparrow$ ，使CPU尽可能忙碌（0%-100%）
  • 吞吐量（throughput）
    • $\uparrow$ ，单位时间内进程完成的数量
  • 周转时间（turnaround time）
    • $\downarrow$，进程就绪到进程完成的时间
    • $T_{周转} = T_{完成} – T_{到达}$
    • 周转时间强调的是性能（performance） ，除此之外，还有一个很重要的指标：公平
  • 响应时间
    • $\downarrow$，交互式任务中，响应用户操作的时间
    • $T_{响应} = T_{首次运行}– T_{到达}$
  • …

工作负载假设

  • 完全可操作的调度准则：
    • 假设1.所有的任务运行相同的时间
    • 假设2. 所有的任务同时到达
    • 假设3. 一旦开始，所有任务保持运行直到完成
    • 假设4. 所有的任务只使用CPU（不考虑I/O）
    • 假设5. 每个工作的运行时间是已知的

三、进程调度的经典策略

先到先得（FCFS: First Come First Served）

  • 按照进程就绪的先后次序调度（非抢占式）
  • 优点：最“简单直接”的策略，易于实现（FIFO队列）

enter image description here

  • 弊端：混合任务场景下对短任务不友好，不适合交互环境

enter image description here

最短任务优先（SJF: Shorted Job First）

  • 先运行最短的任务，然后是次短的，以此类推（非抢占式）
  • 优点：避免出现护航效应，可以缩短平均周转时间
  • 弊端：效率依赖任务到达（进程就绪）时间

最短完成时间优先（STCF:Shortest Time-to-Complete First）

  • 用抢占式的调度思想，当有新进程就绪时，确定正在运行任务 和新任务谁的完成剩余时间少，并进行调度
  • 弊端：部分任务对响应时间非常敏感，快速响应可以增强用户交互体验

enter image description here

时间片轮转（RR:Round Robin）

  • 在一个时间片内运行一个任务，然后在下一个时间片切换到队 列中的下一个任务运行，而不是运行任务直到结束
  • 时间片必须是时钟中断的正整数倍
  • 时间片长短会影响系统性能，需要设计者做好权衡
    • 短时间片：减少响应时间，繁重的切换开销
    • 长时间片：避免频繁切换，增加响应时间

进程调度的目标本质就是权衡效率与公平

enter image description here

如果有I/O会怎么样（放宽假设4）

  • 重叠(overlap)思想可以提高利用率
  • 当任务发出I/O申请时放弃CPU
    • 任务会阻塞等待I/O完成
    • 调度程序需要选择其他进程在CPU上执行
  • 当I/O完成时候
    • 发出一个I/O完成的中断
    • 操作系统将进程从阻塞态变回就绪态，等待被调度

四、多级反馈队列

  • 通过历史经验预测未来
    • 通过优先运行短的任务来提升周转时间
    • 不利用任务长度的先验知识(priori knoledge)，而是进行预测
  • MLFQ有许多独立的队列(queues)
    • 每个队列被赋予了不同的优先级
  • 任何时刻，任务只能处于一个队列中
    • 规则1：高优先级的任务会被先执行
    • 规则2：同优先级的任务采取RR调度
  • MLQF根据观察到的行为调整任务的优先级
    • 规则3：新进程被置于最高优先级队列
    • 规则4a：任务用完时间片后，降低优先级
    • 规则4b：如果任务在时间片内主动放弃CPU，则优先级不变
      • 例如：
      • 如果一个任务不断放弃CPU去等待键盘输入，则保持它的优先级
      • 如果一个任务长时间占用CPU，则降低其优先级

enter image description here

  • （考虑I/O）MLFQ总是把交互式任务放在最高优先级
  • 适时提升优先级
    • 规则5：经过一段时间S，将所有任务重新加入最高优先级队列

enter image description here

  • 如何避免愚弄调度程序
    • 规则4：引入时间配额，一旦任务完成了在某一层队列中的时间配额，不论是主动放弃还是被动放弃，都降低其优先级

enter image description here

  • MLFQ调优
    • 高优先级：更短的时间片，
    • 低优先级：更长的时间片（还是一 种公平的体现）

enter image description here

小结

  • 进程调度：内核决定将CPU分配给某个就绪进程的过程
  • 进程的调度时机包含非抢占式和抢占式
  • 调度的指标包含：性能、公平
  • 经典调度策略：FCFS、SJF、STCF、RR
  • 多级反馈队列