上文介绍了cfs的enqueue操作,那对应的,就需要dequeue,dequeue就是在rb-tree中删除一个任务
# schedule dequeue
以schedule为例,其流程为
```
schedule
  _schedule
    pick_next_task
      pick_next_task_fair
        set_next_entity
          __dequeue_entity
            rb_erase_cached
```
我们可以看到dequeue的核心函数是`__dequeue_entity`, 根据上述流程可以知道,当任务被选中执行的时候,会选中rb-tree最小的任务后,主动调用`__dequeue_entity`来pop queue
# other dequeue
其他非标准场景例如
* blocking,sleep
* migration
* exit
* hotplug
* resched
* reweight
* cgroups change

这些场景上单独封装了和enqueue_task成对的函数,如下
```
static inline void dequeue_task(struct rq *rq, struct task_struct *p, int flags)
{
	if (!(flags & DEQUEUE_NOCLOCK))
		update_rq_clock(rq);

	if (!(flags & DEQUEUE_SAVE)) {
		sched_info_dequeued(rq, p);
		psi_dequeue(p, flags & DEQUEUE_SLEEP);
	}

	uclamp_rq_dec(rq, p);
	p->sched_class->dequeue_task(rq, p, flags);
}
```
同样的也有成对的deactivative_task
```
void activate_task(struct rq *rq, struct task_struct *p, int flags)
{
	enqueue_task(rq, p, flags);

	p->on_rq = TASK_ON_RQ_QUEUED;
}

void deactivate_task(struct rq *rq, struct task_struct *p, int flags)
{
	p->on_rq = (flags & DEQUEUE_SLEEP) ? 0 : TASK_ON_RQ_MIGRATING;

	dequeue_task(rq, p, flags);
}
```
值得注意的是,deactivate_task和dequeue_task有一些额外的flag判断,简单解析一下
1. p->on_rq = (flags & DEQUEUE_SLEEP) ? 0 : TASK_ON_RQ_MIGRATING;

说明这次deactivate_task大概率是因为睡眠或者迁移导致的dequeue,分别为sleep和migration设置了on_rq标志位

2. DEQUEUE_NOCLOCK

如果设计到睡眠,迁移,那么入队出队需要更新时间,但是如果是直接schedule,那么这个会默认带上,也就意味着没必要重复的更新时间

3. DEQUEUE_SAVE

它和ENQUEUE_RESTORE成对,通过记录enqueue和dequeue的sched_info,然后在dequeue的时候故意不去将sched_info dequeue,这样可以在例如负载均衡的场景上获取sched_info信息统计负载,当然也可以调试.sched_info会更新enqueue和dequeue的时间戳

总结dequeue的大概流程为
```
deactivate_task
  dequeue_task
    dequeue_task_fair
      dequeue_entity 
        __dequeue_entity
          rb_erase_cached
```

值得注意的是,我们在enqueue提到了为了维护公平性需要单独加上当前cpu的min_vruntime,那对应的就要在dequeue上单独减去当前cpu的min_vruntime,这个代码就藏在dequeue_entity中
```
	if (!(flags & DEQUEUE_SLEEP))
		se->vruntime -= cfs_rq->min_vruntime;
```
注意的是,如果不是SLEEP,那假设是MIDRATION,那是通过 update_curr() ->  update_min_vruntime() 更新的,所以这里就不需要再多减一次了.

# 总结
与enqueue成对的,本文介绍了cfs的dequeue,简单理解就是cfs的dequeue就是在rb-tree上删掉成员,所以有两个路径
* 路径1: pick_next_task上,直接删掉节点就行
* 路径2: 其他场景,调用成对的api,dequeue_task,它会更新和维护好vruntime,以及调度时钟信息














调度(9)-CFS调度任务出队

上文介绍了cfs的几个特征点权重/vruntime/调度周期，以及说明了cfs调度的数据结构，这些信息可以宏观上看到调度器的实现方式，本文再基于调度的一个通用概念enqueue进行介绍。

什么是enqueue，简单来说就是任务到来的时候，需要选enqueue给到调度器，由调度器根据策略来选择哪个任务运行，所以enqueue是调度器的数据来源

