上文聊到了CFS的一个特性，调度周期，本文梳理一下cfs调度器的基本数据结构
# task_struct
在linux系统中，所有的任务都是一个task_struct，所以我们从这里作为起点
```
struct task_struct {
        volatile long                   state;  # 状态
        int                             on_cpu;  # 是否当前CPU 
        unsigned int                    cpu;  # CPU ID
        int                             on_rq;  # 是否在rq
        int                             prio;  # 优先级
        int                             static_prio;  # nice 优先级
        int                             normal_prio;  # 正常优先级
        unsigned int                    rt_priority;  # 实时优先级
        const struct sched_class        *sched_class;  # 调度类
        struct sched_entity             se;  # 调度实体
        struct sched_rt_entity          rt;  # rt的调度实体
        struct task_group               *sched_task_group;  # cgroup任务组
        struct sched_dl_entity          dl;  # dl的调度实体
        unsigned int                    policy;  # 策略
        int                             nr_cpus_allowed;  # 最大cpu值
        const cpumask_t                 *cpus_ptr;  # cpu_mask结构体
        cpumask_t                       cpus_mask;  # mask掩码
......
}
```
任务结构体管理调度实体，所以我们查看调度实体se
# sched_entity
```
struct sched_entity {
        /* For load-balancing: */
        struct load_weight              load; # 权重
        struct rb_node                  run_node; # rb-tree
        struct list_head                group_node; # cgroup任务组
        unsigned int                    on_rq; # 是否在rq

        u64                             exec_start; # 执行时间
        u64                             sum_exec_runtime; # 累计时间
        u64                             vruntime; # 运行时间
        u64                             prev_sum_exec_runtime; # 上次累计时间

        u64                             nr_migrations; # 迁移次数

        struct sched_statistics         statistics; # 统计信息

        int                             depth; # 深度，cgroup使用
        struct sched_entity             *parent; # 父节点，cgroup使用
        /* rq on which this entity is (to be) queued: */
        struct cfs_rq                   *cfs_rq; # cfs rq
        /* rq "owned" by this entity/group: */
        struct cfs_rq                   *my_q; # cgroup下的cfs rq
        /* cached value of my_q->h_nr_running */ 
        unsigned long                   runnable_weight; # h_nr_running 

        struct sched_avg                avg; # 负载均衡
};
```
调度实体管理运行队列，所以接下来看cfs_rq
# cfs rq
```
struct cfs_rq {
        struct load_weight      load; # 权重
        unsigned int            nr_running; # 调度实体数量

        u64                     exec_clock; # 累计时钟
        u64                     min_vruntime; # 最小运行时间

        struct rb_root_cached   tasks_timeline; # rb-tree 根

        /*
         * 'curr' points to currently running entity on this cfs_rq.
         * It is set to NULL otherwise (i.e when none are currently running).
         */
        struct sched_entity     *curr; # 当前se指针
        struct sched_entity     *next; # 下个se指针
        struct sched_entity     *last; # 上个se指针
        struct sched_entity     *skip; # 需要跳过的se指针
......
}
```
runqueue管理的是rb-tree，所以接下来看rb-tree结构 tasks_timeline
# tasks_timeline
```
struct rb_root_cached {
        struct rb_root rb_root; # rb-tree 根
        struct rb_node *rb_leftmost; # rb-tree 最左节点
};
```
到这里，cfs的基本结构大致为`task_struct->sched_entity->runqueue->rb-tree`   
但是还有一个不应该忽视的，就是cgroup下的组调度
# task_group
```
struct task_group {
        struct cgroup_subsys_state css; # cgourp状态

#ifdef CONFIG_FAIR_GROUP_SCHED
        /* schedulable entities of this group on each CPU */
        struct sched_entity     **se; # 调度实体
        /* runqueue "owned" by this group on each CPU */
        struct cfs_rq           **cfs_rq; # runqueue
        unsigned long           shares; # cgoup 份额
#ifdef CONFIG_RT_GROUP_SCHED
        struct sched_rt_entity  **rt_se; # rt的调度实体
        struct rt_rq            **rt_rq; # rt的runqueue

        struct rt_bandwidth     rt_bandwidth; # rt带宽控制
        struct cfs_bandwidth    cfs_bandwidth; # cfs带宽控制
#endif
......
}
```
task_group 中有两个重要的成员：其一是sched_entity 指针的数组，将其插入到其父 cfs_rq 的红黑树中，实现组级公平竞争，另一个则是 cfs_rq，用于管理该组内任务的调度队列。我们可以看到重点在task_group的分组行为。   

