1. 概念

CPU调度就是对CPU进行分配。从就绪队列中按照一定算法选择一个进程将CPU分配给它运行。

CPU三级调度

  • 高级（作业调度）：从外存后备队列中调选作业分配内存，使之可以竞争CPU
  • 中级（内存调度）：提高内存利用率，将不能运行的进程调至外存
  • 低级（进程调度）：最基本，给就绪队列中的进程分配CPU

2.实现

调度程序由三部分组成

  • 排队器
  • 分派器
  • 上下文切换器

不能进行调度&切换的情况

  • 处理中断过程中
  • 原子操作过程中（连中断都屏蔽）

进程调度方式

  • 非抢占调度
  • 抢占调度（允许更紧迫的插队）

常用计算

  • 周转时间=作业完成时间−提交时间周转时间= 作业完成时间-提交时间
  • 平均周转时间=（周转时间1+...+周转时间n)/n平均周转时间= （周转时间1+...+周转时间n)/n
  • 带权周转时间=作业周转时间作业实际运行时间带权周转时间=\frac{作业周转时间}{作业实际运行时间}
  • CPU利用率=CPU有效工作时间CPU有效工作时间+CPU空闲等待时间作CPU利用率=\frac{CPU有效工作时间}{CPU有效工作时间+CPU空闲等待时间作}

3.进程切换

上下文切换

用PCB表示（CPU寄存器的值+进程状态等）

先有资源调度（决策），再有进程切换（执行）

上下文切换&模式切换

  • 上下文：切换进程，昂贵，内核态
  • 模式：同一个进程，用户态、内核态切换

4.调度算法

  1. 先来先服务 FCFS

  2. 短作业优先 SJF

    • 平均等待时间、平均周转时间最优

  3. 高响应比优先

    • 响应比Rp=等待时间+要求服务时间要求服务时间R_p = \frac{等待时间+要求服务时间}{要求服务时间}​

      • 等待时间：截止目前每个进程已经排队的时长

    • 相比SIF算法克服了饥饿现象

  4. 优先级

    • 一般优先级原则
      • 系统进程>用户进程
      • 交互型>非交互性
      • I/O型>计算型

  5. 时间片轮转 RR

    • 按FCFS原则排好就绪队列，设定时间片大小
    • 给队首进程分配时间片
    • 执行一个时间片后，产生一个时钟中断，无论完成与否必须释放时间片
    • 被剥夺的进程返回队尾重新排队

  6. 多级队列

    • 适用于多CPU系统

  7. 多级反馈队列

    • 设置多个就绪队列，第1级队列优先级最高，其余逐个降低
    • 优先级越高，队列的时间片越小
    • 每个队列采用FCFS算法