# 任务创建enqueue
任务创建通过fork调用，如下
```
SYSCALL_DEFINE0(fork)
{
        struct kernel_clone_args args = {
                .exit_signal = SIGCHLD,
        };

        return kernel_clone(&args);
}
```
kernel_clone是一层封装，我们抓kernel_clone的实现
```
pid_t kernel_clone(struct kernel_clone_args *args)
{
        wake_up_new_task(p);
}
```
可以看到，任务fork的时候，会主动触发一次wake_up，其流程如下
```
void wake_up_new_task(struct task_struct *p)
{
        p->state = TASK_RUNNING;
        activate_task(rq, p, ENQUEUE_NOCLOCK);
        check_preempt_curr(rq, p, WF_FORK);
}
```
在activate_task里面入队
```
void activate_task(struct rq *rq, struct task_struct *p, int flags)
{
        if (task_on_rq_migrating(p))
                flags |= ENQUEUE_MIGRATED;

        enqueue_task(rq, p, flags);

        p->on_rq = TASK_ON_RQ_QUEUED;
}
```
enqueue_task实际上是一个hook，调用对应的sched_class的enqueue_task回调
```
static inline void enqueue_task(struct rq *rq, struct task_struct *p, int flags)
{
        if (!(flags & ENQUEUE_NOCLOCK))
                update_rq_clock(rq);

        if (!(flags & ENQUEUE_RESTORE)) {
                sched_info_queued(rq, p);
                psi_enqueue(p, flags & ENQUEUE_WAKEUP);
        }

        uclamp_rq_inc(rq, p);
        trace_android_rvh_enqueue_task(rq, p, flags);
        p->sched_class->enqueue_task(rq, p, flags);
        trace_android_rvh_after_enqueue_task(rq, p);
}
```
cfs的sched_class的结构初始化如下
```
const struct sched_class fair_sched_class
        __section("__fair_sched_class") = {
        .enqueue_task           = enqueue_task_fair,
        .dequeue_task           = dequeue_task_fair,
        .yield_task             = yield_task_fair,
        .yield_to_task          = yield_to_task_fair,

        .check_preempt_curr     = check_preempt_wakeup,

        .pick_next_task         = __pick_next_task_fair,
        .put_prev_task          = put_prev_task_fair,
        .set_next_task          = set_next_task_fair,

#ifdef CONFIG_SMP
        .balance                = balance_fair,
        .select_task_rq         = select_task_rq_fair,
        .migrate_task_rq        = migrate_task_rq_fair,

        .rq_online              = rq_online_fair,
        .rq_offline             = rq_offline_fair,

        .task_dead              = task_dead_fair,
        .set_cpus_allowed       = set_cpus_allowed_common,
#endif

        .task_tick              = task_tick_fair,
        .task_fork              = task_fork_fair,

        .prio_changed           = prio_changed_fair,
        .switched_from          = switched_from_fair,
        .switched_to            = switched_to_fair,

        .get_rr_interval        = get_rr_interval_fair,

        .update_curr            = update_curr_fair,

#ifdef CONFIG_FAIR_GROUP_SCHED
        .task_change_group      = task_change_group_fair,
#endif

#ifdef CONFIG_UCLAMP_TASK
        .uclamp_enabled         = 1,
#endif
};
```
所以入队其实就是 enqueue_task_fair，抓重点，我们找enqueue做了什么
```
static void
enqueue_task_fair(struct rq *rq, struct task_struct *p, int flags)
{
        for_each_sched_entity(se) {
                if (se->on_rq)
                        break;
                cfs_rq = cfs_rq_of(se);
                enqueue_entity(cfs_rq, se, flags);

                cfs_rq->h_nr_running++;
                cfs_rq->idle_h_nr_running += idle_h_nr_running;

                flags = ENQUEUE_WAKEUP;
        }
}
```
for_each_sched_entity是遍历了task_struct的shed_entity，这里相当于遍历了cfs的每一层se   

真正的enqueue的操作是将sched_entity加入到rb-tree上，所以我们查看enqueue_entity，而enqueue_entity会维护cfs的信息一致性，大概如下
```
static void
enqueue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int flags)
{
        update_curr(cfs_rq);
        update_load_avg(cfs_rq, se, UPDATE_TG | DO_ATTACH);
        se_update_runnable(se);
        update_cfs_group(se);
        account_entity_enqueue(cfs_rq, se);
        if (flags & ENQUEUE_WAKEUP)
                place_entity(cfs_rq, se, 0);
        /* Entity has migrated, no longer consider this task hot */
        if (flags & ENQUEUE_MIGRATED)
                se->exec_start = 0;
        check_schedstat_required();
        update_stats_enqueue(cfs_rq, se, flags);
        check_spread(cfs_rq, se);
        if (!curr)
                __enqueue_entity(cfs_rq, se);
        se->on_rq = 1;
}
```
可以看到，enqueue_entity做了很多cfs上的状态更新，如update_load_avg更新pelt的load，se_update_runnable更新se->runnable_weight等等

