CPU调度概念

调度的三个层次

• 高级调度（作业调度 Long-term schedule）：外存→内存，面向作业
  • 从后备队列选择合适的作业调入内存
  • 无→创建态→就绪态
  • 发生频率最低
• 中级调度（内存调度 Middle-term schedule）：外存→内存，面向进程
  • 从挂起队列选择合适进程将其数据调回内存
  • 挂起态→就绪态、阻塞挂起→阻塞态
  • 发生频率中等
• 低级调度（进程调度 Short-term schedule）：内存→CPU
  • 从就绪队列选择一个进程为其分配处理机
  • 就绪态→运行态
  • 发生频率最高
    
    计算密集型（compute-bound）
    I/O密集型（I/O-bound）

进程调度

进程调度的时机：

• 当前进程主动放弃CPU
  • 进程正常终止
  • 运行过程中发生异常而终止
  • 进程主动请求阻塞（等待I/O）
• 当前进程被动放弃CPU
  • 分给进程的时间片用完了
  • 有更紧急的事需要处理（如I/O中断）
  • 有更高优先级的进程进入就绪队列

    什么时候不能进程调度：

    在处理中断过程中
    进程在操作系统内核程序临界区中（普通的临界区是可以的，如打印机）
    原子操作过程中（原语）

进程调度的方式

• 非抢占式：只允许进程主动放弃CPU
• 抢占式：可以由操作系统剥夺当前进程CPU控制权
  • 当一个进程在CPU执行时，有更重要、更紧迫的进程需要使用CPU，则立即暂停当前进程，将CPU分配给更紧迫的那个进程。// 适用于分时操作系统、实时操作系统

进程的切换与过程

• 狭义进程调度：从就绪队列选中一个要运行的进程。
• 进程切换：指一个进程让出CPU，让给另一个进程的过程。
  1. 对原来运行进程数据保存
  2. 新进程数据恢复（程序计数器、程序状态字、数据寄存器等，存放在PCB）
• 广义进程调度：选择+进程切换

CPU调度算法评价指标

CPU利用率

$利用率=\frac{忙碌时间}{总时间}$

系统吞吐量

$系统吞吐量=\frac{总共完成了多少作业}{总共花费的时间}$

周转时间

作业被提交给系统开始，到作业完成为止的时间间隔。
包括四部分：

• 作业在外存后备队列等待作业调度时间
• 进程在就绪队列等待进程调度的时间
• 进程在CPU上执行时间
• 进程等待I/O操作完成时间

$$周转时间=作业完成时间-作业提交时间$$ $$平均周转时间=\frac{各作业周转时间之和}{作业数}$$ $$带权周转时间=\frac{作业周转时间}{作业实际运行时间}=\frac{作业完成时间-作业提交时间}{作业实际运行时间}$$ $$平均带权周转时间=\frac{各作业带权周转时间之和}{作业数}$$

等待时间

进程/作业处于等待CPU状态时间之和
进程：进程建立后等待被服务的时间之和
作业：建立进程后的等待时间 + 作业在外存后备队列中等待的时间

响应时间

用户提交请求到首次产生响应所用的时间

调度算法

批处理系统 Batch System

先来先服务 FCFS，First Come First Serve

进程按照请求CPU顺序使用CPU
用于作业调度，考虑哪个作业先到达后备队列；用于进程调度，考虑哪个进程先到达就绪队列
非抢占式算法
优点：公平、算法实现简单
缺点：对长作业有利，对短作业不利

短作业优先（SJF，Shortest Job First）

追求最少的平均等待时间，最少的平均周转时间，最少的平均带权周转时间
最短的作业时间，优先被得到服务。按照到达的进程/作业，最短运行的先服务。
非抢占式
抢占式（最短剩余时间优先算法）
优点：最短平均等待时间、平均周转时间
缺点：不公平，对短作业有利，长作业不利，可能产生饥饿现象

最短剩余时间优先算法（SRTN，Shortest Remain Time Next）

得到平均等待时间、平均周转时间最少
就是抢占式的短作业优先

高响应比优先（HRRN，Highest Response Ratio Next）

$响应比=\frac{等待时间+要求服务时间}{要求服务时间}$
每次调度先计算各个作业/进程的响应比，选择响应比最高的作业/进程为其服务
非抢占式算法
优点：综合考虑等待时间和运行时间
缺点：没有缺点

交互式系统 Interactive System

时间片轮转（Round-Robin）用于分时操作系统

算法思想：公平、轮流为各个进程服务
算法规则：按照各进程到达就绪队列顺序，轮流让进程执行一个时间片（如100ms），若进程未在时间片内执行完，就剥夺CPU，将进程重新放入就绪队列队尾
用于进程调度
抢占式算法，由时钟装置发出时钟中断来通知CPU
如果时间片太大，就会增大进程响应时间，退化为先来先服务调度算法
如果时间片太小，进程切换过于频繁，就会花费大量时间处理切换，导致实际执行时间比例减少。

优点：公平，响应快，适用于分时操作系统
缺点：高频率进程切换，有一定开销，不区分任务紧急程度

优先级调度算法（Priority Scheduling）

思想：场景需要根据任务紧急程度决定处理顺序
规则：每个作业/进程有各自的优先级，调度时选择优先级最高的。优先级一样，处理先到达的
既能作业调度，也能进程调度
抢占式、非抢占式都有
静态优先级：创建进程确定，之后一直不变
动态优先级：创建进程有一个初始值，之后动态调整
系统进程优先级高于用户进程
前台进程优先级高于后台进程
操作系统偏好I/O型进程（对整体利用率、吞吐量有提升）
动态调整：追求公平、提升资源利用率、频繁IO操作提升优先级
优点：优先级区分紧急程度、重要程度，适用于实时操作系统
缺点：如果源源不断高优先级，就会导致饥饿

多级反馈队列调度算法（Multi-level Feedback queue scheduling）

思想：前两种的折中
规则：

1. 设置多级就绪队列，各级队列优先级从高到低，时间片从小到大
2. 新进程到达进入一级队列，运行时间片用完（时间片没用完被抢占，就返回当前级队列）程序还未结束，放入下一级队列（当处于最后一级队列的时候，重新回到最后一级队列）
3. 只有第k级队列为空，才会为k+1级队头分配时间片

抢占式算法
优点：公平，每个进程都能得到快速响应，短进程经历较少时间就能完成，不必实现估计进程的运行时间，可以灵活调整对各类进程的偏好程度（I/O密集型进程偏好，可以放入当前优先级队列）
可能会导致饥饿

彩票调度（Lottery Scheduling）

按比例分配给进程彩票，然后抽奖，抽中彩票的就给分配一个时间片。

More：

Guarantee Scheduling
Fair-Share Scheduling

RealTime System 实时系统

实时系统：时间起主导的系统，要求计算机必须在一个确定的时间范围内作出反应
Minimizing Latency
Priority-Based Scheduling
Rate-Monotonic Scheduling
Earliest-Deadline-First Scheduling

线程调度

二级调度

• 内核级线程：系统范围竞争，需要完整的机器指令
• 用户级线程：用户范围竞争，切换需要少量机器指令