默认情况下，可以按照上面描述的流程管理`task_struct->sched_entity->runqueue->rb-tree`，但实际上，可以通过cgroup分组，那么其流程管理为`task_struct->task_group->sched_entity->runqueue->rb-tree`    
通过添加这么一个组的概念，借助my_q就可以使得cpu上的任务可以按组来管理了。

# 总结
本文将调度大的框架上的基本数据结构的交互进行了一个说明，可能很轻松的了解到调度在数据结构上是如何实现or流转的，同样的，我也整理了图示，如下

![image.png](/static/img/80281b3f5e19cf6539a6a12cb39ff81a.image.webp)

可以看到，所谓调度，就是从task_struct中，找到group/task内的se，通过se下的runqueue找到rb-tree，然后通过rb-tree进行任务管理，简单明了。

更详细一点的图片如下，摘自网络，意思一致

![image.png](/static/img/9f620d420a11c6d0d48f002dc1dc0991.image.webp)


# 参考
> https://blogs.oracle.com/linux/cfs-group-scheduling



调度(7)-CFS基本数据结构

CFS为了局部的公平性， 引入了一个概念叫做调度周期，什么是调度周期，就是每个进程在一个周期内至少运行一次。本文说明一下CFS的调度周期

# 调度周期的实现
调度周期是为了保证CFS调度器上的进程在一个周期内至少运行一次，那么怎么保证的呢？我们跟踪一下代码
```
        if (td->mode == TICKDEV_MODE_PERIODIC)
                tick_setup_periodic(newdev, 0);
```
这里调度周期来自timer的periodic模式
```
tick_setup_periodic
  tick_set_periodic_handler
    dev->event_handler = tick_handle_periodic
```
这里tick_handle_periodic的流程
```
tick_handle_periodic
  tick_periodic
    update_process_times
      scheduler_tick
        curr->sched_class->task_tick(rq, curr, 0);
          task_tick_fair
            entity_tick
              check_preempt_tick
                sched_slice
                  __sched_period
```
这里`__sched_period`是最终的实现，其返回了调度周期，实现如下
```
/*
 * The idea is to set a period in which each task runs once.
 *
 * When there are too many tasks (sched_nr_latency) we have to stretch
 * this period because otherwise the slices get too small.
 *
 * p = (nr <= nl) ? l : l*nr/nl
 */
static u64 __sched_period(unsigned long nr_running)
{
        if (unlikely(nr_running > sched_nr_latency))
                return nr_running * sysctl_sched_min_granularity;
        else
                return sysctl_sched_latency;
}
```
我们查看这三个值
* sched_nr_latency
* sysctl_sched_latency
* sysctl_sched_min_granularity


```
static unsigned int sched_nr_latency = 8;
unsigned int sysctl_sched_latency                       = 6000000ULL;
unsigned int sysctl_sched_min_granularity                       = 750000ULL;
```
这代表什么意思呢？
1. 核心上的任务临界值是8（经验值）
2. 少于等于8个任务的时候按照6ms周期
3. 大于8个任务的时候按照0.75ms * 任务数量作为周期

值得注意的是，这个计算公式是纯经验值，任何人都可以手动sysctl修改看看效果。

