调度

调度术语

术语辨析

• 被操作系统调度的是内核线程————而不是进程
• 然而，“线程调度”和“进程调度”这两个属于经常互换使用
• 当讨论一般概念时我们使用“进程调度”，当设计线程特定概念时使用“线程调度”
• 同时“在CPU上运行”实际是指在“CPU核心上运行”

注：CPU与CPU核心

• CPU可以包含多个核心。何以把CPU比作一座办公大楼，CPU核心是一个办公室，正在执行的线程就是一个正在工作的员工

进程调度

基本概念

• 进程执行由CPU执行和I/O等待的循环组成
• CPU突发和I/O突发交替进行
• CPU突发分布在进程间和计算机间差异很大，但遵循相似的曲线
• 通过多道程序设计获得最大的CPU利用率
• 当前进程处于I/O突发时，CPU调度器选择另一个进程

CPU调度器

调度决策选择

• CPU调度器从就绪队列中的进程中进行选择，并将CPU分配给其中一个进程
• CPU调度决策可能在一下情况发生
  • 进程从运行状态切换到等待状态
  • 进程从运行状态切换到就绪状态
  • 进程从等待状态切换到就绪状态
  • 进程终止
• 仅在条件1和4下的调度是非抢占式的
  • 一旦CPU被分配给进程，该进程会保持CPU直到终止或等待I/O
  • 也被称为协作式调度
• 抢占式调度还会在条件2和3下调度进程
  • 抢占式调度需要硬件支持，如定时器
  • 需要同步原语

注：协作式调度与抢占式调度

• 协作式调度：自觉排队
  • 基本思想：没有管理员的机房，每个人用完电脑后主动让给下一个人，程序自己决定什么时候停下来并主动分享资源
  • 什么时候让出CPU
    • 程序需要读写文件时（I/O）
    • 程序主动调用sleep休眠
    • 程序运行完毕退出
    • 程序主动调用yield让出
• 抢占式调度：由管理员的排队
  • 核心思想：有管理员的机房，管理员用定时器控制每个人的使用时间，到了时间就必须让出
• 什么时候强制切换
  • 时间片用完
  • 有更高优先级的程序要运行
  • 程序进行I/O操作时
  • 程序运行完毕

抢占

内核抢占

• 抢占也会影响系统内核的设计
• 如果在更新共享数据时被抢占，内核状态将会不一致
• 即当中断发生时内核正在服务系统调用
• 两种解决方案
  • 等待系统调用完成或I/O阻塞
  • 内核时非抢占式的，但对进程仍然是抢占式的
  • 在更新共享数据时禁用内核抢占
• 最新的Linux内核采用这种方法
  • Linux支持SMP
  • 共享数据受内核同步保护
  • 在内核同步时禁用内核抢占
  • 将非抢占式SMP内核转变为抢占式内核

用户抢占和内核抢占的具体时机

• 用户抢占
  • 从系统调用返回用户空间时
  • 从中断处理程序返回用户空间时
• 内核抢占
  • 当中断处理程序退出，返回内核空间之前
  • 当内核代码重新变为可抢占时
  • 如果内核中的任务显示调用schedule()
  • 如果内核中的任务阻塞（这会导致调用schedule）

分派器(Dispatcher)

• 分派器模块将CPU的控制权交给由段齐调度器选中的进程
• 切换上下文
• 切换到用户模式
• 跳转到用户程序中的正确位置以重启该程序
• 分派延迟：分派其停止一个进程并启动另一个进程所需的时间

调度标准

• CPU利用率：CPU忙碌的百分比
• 吞吐量：每个事件单位内完成执行的进程数量
• 周转时间：执行特定进程的事件
  • 从提交时间到完成时间
• 等待时间：在就绪队列中等待的总时间
• 相应时间：从请求提交到产生第一个相应所需的时间
  • 开始相应所需的时间

调度算法优化标准

• 一般来说，最大化CPU利用率和吞吐率，最小化周转时间、等待时间和响应时间
• 不同系统优化不同的值
• 在多数情况下优化平均值
• 在某些情况下，优化最小值或最大值
  • 例如：实时系统
• 对于交互式系统，最小化响应时间的方差

