之前讨论的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从调度这件事，从通用，退化成高度定制了。



调度(3)-调度器的设计

如果为所有程序设计的是静态优先级，那么天生的弊端就是低优先级任务饿死。所以在设计调度策略的时候，考虑动态优先级是必不可少的。本文简单说明一下动态优先级
# 如何设计动态优先级
通常一个程序包含两种情况
* CPU密集型
* IO密集型

而这两种情况并不代表着程序一直都是，而是在运行过程中切换的。也就是一个任务一会儿是CPU密集型，一会儿是IO密集型。我们应该在不同情况下为其设置不同的优先级情况。通常来说，对于IO密集型的任务，应该将其优先级设置较高，让其立马能够将任务推向IO去处理，而对于CPU密集型任务，应该将其优先级稍微降低，从而保证IO型的任务不会出现饿死的情况。

这样，我们可以构造一个公式如下

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

因为在100-140优先级范围内，越高代表越优先级越低，此公式的关键点在于bonus值，这个值是等待IO的时间。也就是说，一个任务等待IO时间越长，那么其整体优先级会更高。

# 负载均衡
在多核系统上，为了避免大小脚的问题，也就是某个核心任务过重，而其他核心任务太轻，所以需要进行负载均衡。首先，我们知道现在runqueue是per-CPU的，所以当任务从一个CPU迁移到另一个CPU的时候，那么此任务相当于也是在做动态优先级调整。这种调整的目的是为了CPU的负载更均衡

在Linux上通过PELT计算负载，其思路是在一个任务开始运行的时候，先判断CPU的负载情况，如果当前CPU负载较高，则将其迁移到负载低的那个CPU队列上运行。

PELT的量化负载公式如下

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

实际算力公式：

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

在安卓平台，可能会采用WALT

# 参考
> https://static.linaro.org/connect/sfo17/Presentations/SFO17-307%20WALT%20vs%20PELT.pdf

调度(2)-动态优先级的必要性

早期的Linux调度策略设计的比较简单，逐步的随着linux的越来越火热，调度问题受到了很多人的关注，本文基于历史和一些数据总结一下linux2.4和linux2.6的调度状态。为什么从这两个版本说呢，因为现在linux内核的调度策略的雏形是从2.6开始形成的

# Linux 2.4
在linux 2.4时，内核使用全局队列来管理任务，当任务到来的时候，此队列在content switch的时候会遍历整个runqueue，找到优先级最高的任务来运行。这样的设计有如下几个问题
* O(n)负载度：因为没有考虑设计问题，所以调度器本身的效率低下
* 锁争用：所有CPU都在同一个全局runqueue上争抢锁，这使得锁竞争巨大

# Linux 2.6 
2.6版本的调度器为了设计O(1)的调度器，对齐进行了整体的设计，首先为了解决锁的问题，调度队列是通过per-cpu上维护两个队列（active和expired），0-99作为实时任务，值越高优先级越高，100-140作为普通任务。下面来介绍2.6上调度是如何设计的。

其实翻看我之前rtems的分析就可以提前知道，调度器通过bitmap+拉链来设计O(1)的代码。同样的Linux 2.6就是这么设计的。它有两个关键元素
* bitmask: 以优先级作为bitmask，这样在寻找优先级最高的任务的时候，只是高效的bitmap就能知道哪个优先级内的队列非空
* queue： 每个优先级的bit下对应一个拉链，拉链本身是fifo结构的，当找到最高优先级的非空队列的时候，只需要在队列里面pop最先入队的任务即可
* active和expired： 在per-CPU上设计两个队列轮转，active是需要立即调度的任务队列，expire将要调度的任务队列。当active的任务运行完毕之后，active和expired做一次轮转

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

通过图可以演示这两个队列

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

此时OS从100上选择了一个任务来运行，当运行完成之后，该任务被放置在expired队列上，等待轮转后运行

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

当active runqueues的任务都运行完成了，则active和expired做一次轮转。

## 关于timeslice
调度器的分片是在时钟tick中计算的。默认会分配一个值，每次tick到期，会对当前正在运行的任务的timeslice值自减1。当tick完成的时候，也就是timeslice完成的时候。就是将该任务从active迁移到expired的时机。

# 总结
本文介绍了基本的调度概念，可以强化理解O(1)调度器的历史由来。

# 参考
> https://zhuanlan.zhihu.com/p/33461281