# 怎么保证周期性
上面知道了调度周期的计算方式，实际上就是在进行抢占来实现的，简单来说就是通过update_curr计算好vruntime，然后用 check_preempt_tick 判断是否超周期了，如果超周期了，那么就实施抢占。我们看看check_preempt_tick的策略
```
static void
check_preempt_tick(struct cfs_rq *cfs_rq, struct sched_entity *curr)
{
        unsigned long ideal_runtime, delta_exec;
        struct sched_entity *se;
        s64 delta;
        bool skip_preempt = false;

        ideal_runtime = sched_slice(cfs_rq, curr);
        delta_exec = curr->sum_exec_runtime - curr->prev_sum_exec_runtime;
        trace_android_rvh_check_preempt_tick(current, &ideal_runtime, &skip_preempt,
                        delta_exec, cfs_rq, curr, sysctl_sched_min_granularity);
        if (skip_preempt)
                return;
        if (delta_exec > ideal_runtime) {
                resched_curr(rq_of(cfs_rq));
                /*
                 * The current task ran long enough, ensure it doesn't get
                 * re-elected due to buddy favours.
                 */
                clear_buddies(cfs_rq, curr);
                return;
        }

        /*
         * Ensure that a task that missed wakeup preemption by a
         * narrow margin doesn't have to wait for a full slice.
         * This also mitigates buddy induced latencies under load.
         */
        if (delta_exec < sysctl_sched_min_granularity)
                return;

        se = __pick_first_entity(cfs_rq);
        delta = curr->vruntime - se->vruntime;

        if (delta < 0)
                return;

        if (delta > ideal_runtime)
                resched_curr(rq_of(cfs_rq));
}
```
首先我们知道resched_curr就是抢占操作，那么代码有两个点是运行抢占的，如下
## 抢占点1
```
 if (delta_exec > ideal_runtime)
```
如果任务跑的时机大于理想认为的周期时间了，那么抢占
## 抢占点2
```
if (delta > ideal_runtime)
```
这段逻辑需要结合一下上下文代码，如下
```
 se = __pick_first_entity(cfs_rq);
        delta = curr->vruntime - se->vruntime;
```
因为cfs是利用rb-tree构建，rb-tree可以查看我之前的文章。所以这里se就是最小vruntime的调度实体。   
那么delta就是当前时间减去最应该被调度的任务,如果大于周期，那么强行抢占。

可以看到，抢占点2其实就是一段客制化代码，其用于避免cfs的starvation问题（饿死问题）
## 注意点1
除了两个抢占点，check_preempt_tick还有一个特殊return，那就是
```
if (delta_exec < sysctl_sched_min_granularity)
                return;
```
这里意思也很明确，就是当前任务如果运行时间太短，那就不抢占了。这笔内容其实就是缓解调度的高开销。
# 总结
本文详细的介绍了CFS的另一个重要概念就是调度周期，CFS为了维持局部的公平性，专门引入的调度周期，这样使得任务不会被饿死。而实现所谓的调度周期的办法就是增加抢占点，让满足调度周期的任务强行被抢占了。



调度(6)-CFS调度周期

之前讨论的CFS的weight，通过weight的设置，可以使得其相比于步幅调度具备局部更多的公平，本文进一步的讨论vruntime是的计算方式，有些大的公式在讨论权重的时候已经介绍一点了。

# virtual runtime
回顾公式`vruntime += delta * nice0 / weight`，可以看到，cfs调度器通过vruntime来平衡任务的公平性，所以在cfs中，我们不能单看weight这一个影响因子，只需要看vruntime的大小就能知道一个任务的优先级顺序，vruntime越小，则越容易被调度。