最后执行enqueue的操作是`__enqueue_entity`
```
static void __enqueue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se)
{
        struct rb_node **link = &cfs_rq->tasks_timeline.rb_root.rb_node;
        struct rb_node *parent = NULL;
        struct sched_entity *entry;
        bool leftmost = true;

        trace_android_rvh_enqueue_entity(cfs_rq, se);
        /*
         * Find the right place in the rbtree:
         */
        while (*link) {
                parent = *link;
                entry = rb_entry(parent, struct sched_entity, run_node);
                /*
                 * We dont care about collisions. Nodes with
                 * the same key stay together.
                 */
                if (entity_before(se, entry)) {
                        link = &parent->rb_left;
                } else {
                        link = &parent->rb_right;
                        leftmost = false;
                }
        }

        rb_link_node(&se->run_node, parent, link);
        rb_insert_color_cached(&se->run_node,
                               &cfs_rq->tasks_timeline, leftmost);
}
```
这里将一个调度实体按照其 vruntime 的大小，插入到 CFS 运行队列的红黑树中，一共两步，插入和染色。关于rb-tree的可以查看文章《rb-tree实现》
# 任务唤醒enqueue
上面已经把基本流程过了，任务唤醒场景的代码调用链为
```
try_to_wake_up
  ttwu_queue
    ttwu_do_activate
      activate_task
```
# 任务迁移enqueue
```
migrate_tasks
  __migrate_task
    move_queued_task
      activate_task
```
# 维护公平
上面介绍了CFS调度enqueue的几个大的场景，现在我们看代码的一个经典注释
```
/*
 * MIGRATION
 *
 *      dequeue
 *        update_curr()
 *          update_min_vruntime()
 *        vruntime -= min_vruntime
 *
 *      enqueue
 *        update_curr()
 *          update_min_vruntime()
 *        vruntime += min_vruntime
 *
 * this way the vruntime transition between RQs is done when both
 * min_vruntime are up-to-date.
 *
 * WAKEUP (remote)
 *
 *      ->migrate_task_rq_fair() (p->state == TASK_WAKING)
 *        vruntime -= min_vruntime
 *
 *      enqueue
 *        update_curr()
 *          update_min_vruntime()
 *        vruntime += min_vruntime
 *
 * this way we don't have the most up-to-date min_vruntime on the originating
 * CPU and an up-to-date min_vruntime on the destination CPU.
 */
```
根据上面的注释，我们看到，其在migration/wakeup两个场景上的入队和出队操作都自行将vruntime先减去min_vruntime后又加上min_vruntime了。  
这个min_vruntime是per-cpu上遍历整个runqueue中最小的vruntime的记录值，也就是说，这个min_vruntime在每个CPU上的值并不一样，所以它有两个作用
* 为新创建的进程提供最小vruntime
* 当任务迁移和唤醒时，切换cpu的时候进行公平性维护

关于上述的1，这个比较清晰明了，在讨论步幅调度的时候就提到了如果新任务的步幅是0，那么其他任务很容易饿死，所以新的任务需要带一个很小的步幅，同样对于cfs也是，这个值是min_vruntime，它记录了runqueue中最小的vruntime

而上述的2，它是怎么维护公平性的呢？ 实际上正是因为runqueue是per-cpu的，所以每个cpu上的min_vruntime是不一样的，举个例子，假设CPU0和CPU1，CPU0的min_vruntime是10，而CPU1的min_vruntime是100，当任务迁移和唤醒的时候，假设一个任务创建在CPU0，那他的min_vruntime和vruntime是10，此时被唤醒或迁移到了CPU1上，如果我们此时还是拿vruntime为10去enqueue，那么这对CPU1上runqueue的任务并不公平，因为此时这个任务vruntime最小，它因为被迁移导致优先级最高。

反之，如果CPU1的任务被迁移到CPU0上，那么被迁移的任务因为vruntime偏大的问题导致其优先级过低

所以上述又出现了局部不公平性，而为了解决这种局部不公平性的原则，做法是
* 当dequeue/migration 出队时减去源 min_vruntime，在 enqueue 时加上目标 min_vruntime，从而防止迁移或唤醒的任务因为不同 CPU 时间推进速度不同而获得不公平的调度优势。也就是跨CPU的公平性维护

# 总结
本文介绍了cfs的enqueue的流程，可以知道在linux中，任务从创建开始，其是在什么时机进行入队到rb-tree的，大家可以清晰的了解到调度器入队的过程，从而理解调度器本身的运作机制。











调度(8)-CFS调度任务入队

上文聊到了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



