static u64 __calc_delta(u64 delta_exec, unsigned long weight, struct load_weight *lw)
{
    u64 fact = scale_load_down(weight);
    int shift = 32;
 
    __update_inv_weight(lw);
 
    if (unlikely(fact >> 32)) {
        while (fact >> 32) {
            fact >>= 1;
            shift--;
        }
    }
 
    fact = (u64)(u32)fact * lw->inv_weight;
 
    while (fact >> 32) {
        fact >>= 1;
        shift--;
    }
 
    return mul_u64_u32_shr(delta_exec, fact, shift);
} 

按照上面说的理论，calc_delta_fair()函数调用__calc_delta()的时候传递的weight参数是NICE_0_LOAD，lw参数是进程对应的struct load_weight结构体。

static inline u64 calc_delta_fair(u64 delta, struct sched_entity *se)
{
    if (unlikely(se->load.weight != NICE_0_LOAD))             /* 1 */
        delta = __calc_delta(delta, NICE_0_LOAD, &se->load);  /* 2 */
 
    return delta;
} 

1. 按照之前的理论，nice值为0（权重是NICE_0_LOAD）的进程的虚拟时间和实际时间是相等的。因此如果进程的权重是NICE_0_LOAD，进程对应的虚拟时间就不用计算。
2. 调用__calc_delta()函数。

Linux通过struct task_struct结构体描述每一个进程。但是调度类管理和调度的单位是调度实体，并不是task_struct。在支持组调度的时候，一个组也会抽象成一个调度实体，它并不是一个task。所以，我们在struct task_struct结构体中可以找到以下不同调度类的调度实体。

struct task_struct {
         struct sched_entity        se;
    struct sched_rt_entity      rt;
    struct sched_dl_entity      dl;
    /* ... */
} 

se、rt、dl分别对应CFS调度器、RT调度器、Deadline调度器的调度实体。

struct sched_entity结构体描述调度实体，包括struct load_weight用来记录权重信息。除此以外我们一直关心的时间信息，肯定也要一起记录。struct sched_entity结构体简化后如下：

struct sched_entity {
    struct load_weight      load;
    struct rb_node      run_node;
    unsigned int        on_rq;
    u64         sum_exec_runtime;
    u64         vruntime;
}; 

1. load：权重信息，在计算虚拟时间的时候会用到inv_weight成员。
2. run_node：CFS调度器的每个就绪队列维护了一颗红黑树，上面挂满了就绪等待执行的task，run_node就是挂载点。
3. on_rq：调度实体se加入就绪队列后，on_rq置1。从就绪队列删除后，on_rq置0。
4. sum_exec_runtime：调度实体已经运行实际时间总合。
5. vruntime：调度实体已经运行的虚拟时间总合。

就绪队列（runqueue）

系统中每个CPU都会有一个全局的就绪队列（cpu runqueue），使用struct rq结构体描述，它是per-cpu类型，即每个cpu上都会有一个struct rq结构体。每一个调度类也有属于自己管理的就绪队列。例如，struct cfs_rq是CFS调度类的就绪队列，管理就绪态的struct sched_entity调度实体，后续通过pick_next_task接口从就绪队列中选择最适合运行的调度实体（虚拟时间最小的调度实体）。struct rt_rq是实时调度器就绪队列。struct dl_rq是Deadline调度器就绪队列。

struct rq {
         struct cfs_rq cfs;
    struct rt_rq rt;
    struct dl_rq dl;
};
 
struct rb_root_cached {
    struct rb_root rb_root;
    struct rb_node *rb_leftmost;
};
 
struct cfs_rq {
    struct load_weight load;
    unsigned int nr_running;
    u64 min_vruntime;
    struct rb_root_cached tasks_timeline;
}; 

1. load：就绪队列权重，就绪队列管理的所有调度实体权重之和。
2. nr_running：就绪队列上调度实体的个数。
3. min_vruntime：跟踪就绪队列上所有调度实体的最小虚拟时间。
4. tasks_timeline：用于跟踪调度实体按虚拟时间大小排序的红黑树的信息（包含红黑树的根以及红黑树中最左边节点）。

CFS维护了一个按照虚拟时间排序的红黑树，所有可运行的调度实体按照p->se.vruntime排序插入红黑树。如下图所示。

CFS选择红黑树最左边的进程运行。随着系统时间的推移，原来左边运行过的进程慢慢的会移动到红黑树的右边，原来右边的进程也会最终跑到最左边。因此红黑树中的每个进程都有机会运行。

现在我们总结一下。Linux中所有的进程使用task_struct描述。task_struct包含很多进程相关的信息（例如，优先级、进程状态以及调度实体等）。但是，每一个调度类并不是直接管理task_struct，而是引入调度实体的概念。CFS调度器使用sched_entity跟踪调度信息。CFS调度器使用cfs_rq跟踪就绪队列信息以及管理就绪态调度实体，并维护一棵按照虚拟时间排序的红黑树。tasks_timeline->rb_root是红黑树的根，tasks_timeline->rb_leftmost指向红黑树中最左边的调度实体，即虚拟时间最小的调度实体（为了更快的选择最适合运行的调度实体，因此rb_leftmost相当于一个缓存）。每个就绪态的调度实体sched_entity包含插入红黑树中使用的节点rb_node，同时vruntime成员记录已经运行的虚拟时间。我们将这几个数据结构简单梳理，如下图所示。