我们跟踪代码，看看vruntime是怎么自加的
```
update_curr
  curr->vruntime += calc_delta_fair(delta_exec, curr);
    delta = __calc_delta(delta, NICE_0_LOAD, &se->load);      
```
其核心计算函数为
```
/*
 * delta_exec * weight / lw.weight
 *   OR
 * (delta_exec * (weight * lw->inv_weight)) >> WMULT_SHIFT
 *
 * Either weight := NICE_0_LOAD and lw \e sched_prio_to_wmult[], in which case
 * we're guaranteed shift stays positive because inv_weight is guaranteed to
 * fit 32 bits, and NICE_0_LOAD gives another 10 bits; therefore shift >= 22.
 *
 * Or, weight =< lw.weight (because lw.weight is the runqueue weight), thus
 * weight/lw.weight <= 1, and therefore our shift will also be positive.
 */
static u64 __calc_delta(u64 delta_exec, unsigned long weight, struct load_weight *lw)
{
        u64 fact = scale_load_down(weight);
        int shift = WMULT_SHIFT;

        __update_inv_weight(lw);

        if (unlikely(fact >> 32)) {
                while (fact >> 32) {
                        fact >>= 1;
                        shift--;
                }
        }

        fact = mul_u32_u32(fact, lw->inv_weight);

        while (fact >> 32) {
                fact >>= 1;
                shift--;
        }

        return mul_u64_u32_shr(delta_exec, fact, shift);
}
```
上述代码的公式
```
vruntime_delta = delta_exec * (weight / lw->weight)
               = (delta_exec * weight * lw->inv_weight) >> WMULT_SHIFT
#define WMULT_SHIFT    32
```
这个在权重篇介绍过，inv_weight 是 weight 的速算表。此时我们再代入公式`vruntime += delta * nice0 / weight`可以将公式抽象成如下
```
vruntime_delta = wall_time_delta * (NICE_0_weight / NICE_k_weight)
               = wall_time_delta * (NICE_0_weight * 2^32 / (NICE_k_weight * 2^32))
               = (wall_time_delta * (NICE_0_weight * 2^32 / NICE_k_weight)) >> 32
               = (wall_time_delta * NICE_0_weight * (2^32 / NICE_k_weight)) >> 32
```
注意其中`2^32 / NICE_k_weight`其实就是`sched_prio_to_wmult`本存放在`load_weight`结构上
```
struct load_weight {
        unsigned long                   weight;
        u32                             inv_weight;
};
```
回到代码`__calc_delta`上，实际上是分两个步骤上计算的。   
步骤1，`fact = mul_u32_u32(fact, lw->inv_weight);`   
这里计算公式为
```
fact = (weight / lw->weight) * 2^32
```
步骤2，`mul_u64_u32_shr(delta_exec, fact, shift);`   
这里计算公式为
```
delta_exec * fact >> 32
```
两个公式整合就是原公式了。
```
vruntime_delta = delta_exec * (weight / lw->weight)
```
# 总结
本文介绍了vruntime的公式由来，可以清晰的知道vruntime的计算公式，如果想了解此计算公式的可以详细查看一下，不过一般调试过程中不会太关注这个公式，本文只是知识归纳总结一下而已。

# 参考
> http://www.wowotech.net/process_management/447.html





调度(5)-CFS的vruntime

之前讨论的调度器的设计两大思想，启发式算法和调度类。现在我们深入到linux官方调度器CFS上查看cfs调度器的设计思想

# 什么是CFS
CFS也就是Completely Fair Scheduler，完全公平调度器，顾名思义。   
那怎么做到完全公平呢？我举个例子，假设有3个任务，每个任务的处理时间都是33.33%，那么它们公平了吗。答案是是的，这种调度器是公平调度器，但却不是完全公平调度器，为什么呢。

这种公平调度器在传统操作系统上其实叫做 步幅调度，怎么理解
1. 每个任务按照严格的比例划分
2. 提供一个share概念，是每个进程按照比例分到的蛋糕
3. 提供一个stride概念，每次运行之后就像前进一样，加上stride
4. 提供一个pass概念，作为任务默认的初始值，每次运行后加上步子

