Linux - 调度策略

参考博客

• Linux进程调度-实时调度器

小结

• 优先级数值越低，则调度优先级越高
  • 0-99: 实时任务
  • 100-139: 普通任务
• 每个CPU都有三个运行队列
  • dl_queue: SHCED_DEADLINE策略的任务会在这个优先级里，距离当前时间点最近的Deadline任务会被选择执行
  • rt_queue
  • cfs_queue
  • dl > rt > cfs，因此调度点选择下一个待执行任务时，先选dl ->

Linux 的几种调度策略

实时进程

• 优先级高于普通进程：如果系统中始终有实时进程，那么普通进程将得不到调度【需要进一步明确】
• SCHED_ FIFO
  • 没有时间片的概念；当某FIFO线程被调度运行时，其可以占用CPU任意长的时间
  • 高优先级线程执行完成才会轮到较低优先级进/线程的执行
  • 高优先级线程可以抢占低优先级的线程
• SCHED_RR：
  • 时间片轮转
  • 高优先级可以抢占低优先级
  • 时间片用完后会被放入同一优先级队列的尾部，把CPU让给同一优先级的其它进程

普通进程（非实时进程）

• 强调公平性，防止进程饥饿
• SCHED_NORMAL
• SCHED_BATCH
• SCHED_IDLE

小结

• 编程时用户指定创建进程/线程的调度策略，内核会为其选择对应的调度器
• SCHED_FIFO/SCHED_RR均使用实时调度器RT
• SCHED_NORMAL/SCHED_BATCH均使用CFS调度器
• SCHED_IDLE使用IDLE调度器

Linux的调度器发展历程

1. 楼梯调度
   • 证明了完全公平思想的可行性
2. RSDL
   • 对SD算法的改进
   • 继承了“完全公平”的核心思想
3. CFS -> 目前采用的调度策略
   • 完全公平的核心思想
     • 有10个进程，在CPU时间10ms内，每个进程的运行时间应为(10ms/10) = 1ms
   • 不跟踪进程的睡眠时间
   • 不再区分交互式进程
   • 没有将任务维护在链表式的运行队列上
   • 对每个CPU维护一个以时间为顺序的红黑树

调度器管理模块

• 为了支持实时进程
• CFS提供了调度器模块管理器，各种不同的调度器算法都可以作为一个模块注册到该管理器中。不同的进程可以选择使用不同的调度器模块

1. 实时调度模块 (sched_rt.c)
   • 对应实时进程：SCHED_RR，SCHED_FIFO
   • 每个CPU的rt_rq中含有100个队列，分别对应优先级0-99；数字越低代表优先级越高
2. CFS调度模块 (sched_fair.c)
   • 对应普通进程：SCHED_NORMAL，SCHED_BATCH
   • 使用红黑树挂载所有的调度实体(进程/线程)；线程先后顺序使用虚拟执行时间进行
3. IDLE调度器
   • 管理SCHEd_IDLE类的线程

CFS调度器实现细节

参考

• Linux进程调度- CFS调度器

简要原理

• 调度器计算、维护、更新每个进程的虚拟执行时间 <- 来自进程执行时间【这两个都有相应的计算公式】
• ==调度点==时，调度器选择==虚拟执行时间较小==的进程进行切换 -> 期望分配给每个普通任务的CPU时间是相同的
• 虚拟执行时间计算时，要考虑到任务的==权重值==

虚拟执行时间计算

• nice值到权重的映射：nice值从-20 -> 19，每个任务的nice值是固定的，进而得到固定的权重：可以看到nice值越低，越容易获得CPU。默认nice值是0

  const int sched_prio_to_weight[40] = { 
  /* -20 */ 88761, 71755, 56483, 46273, 36291, 
  /* -15 */ 29154, 23254, 18705, 14949, 11916, 
  /* -10 */ 9548, 7620, 6100, 4904, 3906, 
  /* -5 */ 3121, 2501, 1991, 1586, 1277, 
  /* 0 */ 1024, 820, 655, 526, 423, 
  /* 5 */ 335, 272, 215, 172, 137, 
  /* 10 */ 110, 87, 70, 56, 45, 
  /* 15 */ 36, 29, 23, 18, 15, };

• 执行时间的计算：runtime = (sched_period * weight / sum(weights)) >> WMULT_SHIFT
• sched_period：默认为6ms，当任务较多时为：nr_running * 0.75(默认)
• 虚拟执行时间：vruntime += runtime * NICE0_LOAD / weight
• NICE0_LOAD也为一个常量

实时调度模块

参考

• Linux进程调度-实时调度器

BFS调度器