CPU调度

基本概念

• CPU调度：每当CPU空闲时，操作系统必须按照一定的策略从就绪队列当中选择一个进程来执行
  • 调度的对象：进程或线程，也常称CPU调度为进程调度
• 程序代码
  • CPU约束型程序
    • 以计算为主，CPU区间会较多，还会有少量长的CPU区间
  • I/O约束型程序
    • 以I/O为主，但配合I/O处理会由大量短的CPU区间
• 非抢占式调度：由于主动让出CPU的情况发生，致使调度程序将CPU分配给某就绪进程的调度方式
  • 调度情况：因等待某些事情而让出CPU；进程的任务完成了，自动终止退出
  • 案例：早期的多道批处理操作系统
• 抢占式调度：操作系统将正在进行的进程强行暂停，由调度程序将CPU分配给其他就绪进程的调度方式
  • 调度情况：规定的时间片到了；出现了优先级更高的进程
  • 案例：大多数现代操作系统
• 分派程序
  • 将CPU的控制交给由短期调度程序选择的进程的模块
  • 每次进程切换时都要使用，所以应尽可能快
  • 分派延迟
    • 分派程序停止一个进程而启动另一个进程所要花的时间

调度准则

• 设计准则
  • 公平性
  • 响应时间短
    • 响应时间：从用户输入到产生反应的时间
  • 周转时间短
    • 周转时间：从任务提交到任务结束的时间
  • 吞吐量大
    • 吞吐量：单位时间完成的任务数量
    • = CPU使用率高 + 上下文切换代价小
• 矛盾
  • 响应时间短与公平性的矛盾
  • 吞吐量和响应时间之间的矛盾

综合考虑，任务可以分为交互式任务和批处理任务

调度算法

1. FIFO（先到先服务调度FCFS）

• 调度的顺序就是任务到达就绪队列的顺序
• 公平、简单、非抢占、不适合交互式（不利于短作业）

2. 最短作业优先调度SJF

• 最短的作业最先调度（CPU区间长度最小）
• SRJF（SJF的可抢占版本）
  • 平均等待时间更短
• 是优先级调度的特例（不适合交互式系统）

3. 优先级调度

• 每个任务关联一个优先级，调度优先级最高的任务最先调度
• 可能出现的情况：优先权太低的任务一直就绪，得不到运行（饥饿）
  • 处理方法：优先级动态调整
    • 老化技术：任务的优先级会随等待时间增长而不断增高

4. 轮转法调度RR

• 按时间片来轮转调。每一个进程在使用完一个时间片后，必须释放处理机给下一个就绪进程，而被剥夺的进程返回到就绪队列的末尾重新排队，等待再次运行（按照FCFS策略排成一个就绪队列）
• 特点：等待时间较短；上下文切换次数较多
• 时间片的设定
  • 时间片太大
    • 响应时间太长，变成FCFS
  • 时间片太小
    • 进程频繁地切换，处理及的开销增大
    • 吞吐量变小，周转时间变长

5. 多级队列调度（混合多种调度算法）

• 按照一定的规则建立多个进程队列
• 不同的队列有固定的优先级（高优先级有抢占权）
• 不同的队列可以给不同的时间片和采用不同的调度方法
• 问题：也存在一定程度的“饥饿”现象

6. 多级反馈队列

• 任务可以在队列之间移动，更细致的区分任务
• 可根据占用CPU时间多少来移动队列，阻止“饥饿”，可在PCB中记录其占用的CPU区间，作为移动依据
• 最通用的调度算法，多数OS都使用该方法或其变形

7. 多核CPU调度算法

• 问题
  • 对于多核处理器，每个CPU都有缓存，缓存着进程使用内存或寄存器等信息。
  • 当进程被OS调度到其他CPU时，CPU cache命中率可能就会降低
• CPU的亲和性affinity：进程/线程要在指定的CPU上尽量长时间地运行而不被迁移到其他处理器上（CPU关联性）
  • 软亲和性
    • 进程要在指定的CPU上尽量保持长时间，意味着进程通常不会在处理器之间频繁迁移
  • 硬亲和性
    • 利用内核提供给用户的API，强行将进程或者线程绑定到某一个指定的CPU核运行
• Linux

调度器	linux版本
O(n)的始调度算法	linux 0.11~2.4
O(1)调度器	linux 2.5
CFS调度器	linux 2.6~至今

• O(n)调度器（linux2.4版）
  • 采用一个runqueue运行队列来管理所有就绪进程
  • 调度器schedule会选择一个优先级最高（时间片最大）进程运行，同时对睡眠的进程增加一些时间片
  • 当runqueue运行队列中无进程可选择时，则会对系统中所有的进程进行依此重新计算时间片的操作，同时也会对时间片的进程做一次补偿
• O(1)调度器
  • 引入了per-CPU runqueue的结构，系统中所有的可运行状态的进程首先经过负载均衡模块挂入各CPU的runqueue
  • 每隔200ms检查CPU的负载是否均衡
    • 如果不均衡，负载均衡模块在CPU之间进行依此任务均衡操作，然后由各CPU调度器调度
  • 对于每个CPU
    • 每个cpu runqueue维护自己的active队列和expried队列
    • 当前cpu上运行进程的时间片用完后就会被放入expired队列中
    • 当active队列中所有进程的时间片都用完，进程执行完毕后，交换active队列和expired队列。所以expired队列就成了active队列（只需要指针的交换）
• 全局队列调度
  • 操作系统维护一个全局的任务等待队列
  • 当系统中有一个CPU核心空闲时，操作系统就从全局任务等待队列中选取就绪任务开始在核心上执行
  • 优点：CPU核心利用率较高
• 局部队列调度
  • 操作系统为每个CPU内核维护一个局部的任务等待队列
  • 当系统中有一个CPU内核空闲时，便从该核心的任务等待队列中选取恰当的任务执行
  • 优点：基本上无需在多个CPU核心间切换，有利于提高CPU核心局部Cache命中率
• linux（分时OS）的调度时机
  • 由用户引起的调度：创建进程、调用wait等让出CPU等
    • 此时的调度时机是系统调用返回（fork等都是系统调用）
  • 由内核引起的调度：时钟中断，给资源上锁等
    • 此时只需要在内核的适当位置调用schedule()