那么步幅调度简单理解就是所有的进程在多个跑道上跑步，他们的起始点是pass值，我们通过进程的比例来决定份额share，如果share高，那么他同一时刻是优先跑。那么等价share可以换算成stride，也就是每个人的步子，同一时刻下份额高，那么步子低，也就是说stride低的先跑。每次时刻跑完了记录pass上自加stride

换句话说，现实生活中，每个人的步幅高，他就跑的快，步幅高是单位时间内某人步子更大，他天生就会比普通人快，但是我们要追求公平，所以我们让哪些跑的慢的同学，也就是单位时间步子小的同学占更大的份额，这样可以保证即使每个同学最终都是平均的到达终点

在实际情况下，跑得快的同学可以考虑情绪价值等一下跑的慢的同学，这是主观行为   
在调度的设计中，机制让跑得快的同学一定要等跑得慢的同学，这是机制

一个跑步的图片，摘自网络

![image.png](/static/img/808f41939cb63e5ffa29b5f1238fbdcb.image.webp)

步幅调度的图片，摘自论文

![image.png](/static/img/18e5556a259662761853bb8d3410e594.image.webp)

理解了步幅调度，那么我们理解CFS就更轻松了，因为一个是公平调度，一个是完全公平调度。一方面他们的维持公平的原理是一致的，另一方面，它考虑了公平调度的缺点，去适当按照启发式的算法尝试做到完全公平

## 公平的概念
CFS和步幅调度很相似，在步幅调度中，stride越小，那么进程越容易被调度，而在cfs中，步幅不再存在，我们按照vruntime越小决定进程越容易被调度

那哪些地方需要做启发式的算法呢，我们可以先看看步幅调度的缺点

问题1. 新的任务进来时，pass肯定比旧的任务小，那么步幅调度一定优先调用新进程。这会导致眼下对其他任务并不公平。  
问题2. 假设系统存在很高份额的任务，那么步幅调度肯定优先调用高份额低步幅的任务，如果低步幅的任务数量多，运行时间短，那么会导致眼下对其他任务并不公平。

可以看到，启发式算法要做到完全的公平，而不是绝对的公平。

完全的公平指的是既要整体上按照公平调度，也要在局部或眼下维持一定的公平。

# 权重
对于步幅调度，其时间为pass+stride不断累积，上图可以看到pass一直增加。它是决定公平   
而对于CFS调度，需要维护局部的公平，所以增加了权重的概念。那么它计算公式需要乘以权重，如下
```
vruntime += delta * nice0 / weight
```
这里delta和nice0是很好理解，weight存在的意义就是局部最优的实施。
```
/*
 * Nice levels are multiplicative, with a gentle 10% change for every
 * nice level changed. I.e. when a CPU-bound task goes from nice 0 to
 * nice 1, it will get ~10% less CPU time than another CPU-bound task
 * that remained on nice 0.
 *
 * The "10% effect" is relative and cumulative: from _any_ nice level,
 * if you go up 1 level, it's -10% CPU usage, if you go down 1 level
 * it's +10% CPU usage. (to achieve that we use a multiplier of 1.25.
 * If a task goes up by ~10% and another task goes down by ~10% then
 * the relative distance between them is ~25%.)
 */
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,
};
```
根据注释可以理解，这里给定了sched_prio_to_weight，其值其实是一个近似计算的经验值，也就是每1个nice下，按照cpu下降10%的实测数据估算，这个比例~25%。   
这里10%也可以估算。如下  
假设A为n，B为n+1，那么
```
weight_a = 1024 / 1.25 ^ n   
weight_b = 1024 / 1.25 ^ (n + 1)
percentage_a = weight_a / (weight_a + weight_b)
percentage_b = weight_b / (weight_a + weight_b)
```
我拿最简单的权重计算
```
36 + 29 = 65
a = 36 / 65 = 55.38%
b = 29 / 65 = 44.61%
55.38% - 44.61% = 10.77% ~= 10%
29 * 1.25 = 36.25 ~= 36
```