调度算法

先来先服务调度(FCFS)

• 总结：排队买票
• 核心思想：谁先来谁先服务，就像银行排队一样
• 工作原理
  • 按照进程到达的先后顺序执行
  • 第一个到达当地的进程先执行完，在执行第二个，以此类推
  • 一旦开始执行就不会被打断
• 优点：公平、简单、不会饥饿
• 缺点：短任务可能等很久（护航效应）

最短作业优先调整(SJF)

• 总结：快餐优先
• 核心思想：总是先做最快能完成的任务
• 工作原理：
  • 在所有等待的进程中，选择执行时间最短的执行
  • 可以大幅减少平均等待时间
  • 需要事先知道每个进程要执行多长时间
• 优点：平均等待时间最短（理论最优）
• 缺点：长任务可能永远轮不到（饥饿问题）

优先级调度(Priority)

• 核心思想：重要的任务先做
• 工作原理：
  • 每个进程都有一个优先级数字
  • 总是选择优先级最高的进程执行
  • 可以根据重要性动态调整优先级
• 老化机制：为了防止普通顾客永远等不到，可以让等待时间长的客户逐渐升级
• 优点：体现重要性，灵活可控
• 缺点：低优先级可能饥饿，需要防饥饿机制

时间片轮转调度(Round Robin)

• 核心思想：轮流服务
• 工作原理：
  • 给每个进程分配相同的时间片
  • 时间到了就强制切换到下一个进程
  • 没完成的进程重新排队等下一轮
• 优点：响应时间好，公平，适合交互式系统
• 缺点：频繁切换有开销，时间片大小难选择

多级队列调度(MLQ)

• 核心思想：分类服务
• 工作原理
  • 把进程分成几个固定的类别（系统进程、前台进程、后台进程等）
  • 每个类别有自己的队列和调度策略
  • 高优先级队列优先服务
• 优点：不同类型用最适合的策略，系统进程优先
• 缺点：底层队列可能饥饿，分类可能不准确

多级反馈队列调度(MLFQ)

• 核心思想：根据客户的行为表现动态调整服务等级
• 工作原理：
  • 新进程从最高优先级队列开始
  • 如果用完时间片还没完成，就降级到下一级队列
  • 如果主动让出CPU（比如等待I/O），可能提升等级
  • 等待太久的进程会自动升级（防止饥饿）
• 优点：最只能，自适应，段任务响应快，长任务不饥饿
• 缺点：最复杂，参数调整困难，实现开销大

MLQ详解

多级队列调度

• 多级队列调度
  • 就绪队列被分割为多个独立的队列
  • 例如：前台（交互式）进程和后台（批处理）进程
  • 进程被永久分配到指定的队列
  • 每个队列都有自己的调度算法
  • 例如：交互式进程使用RR，批处理进程使用FCFS
• 队列间调度
  • 必须子啊队列之间进行调度
  • 固定优先级调度
  • 存在饥饿的可能性
  • 时间片分配：每个队列获得一定数量的CPU时间，用于在其进程之间进行调度
  • 例如：前台进程80%时间用RR，后台进程20%时间用FCFS
• 多级反馈队列
  • 多级反馈队列调度使用多级队列
  • 进程可以在不同队列之间移动
  • 它试图推断进程的类型
  • 老化机制可以通过这种方式实现
  • 目标时给交互式和I/O密集型进程高优先级
• MLFQ定义参数
  • MLFQ调度器由以下参数定义
  • 队列数量
  • 每个队列的调度算法
  • 确定何时给进程分配更高优先级的方法
  • 确定何时降级进程的方法
  • 确定进程需要服务时进入那个队列的方法
  • MLFQ是最通用的CPU调度算法

线程调度

• 操作系统内核调度内核线程
• 系统竞争范围 (SCS)：系统中所有线程之间的竞争
• 内核不知道用户线程的存在
• 线程库将用户线程调度到LWP上
• 用于多对一和多对多线程模型
• 进程竞争范围 (PCS)：进程内部的调度竞争
• PCS通常基于用户设置的优先级
• 被调度到LWP的用户线程不一定在CPU上运行
• 操作系统内核需要将LWP的内核线程调度到CPU上