进程调度

Posted on | Edited on | In

调度策略

  • 目标

    • 进程响应时间尽可能快
    • 作业吞吐量尽可能高
    • 尽可能避免进程的饥饿现象
    • 低优先级和高优先级进程尽可能调和

  • Linux进程调度

    • 基于分时方式
    • 动态优先级，避免饿死

  • 进程分类

    • 交互式进程： 响应时间要求高
    • 批处理进程： 不需要尽快响应，吞吐量尽可能大
    • 实时进程：响应时间要求高，如机器人控制程序等。

  • 进程的抢占

  • 时间片长度

    • 折中：太长响应差；太短进程切换带来的额外开销高
    • Linux: 凭经验

调度算法

  • 最简单：扫描一遍可运行进程队列，选优先级最高的进程运行

    • 缺点：时间开销大

  • 调度类型

    • SCHED_FIFO: 先进先出的实时进程;没有优先级高的就继续使用CPU
    • SCHED_RR: 时间片轮转的实时进程；时间片到了就放弃
    • SCHED_NORMAL: 普通的分时进程

  • 普通进程的调度

    • 静态优先级
    • 基本时间片
      • 静态优先级越高，基本时间片越长

    • 动态优先级

      • max(100, min(静态优先级 - bonus + 5， 139))
      • bonus表示奖励和惩罚，与进程的平均睡眠时间有关
      • 平均睡眠时间也被调度程序用来确定一个给定进程是交互式进程还是批处理进程

    • 活动和过期进程

      • 活动进程： 还没有用完时间片
      • 过期进程： 已经用完了时间片

  • 实时进程的调度

    • 实时优先级
    • 调度程序总是让优先级高的程序运行
    • 实时进程被另外一个进程取代的条件
      • 进程被另一个具有更高实时优先级的实时进程抢占
      • 进程执行阻塞操作并进入睡眠
      • 进程停止或被杀死
      • 进程通过调用系统调用资源放弃CPU
      • 进程是基于时间片轮转的实时进程，并且用完了他的时间片

调度程序所使用的数据结构

  • runqueue

    • 每个CPU有一个runqueue

    • runqueue字段

    • arrays: 指向活动进程和过期进程的集合

  • 进程描述符

调度进程所使用的函数

  • scheduler_tick

    • 维持当前最新的time_slice计数器
    • 更新实时进程的时间片
      • 先进先出的实时进程：什么都不做
      • 时间片轮转的实时进程：递减时间片计数器并检查时间片是否用完
    • 更新普通进程的时间片
      • 递减时间片计数器。检查进程时间片是否用完。如果时间片用完，重新调度（P272）；否则，检查当前进程的剩余时间片是否太长

  • try_to_wake_up

    • 唤醒睡眠进程
    • 详细操作见P273

  • recalc_task_prio

    • 更新进程平均睡眠时间和动态优先级
    • 详细操作件见P275

  • schedule

    • 选择要被执行的新进程
    • 直接调用
      • 当前进程插入等待队列
      • 改变当前进程状态
      • 调用schedule
      • 检查资源时候可用
      • 若可用，从等待队列中删除当前进程
    • 延迟调用
    • schedule内部执行的详细操作参见P277

  • load_balance

    • 维持多处理器系统中运行队列的平衡

多处理器系统中运行队列的平衡

  • 不同类型的多处理器机器

    • 标准多处理器体系结构
    • 超线程
    • NUMA

  • 调度域

    • 调度域是一个CPU集合
    • 采用分层的组织形式
    • 调度域分层示例

  • rebalance_tick

    • 每一次时钟节拍调用一次
    • 确定运行队列中的进程数，并更新运行队列的平均工作量

  • load_balance

    • 检查是否可以通过把最繁忙的组中的一些进程迁移到本地CPU的运行队列来减轻不平衡状态；如果可以，函数尝试实现这个迁移。
    • 具体操作见P288

  • move_tasks

    • 把进程从源队列迁移到本地运行队列

与调度相关的系统调用

  • nice

    • 改变进程的基本优先级
    • 已被setpriority取代

  • getpriority 和 setpriority

    • 作用于给定组中所有进程的基本优先级

  • sched_getaffinity 和 sched_setaffinity

    • 返回和设置CPU的位掩码