实际上，为了代码实施的高性能，内核讨巧的提供了另一个预运算的查表sched_prio_to_wmult 
```
/*
 * Inverse (2^32/x) values of the sched_prio_to_weight[] array, precalculated.
 *
 * In cases where the weight does not change often, we can use the
 * precalculated inverse to speed up arithmetics by turning divisions
 * into multiplications:
 */
const u32 sched_prio_to_wmult[40] = {
 /* -20 */     48388,     59856,     76040,     92818,    118348,
 /* -15 */    147320,    184698,    229616,    287308,    360437,
 /* -10 */    449829,    563644,    704093,    875809,   1099582,
 /*  -5 */   1376151,   1717300,   2157191,   2708050,   3363326,
 /*   0 */   4194304,   5237765,   6557202,   8165337,  10153587,
 /*   5 */  12820798,  15790321,  19976592,  24970740,  31350126,
 /*  10 */  39045157,  49367440,  61356676,  76695844,  95443717,
 /*  15 */ 119304647, 148102320, 186737708, 238609294, 286331153,
};
```
根据注释可以知道，他们的公式刚刚差2^32，也就是
```
sched_prio_to_wmult[prio] ≈ (2³²) / sched_prio_to_weight[prio]
```
在代码里面计算如下
```
                lw.weight = scale_load(sched_prio_to_weight[prio]);
                lw.inv_weight = sched_prio_to_wmult[prio];
```
## nice的归一化
在内核中，nice默认归一化为1024，我们可以看到如下定义
```
#ifdef CONFIG_64BIT
# define NICE_0_LOAD_SHIFT      (SCHED_FIXEDPOINT_SHIFT + SCHED_FIXEDPOINT_SHIFT)
# define scale_load(w)          ((w) << SCHED_FIXEDPOINT_SHIFT)
# define scale_load_down(w) \
({ \
        unsigned long __w = (w); \
        if (__w) \
                __w = max(2UL, __w >> SCHED_FIXEDPOINT_SHIFT); \
        __w; \
})
#else
# define NICE_0_LOAD_SHIFT      (SCHED_FIXEDPOINT_SHIFT)
# define scale_load(w)          (w)
# define scale_load_down(w)     (w)
#endif

```
这里sched fixed point shift为
```
# define SCHED_FIXEDPOINT_SHIFT               10
```
所以我们可以得到两个概念
1. nice的归一化为1024
2. nice的shift按照bit64/32决定，分别是20/10

那么这个shift在bit64上扩大为20也就意味着NICE_0_LOAD 的值从1024变大为1048576。换算到公式`vruntime += delta * nice0 / weight`相当于扩大了vruntime的计算精度，因为本身bit64可以算的值更大，这样调度的颗粒度能更加精确。但无论如何，我们统一理解nice的归一化是1024是没有任何问题的

# 总结
本文介绍了cfs调度的概念，并且提到了cfs的一个重要概念，权重，通过权重可以进行调度的启发式计算。

# 参考
> https://web.eecs.umich.edu/~mosharaf/Readings/Stride.pdf

调度(4)-CFS调度器和权重

之前提到了O(1)的调度器，这在当前的绝大部分RTOS中已经运用了，但是为什么Linux要在O(1)调度器上进一步开发完全公平的调度器CFS呢。主要原因是动态优先级本身是基于定制策略设置的，这就意味着它不是非常的通用，当系统运行在不同的环境中，需要不断的调整其设定规则来调整优先级。

所以Linux这种面向更通用的内核，更需要一个通用性强的调度策略，而非定制式的调度策略。同样的，在RTOS中，本身很多业务就是定制化的，所以可以看到RTOS的演进中，在动态优先级这里就逐渐停止，因为用户直接定制优先级就可以获得最优调度策略。

# 启式算法
Heuristic algorithms 本身是用来解决复杂问题的一种思路，当一个问题需要解决的时候，如果使用明确的解题步骤去解决，那么可能耗费的人力物力和财力都不成正比，那么我们可以从找到正确答案的角度转换成找到近似解的角度。  
所以启发式算法的目的并不是找到正解，而是通过简单的尝试来猜测可能解。  

在Linux内核中，很多时候都可以看到启发式算法。最简单最常见的是panic。当某个核心panic的时候，内核总是打印那个核心上的kworker，通常我们查看panic日志的时候，有可能分析的kworker并不代表问题出在当前kworker上，而是出现在可能其相关的kworker上。这里总是打印当前核心的panic日志就是启发式搜索  

另一个例子，lockup detector和hung task detector 在检测死锁的时候，默认按照预设的时间判断timeout，如果超时，则打印panic日志。这里timeout值就是启发式算法  

说回调度，CFS为了保证所有的任务一定的公平性，设计了vruntime的概念，如果某个任务分配到的实际时间少，那么cfs给他补足时间，允许接下来给他更多的机会获取使用时间。就好像吃奶的小孩似的，vruntime越小，说明要给他的时间越多，也就是越应该容易被调度的任务。   

值得注意的是，我们在rtos中查看的调度器实现，对于io的停滞时间都是事后计算的，因为没法统计需要实际io出去了多久。在linux中也一样，cfs调度器给vruntime越小的任务分配更多的资源就是为了弥补io出去后的时间过多的任务，下次让vruntime更小的任务运行。所以vruntime就是一种典型的启发式算法。

启发式算法的优点是将定制转向通用，在面对通用下出现的庞大数量级的场景下，提供尽可能正确的局部最优解。CFS的算法的核心就是尽可能的提供公平。 

《我只说三件事：公平，公平，还是公平》
# 调度类
说起调度，一个非常重要的思想也是必须要说明的，这就是 `struct sched_class` 

首先，我们知道不同的调度器都是通过 `struct sched_class` 实现，同样的，对于新增的调度器也可以通过实例化这个调度类来完成。对于这个类本身，只需要实现调度器该有的函数回调，例如enqueue，dequeue，yield，pick_next_task 这种调度操作，如下
```
struct sched_class {
        void (*enqueue_task) (struct rq *rq, struct task_struct *p, int flags);
        void (*dequeue_task) (struct rq *rq, struct task_struct *p, int flags);
        void (*yield_task)   (struct rq *rq);
        bool (*yield_to_task)(struct rq *rq, struct task_struct *p);

        void (*check_preempt_curr)(struct rq *rq, struct task_struct *p, int flags);

        struct task_struct *(*pick_next_task)(struct rq *rq);

        void (*put_prev_task)(struct rq *rq, struct task_struct *p);
        void (*set_next_task)(struct rq *rq, struct task_struct *p, bool first);
        void (*task_tick)(struct rq *rq, struct task_struct *p, int queued);
        void (*task_fork)(struct task_struct *p);
        void (*task_dead)(struct task_struct *p);

        void (*switched_from)(struct rq *this_rq, struct task_struct *task);
        void (*switched_to)  (struct rq *this_rq, struct task_struct *task);
        void (*prio_changed) (struct rq *this_rq, struct task_struct *task,
                              int oldprio);

        unsigned int (*get_rr_interval)(struct rq *rq,
                                        struct task_struct *task);

        void (*update_curr)(struct rq *rq);
} __aligned(STRUCT_ALIGNMENT); 
```


其次，有哪些调度器基于调度类实现呢，这个问题其实就是内核有哪些调度器实例化了sched_class，如下
```
const struct sched_class rt_sched_class
const struct sched_class fair_sched_class
const struct sched_class idle_sched_class
const struct sched_class stop_sched_class
const struct sched_class dl_sched_class
```
可以看到，内核实现了5个调度器。

在较新的linux源码上，对sched_class抽象成了宏定义，如下
```
#define DEFINE_SCHED_CLASS(name) \
const struct sched_class name##_sched_class \
	__aligned(__alignof__(struct sched_class)) \
	__section("__" #name "_sched_class")
```

其原理是不变的，可以看到不同的调度实现上是通过宏来实现

![image.png](/static/img/fe3e863751700b61133e7c8cedd520c4.image.webp)

我们可以留意 `__section("__" #name "_sched_class")`，可以发现，其会生成一个section，所以我们从vmlinux.lds.h找答案

先看RODATA的定义
```
#define RO_DATA(align)                                                  \
        . = ALIGN((align));                                             \
        .rodata           : AT(ADDR(.rodata) - LOAD_OFFSET) {           \
                __start_rodata = .;                                     \
                *(.rodata) *(.rodata.*)                                 \
                SCHED_DATA                                              \
                RO_AFTER_INIT_DATA      /* Read only after init */      \
                . = ALIGN(8);                                           \
                __start___tracepoints_ptrs = .;                         \
                KEEP(*(__tracepoints_ptrs)) /* Tracepoints: pointer array */ \
                __stop___tracepoints_ptrs = .;                          \
                *(__tracepoints_strings)/* Tracepoints: strings */      \
        }                                                               \

```
这里留意 SCHED_DATA，查看实现
```
#define SCHED_DATA                              \
        STRUCT_ALIGN();                         \
        __begin_sched_classes = .;              \
        *(__idle_sched_class)                   \
        *(__fair_sched_class)                   \
        *(__rt_sched_class)                     \
        *(__dl_sched_class)                     \
        *(__stop_sched_class)                   \
        __end_sched_classes = .;
```
可以看到其被设计从不同的区域。那么决定不同调度器的优先级的是如何处理的呢？   
可以看pick_next_task函数
```
static inline struct task_struct *
pick_next_task(struct rq *rq, struct task_struct *prev, struct rq_flags *rf)
{
        for_each_class(class) {
                p = class->pick_next_task(rq);
                if (p)
                        return p;
        }
}
```
在这里，展开一下for_each_class的实现
```
#define sched_class_highest (__end_sched_classes - 1)
#define sched_class_lowest  (__begin_sched_classes - 1)

#define for_class_range(class, _from, _to) \
        for (class = (_from); class != (_to); class--)

#define for_each_class(class) \
        for_class_range(class, sched_class_highest, sched_class_lowest)

```
这些就明了了，其就是利用了ld编排的数据顺序进行遍历，那么调度类的优先级顺序如下
1. stop
2. dl
3. rt
4. fair
5. idle

最新新增了一个sched_ext，它的顺序如下
```
#define SCHED_DATA				\
	STRUCT_ALIGN();				\
	__sched_class_highest = .;		\
	*(__stop_sched_class)			\
	*(__dl_sched_class)			\
	*(__rt_sched_class)			\
	*(__fair_sched_class)			\
	*(__ext_sched_class)			\
	*(__idle_sched_class)			\
	__sched_class_lowest = .;
```
可以看到，ext的优先级倒数第二，关于sched_ext的设计哲学的事情，后面再详细展开。

# 总结
本文从调度器设计的角度提到了两个很重要的点，启发式算法和调度类。启发式算法让调度器能够看似公平的解决调度问题，从而找到局部最优解，拜托了高度定制的优先级策略，而调度类能够让内核轻松的实现多种调度器，而不是一个调度策略一个轮子。

说个实际工程中的问题，随着preempt-rt补丁兴起，很多所谓的linux操作系统高级专家们，又逐渐将cfs这类启发式的调度策略，退化成rt这样靠定制优先级来解决工程问题的局面。大家转而讨论rt线程的优先级值怎么设计的问题去了。  
rt线程虽然能够解决一些实时性问题，但是也让linux从调度这件事，从通用，退化成高度定制了。

