Linux 内核之旅（六）：进程调度（CFS）

struct sched_class {
	const struct sched_class *next;

	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, bool preempt);

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

	struct task_struct * (*pick_next_task) (struct rq *rq,
						struct task_struct *prev,
						struct rq_flags *rf);
	void (*put_prev_task) (struct rq *rq, struct task_struct *p);

	void (*set_curr_task) (struct rq *rq);
	void (*task_tick) (struct rq *rq, struct task_struct *p, int queued);
};

// include/linux/sched.h
struct task_struct {
	// ...
	int				prio;
	int				static_prio;
	int				normal_prio;

	const struct sched_class	*sched_class;
	struct sched_entity		se;

	unsigned int			policy;
	int				nr_cpus_allowed;
	cpumask_t			cpus_allowed;  
}

// kernel/sched/sched.h
struct rq {
	unsigned int nr_running;

	#define CPU_LOAD_IDX_MAX 5
	unsigned long cpu_load[CPU_LOAD_IDX_MAX];

	struct load_weight load;

	struct cfs_rq cfs;

	struct task_struct *curr, *idle, *stop;
	u64 clock;
};

struct cfs_rq {
	//就绪队列上所有进程的累积负载值
	struct load_weight load;
	
	//就绪队列上的进程数量
	unsigned int nr_running;

	//记录就绪队列上进程的最小虚拟运行时间。这个值是计算就绪队列虚拟运行时间的基础，大部分情况下是CFS红黑树最小子节点（最左节点）的虚拟运行时间，但实际情况下可能有时候会比最小子节点的虚拟运行时间稍大一些
	u64 min_vruntime;

	//v4.11.6 中红黑树根节点用 struct rb_root，最左节点单独用 rb_leftmost 指针缓存
	//（注：4.15+ 合并为 struct rb_root_cached tasks_timeline，内部自带 leftmost 缓存）
	struct rb_root tasks_timeline;
	struct rb_node *rb_leftmost;
};

// include/linux/sched.h（v4.11.6，注意此版本 sched_entity 尚无 runnable_weight 字段，该字段为 4.15+ PELT 重写引入）
struct sched_entity {
	// 权重信息，在计算虚拟时间的时候会用到inv_weight成员
	struct load_weight		load;
	// CFS调度器使用红黑树维护调度的进程信息
	struct rb_node			run_node;
	// 进入就绪队列是为1
	unsigned int			on_rq;

	u64				exec_start;
	// 调度实体已经运行实际时间总合
	u64				sum_exec_runtime;
	// 调度实体已经运行的虚拟时间总合
	u64				vruntime;
	u64				prev_sum_exec_runtime;
};

//调度周期是一个动态变化的值，使用__sched_period计算调度周期
//nr_running是系统中就绪进程数量，当超过sched_nr_latency时，无法在一个调度延迟内轮转完所有进程，因此转为保证调度最小粒度。如果nr_running并没有超过sched_nr_latency，那么调度周期就等于调度延迟sysctl_sched_latency（6ms）
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;
}

//数组的值可以看作是公式：weight = 1024 / 1.25nice计算得到。公式中的1.25取值依据是：进程每降低一个nice值，将多获得10% cpu的时间。公式中以1024权重为基准值计算得来，1024权重对应nice值为0，其权重被称为NICE_0_LOAD。默认情况下，大部分进程的权重基本都是NICE_0_LOAD
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,
}; 

/*
 * 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,
};

struct load_weight {
	unsigned long		weight;		//进程的权重
	u32			inv_weight;			//inv_weight等于2^32/weight
};

//将实际时间转换成虚拟时间
//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)
{
	/*
	nice值为0（权重是NICE_0_LOAD）的进程的虚拟时间和实际时间是相等的。因此如果进程的权重是NICE_0_LOAD，进程对应的虚拟时间就不用计算
	*/
	if (unlikely(se->load.weight != NICE_0_LOAD))
		delta = __calc_delta(delta, NICE_0_LOAD, &se->load);	//

	return delta;
}

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);
} 

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

/* kernel/sched/sched.h */

struct cfs_rq {
    u64         min_vruntime;
    /* ... */
};

static u64 sched_slice(struct cfs_rq *cfs_rq, struct sched_entity *se)
{
	//__sched_period函数是计算调度周期的函数，此函数当进程个数小于8时，调度周期等于调度延迟等于6ms。否则调度周期等于进程的个数乘以0.75ms，表示一个进程最少可以运行0.75ms，防止进程过快发生上下文切换
	u64 slice = __sched_period(cfs_rq->nr_running + !se->on_rq);

	//遍历当前的调度实体，如果调度实体没有调度组的关系，则只运行一次
	//获取当前CFS运行队列cfs_rq，获取运行队列的权重cfs_rq->rq代表的是这个运行队列的权重。最后通过__calc_delta计算出此进程的实际运行时间
	for_each_sched_entity(se) {
		struct load_weight *load;
		struct load_weight lw;

		cfs_rq = cfs_rq_of(se);
		load = &cfs_rq->load;

		if (unlikely(!se->on_rq)) {
			lw = cfs_rq->load;

			update_load_add(&lw, se->load.weight);
			load = &lw;
		}

		//__calc_delta函数：不仅仅可以计算一个进程的虚拟时间，它在这里是计算一个进程在总的调度周期中可以获取的运行时间，公式为：进程的运行时间 = （调度周期时间 * 进程的weight） / CFS运行队列的总weigth
		slice = __calc_delta(slice, se->load.weight, load);
	}
	return slice;
}

static void
place_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int initial)
{
	//获取当前CFS运行队列的min_vruntime的值
	u64 vruntime = cfs_rq->min_vruntime;

	/*
	 * The 'current' period is already promised to the current tasks,
	 * however the extra weight of the new task will slow them down a
	 * little, place the new task so that it fits in the slot that
	 * stays open at the end.
	 */
	if (initial && sched_feat(START_DEBIT))
		// 新创建的进程惩罚的时间如何计算？参考sched_vslice的实现，参考下文
		vruntime += sched_vslice(cfs_rq, se);

	/* sleeps up to a single latency don't count. */
	if (!initial) {
		unsigned long thresh = sysctl_sched_latency;

		/*
		 * Halve their sleep time's effect, to allow
		 * for a gentler effect of sleepers:
		 */
		if (sched_feat(GENTLE_FAIR_SLEEPERS))
			thresh >>= 1;

		vruntime -= thresh;
	}

	/* ensure we never gain time by being placed backwards. */
	//通过`max_vruntime`获取最大的`vruntime`
	se->vruntime = max_vruntime(se->vruntime, vruntime);
}

static void update_curr(struct cfs_rq *cfs_rq)
{
	struct sched_entity *curr = cfs_rq->curr;
	u64 now = rq_clock_task(rq_of(cfs_rq));
	u64 delta_exec;

	if (unlikely(!curr))
		return;

	//计算出当前CFS运行队列的进程，距离上次更新虚拟时间的差值
	delta_exec = now - curr->exec_start;
	if (unlikely((s64)delta_exec <= 0))
		return;

	//更新exec_start的值
	curr->exec_start = now;

	schedstat_set(curr->statistics.exec_max,
		      max(delta_exec, curr->statistics.exec_max));

	//更新当前进程总共执行的时间
	curr->sum_exec_runtime += delta_exec;
	schedstat_add(cfs_rq->exec_clock, delta_exec);

	//通过calc_delta_fair计算当前进程虚拟时间
	curr->vruntime += calc_delta_fair(delta_exec, curr);
	//通过update_min_vruntime函数来更新CFS运行队列中最小的vruntime的值
	update_min_vruntime(cfs_rq);


	account_cfs_rq_runtime(cfs_rq, delta_exec);
}

long _do_fork(unsigned long clone_flags,unsigned long stack_start,unsigned long stack_size,int __user *parent_tidptr,int __user *child_tidptr,unsigned long tls){
    struct task_struct *p;
    int trace = 0;
    long nr;
    //......
    // 复制结构
    p = copy_process(clone_flags, stack_start, stack_size,child_tidptr, NULL, trace, tls, NUMA_NO_NODE);
    //......
    if (!IS_ERR(p)) {
        struct pid *pid;
        pid = get_task_pid(p, PIDTYPE_PID);
        nr = pid_vnr(pid);
        if (clone_flags & CLONE_PARENT_SETTID)
            put_user(nr, parent_tidptr);
        //......
        // 唤醒新进程
        wake_up_new_task(p);
        //......
        put_pid(pid);
    }
    //...
} 

static struct task_struct *copy_process(...){
    // 复制进程task_struct结构体
    struct task_struct *p;
    p = dup_task_struct(current, ...);
    // 复制files_struct
    retval = copy_files(clone_flags,p)
    // 复制fs_struct
    retval = copy_fs(clone_flags,p)
    // 复制mm_struct
    retval = copy_mm(clone_flags,p)
    // 复制进程的命名空间 nsproxy
    retval = copy_namespace(clone_flags,p)
    // 申请pid并设置进程号
    pid = alloc_pid(p->nsproxy->pid_ns_for_children,...);
    p->pid = pid_nr(pid);
    if (clone_flags & CLONE_THREAD) {
        p->tgid = current->tgid;
    }else{
        p->tgid = p->pid;
    }
    //...
}

static struct task_struct *copy_process(...){
    //...
    retval = sched_fork(clone_flags, p);
	//...
}

int sched_fork(unsigned long clone_flags, struct task_struct *p){
    __sched_fork(clone_flags, p);
    p->state = TASK_NEW;
    if (rt_prio(p->prio))
        p->sched_class = &rt_sched_class;
    else
        p->sched_class = &fair_sched_class; // fair_sched_class （CFS的调度类）是一个全局对象，为CFS调度算法的实现
}

static void __sched_fork(struct task_struct *p){
    p ->on_rq = 0;
    //...
    p->se.nr_migrations = 0;
    p->se.vruntime = 0; // 注意：新进程是0对老进程不公平，在新进程真正被加入运行队列时，会将其值设置为cfs_rq->min_vruntime
}

void wake_up_new_task(struct task_struct *p){
    // 为进程选择一个合适的cpu
    cpu = select_task_rq(p, task_cpu(p)
    // 为进程指定运行队列
    __set_task_cpu(p,cpu, WF_FORK));
    // 将进程添加到运行队列红黑树
    rq = __task_rq_lock(p);
    activate_task(rq, p, 0);
}

const struct sched_class fair_sched_class = {
	.next				= &idle_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_curr_task      = set_curr_task_fair,
	.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,
};

static void task_fork_fair(struct task_struct *p)
{
	struct cfs_rq *cfs_rq;
	struct sched_entity *se = &p->se, *curr;
	struct rq *rq = this_rq();
	struct rq_flags rf;
 
	rq_lock(rq, &rf);
	update_rq_clock(rq);
 
	cfs_rq = task_cfs_rq(current);
	//cfs_rq是CFS调度器就绪队列，curr指向当前正在cpu上运行的task的调度实体
	curr = cfs_rq->curr;                 
	if (curr) {
		//update_curr()函数是比较重要，主要是更新当前正在运行的调度实体的运行时间信息
		update_curr(cfs_rq);                 
		//初始化当前创建的新进程的虚拟时间
		se->vruntime = curr->vruntime;       
	}

	//place_entity()函数在进程创建以及唤醒的时候都会调用，创建进程的时候传递参数initial=1。主要目的是更新调度实体得到虚拟时间（se->vruntime成员）。要和cfs_rq->min_vruntime的值保持差别不大
	place_entity(cfs_rq, se, 1);             
 
	/*
	这里为什么要减去cfs_rq->min_vruntime呢？因为现在计算进程的vruntime是基于当前cpu上的cfs_rq，并且现在还没有加入当前cfs_rq的就绪队列上。等到当前进程创建完毕开始唤醒的时候，加入的就绪队列就不一定是现在计算基于的cpu。所以，在加入就绪队列的函数中会根据情况加上当前就绪队列cfs_rq->min_vruntime。为什么要先减后加处理呢？假设cpu0上的cfs就绪队列的最小虚拟时间min_vruntime的值是1000000，此时创建进程的时候赋予当前进程虚拟时间是1000500。但是，唤醒此进程加入的就绪队列却是cpu1上CFS就绪队列，cpu1上的cfs就绪队列的最小虚拟时间min_vruntime的值如果是9000000。如果不采用先减后加方法，那么该进程在cpu1上运行肯定是乐坏了，疯狂的运行。现在的处理计算得到的调度实体的虚拟时间是1000500 - 1000000 + 9000000 = 9000500，因此事情就不是那么的糟糕
	*/

	// 另外这里减去的min_vruntime会在enqueue_entity入红黑树的时候加回
	se->vruntime -= cfs_rq->min_vruntime;   
	rq_unlock(rq, &rf);
}

static void update_curr(struct cfs_rq *cfs_rq)
{
	struct sched_entity *curr = cfs_rq->curr;
	u64 now = rq_clock_task(rq_of(cfs_rq));
	u64 delta_exec;
 
	if (unlikely(!curr))
		return;
 
	//计算本次更新虚拟时间距离上次更新虚拟时间的差
	delta_exec = now - curr->exec_start;                    
	if (unlikely((s64)delta_exec <= 0))
		return;
 
	curr->exec_start = now;
	curr->sum_exec_runtime += delta_exec;
	//更新当前调度实体虚拟时间，calc_delta_fair()函数根据上面说的虚拟时间的计算公式计算虚拟时间（也就是调用__calc_delta()函数）
	curr->vruntime += calc_delta_fair(delta_exec, curr);    
	// 更新CFS就绪队列的最小虚拟时间min_vruntime。min_vruntime也是不断更新的，主要就是跟踪就绪队列中所有调度实体的最小虚拟时间。如果min_vruntime一直不更新的话，由于min_vruntime太小，导致后面创建的新进程若根据这个值来初始化新进程的虚拟时间，那么就会扰乱调度新老进程的优先级
	update_min_vruntime(cfs_rq);                            
}

static void update_min_vruntime(struct cfs_rq *cfs_rq)
{
	struct sched_entity *curr = cfs_rq->curr;
	u64 vruntime = cfs_rq->min_vruntime;
 
	if (curr) {
		if (curr->on_rq)
			vruntime = curr->vruntime;
		else
			curr = NULL;
	}
 
	//v4.11.6 直接使用 cfs_rq->rb_leftmost 缓存的最左节点（而非 4.15+ 的 rb_first_cached）
	if (cfs_rq->rb_leftmost) { /* non-empty tree */
		struct sched_entity *se;
		se = rb_entry(cfs_rq->rb_leftmost, struct sched_entity, run_node);
 
		if (!curr)
			vruntime = se->vruntime;
		else
			vruntime = min_vruntime(vruntime, se->vruntime);
	}
 
	/* ensure we never gain time by being placed backwards. */
	cfs_rq->min_vruntime = max_vruntime(cfs_rq->min_vruntime, vruntime);
}

static void
place_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int initial)
{
	u64 vruntime = cfs_rq->min_vruntime;
 
	/*
	 * The 'current' period is already promised to the current tasks,
	 * however the extra weight of the new task will slow them down a
	 * little, place the new task so that it fits in the slot that
	 * stays open at the end.
	 */
	//如果是创建进程调用该函数的话，参数initial参数是1
	//因此这里是处理创建的进程，针对刚创建的进程会进行一定的惩罚，将虚拟时间加上一个值就是惩罚，毕竟虚拟时间越小越容易被调度执行
	//惩罚的时间由sched_vslice()计算
	if (initial && sched_feat(START_DEBIT))
		vruntime += sched_vslice(cfs_rq, se);              
 
	/* sleeps up to a single latency don't count. */
	if (!initial) {
		unsigned long thresh = sysctl_sched_latency;
 
		/*
		 * Halve their sleep time's effect, to allow
		 * for a gentler effect of sleepers:
		 */
		if (sched_feat(GENTLE_FAIR_SLEEPERS))
			thresh >>= 1;
		
		//这里主要是针对唤醒的进程，针对睡眠很久的的进程，总是期望它很快得到调度执行，毕竟睡了那么久
		//所以这里减去一定的虚拟时间作为补偿
		vruntime -= thresh;                                 
	}
 
	/* ensure we never gain time by being placed backwards. */
	//保证调度实体的虚拟时间不能倒退
	//原因？设想一下如果一个进程刚睡眠1ms，然后醒来后却要奖励3ms（虚拟时间减去3ms），然后竟然赚了2ms。作为调度器，睡眠100ms，奖励3ms，那就是没问题的
	se->vruntime = max_vruntime(se->vruntime, vruntime);    
}

static u64 sched_vslice(struct cfs_rq *cfs_rq, struct sched_entity *se)
{
	return calc_delta_fair(sched_slice(cfs_rq, se), se);
}

static u64 sched_slice(struct cfs_rq *cfs_rq, struct sched_entity *se)
{
	//__sched_period()：根据就绪队列调度实体个数计算调度周期
	u64 slice = __sched_period(cfs_rq->nr_running + !se->on_rq);   
 
	for_each_sched_entity(se) {                                    
		struct load_weight *load;
		struct load_weight lw;
 
		cfs_rq = cfs_rq_of(se);
		// 获取就绪队列的权重，也就是就绪队列上所有调度实体权重之和
		load = &cfs_rq->load;                                   
 
		if (unlikely(!se->on_rq)) {
			lw = cfs_rq->load;
 
			update_load_add(&lw, se->load.weight);
			load = &lw;
		}
		//__calc_delta()函数包含如下两个功能：
		//1：计算进程运行时间转换成虚拟时间
		//2：计算调度实体se的权重占整个就绪队列权重的比例，然后乘以调度周期时间即可得到当前调度实体应该运行的时间（参数weught传递调度实体se权重，参数lw传递就绪队列权重cfs_rq->load）。例如，就绪队列权重是3072，当前调度实体se权重是1024，调度周期是6ms，那么调度实体应该得到的时间是6*1024/3072=2ms
		slice = __calc_delta(slice, se->load.weight, load);      
	}
	return slice;
}

do_fork()-->_do_fork()-->wake_up_new_task()-->activate_task()-->enqueue_task()-->enqueue_task_fair()
                                   |
                                   +------------>check_preempt_curr()--->check_preempt_wakeup() 

void wake_up_new_task(struct task_struct *p)
{
	struct rq_flags rf;
	struct rq *rq;
	//....
 
	p->state = TASK_RUNNING;
#ifdef CONFIG_SMP
	p->recent_used_cpu = task_cpu(p);
	//通过调用select_task_rq()函数重新选择cpu，通过调用调度类中select_task_rq方法选择调度类中最空闲的cpu
	__set_task_cpu(p, select_task_rq(p, task_cpu(p), SD_BALANCE_FORK, 0));   
#endif
	rq = __task_rq_lock(p, &rf);

	//将进程加入（runqueue）就绪队列，通过调用调度类中enqueue_task方法
	activate_task(rq, p, ENQUEUE_NOCLOCK);                                  
	p->on_rq = TASK_ON_RQ_QUEUED;
	//既然新进程已经准备就绪，那么此时需要检查新进程是否满足抢占当前正在运行进程的条件，如果满足抢占条件需要设置TIF_NEED_RESCHED标志位
	check_preempt_curr(rq, p, WF_FORK);                                      
}

void activate_task(struct rq *rq, struct task_struct *p, int flags)
{
	if (task_contributes_to_load(p))
		rq->nr_uninterruptible--;

	enqueue_task(rq, p, flags);
}

static inline void enqueue_task(struct rq *rq, struct task_struct *p, int flags)
{
	update_rq_clock(rq);
	if (!(flags & ENQUEUE_RESTORE))
		sched_info_queued(rq, p);
	//CFS调度类对应的enqueue_task方法函数是enqueue_task_fair()
	p->sched_class->enqueue_task(rq, p, flags);
}

static void
enqueue_task_fair(struct rq *rq, struct task_struct *p, int flags)
{
	struct cfs_rq *cfs_rq;
	struct sched_entity *se = &p->se;
 
	for_each_sched_entity(se) {            
		//on_rq成员代表调度实体是否已经在就绪队列中
		//值为1代表在就绪队列中，当然就无需继续添加就绪队列了          
		if (se->on_rq)                      
			break;
		cfs_rq = cfs_rq_of(se);
		//enqueue_entity：将调度实体加入就绪队列，入队（enqueue）操作
		enqueue_entity(cfs_rq, se, flags);            
	}
 
	if (!se)
		add_nr_running(rq, 1);
 
	hrtick_update(rq);
}

static void enqueue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int flags)
{
	bool renorm = !(flags & ENQUEUE_WAKEUP) || (flags & ENQUEUE_MIGRATED);
	bool curr = cfs_rq->curr == se;
 
	/*
	 * If we're the current task, we must renormalise before calling
	 * update_curr().
	 */
	if (renorm && curr)
		/*
	如果传入的调度实体是当前进程，并且当前进程不是被唤醒或者迁移CPU，那么当前进程的虚拟运行时间就需要加上队列当前的最小虚拟运行时间。虚拟运行时间增加，意味着在红黑树中往右边移动，下一次会更晚的被调度到
		这一步需要在下面调用update_curr函数之前进行。
		*/
		se->vruntime += cfs_rq->min_vruntime;
 
	//update_curr 顺便更新当前运行调度实体的虚拟时间信息
	update_curr(cfs_rq);                        
 
	if (renorm && !curr)
		//还记得之前在task_fork_fair()函数最后减去的min_vruntime吗？入就绪队列时再加回来
		se->vruntime += cfs_rq->min_vruntime;   
 
	//更新就绪队列相关信息，例如就绪队列的权重
	account_entity_enqueue(cfs_rq, se);         
 
	if (flags & ENQUEUE_WAKEUP)
		//针对唤醒的进程（flag有ENQUEUE_WAKEUP标识），是需要根据情况给予一定的补偿
		//见place_entity()函数分析
		//当然这里针对新进程第一次加入就绪队列是不需要调用的
		place_entity(cfs_rq, se, 0);            
 
	if (!curr)
		//__enqueue_entity()是将se加入就绪队列维护的红黑树中，所有的se以vruntime为key
		__enqueue_entity(cfs_rq, se);           
	//所有的操作完毕也意味着se已经加入cfs就绪队列，置位on_rq成员
	se->on_rq = 1;                              
}

static void __enqueue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se)
{
	//红黑树根节点
	struct rb_node **link = &cfs_rq->tasks_timeline.rb_node;
	struct rb_node *parent = NULL;
	struct sched_entity *entry;
	int leftmost = 1;

	/*
	 * Find the right place in the rbtree:
	 */
	   /*
     * 从红黑树中找到se所应该在的位置
     * 同时leftmost标识其位置是不是最左结点
     * 如果在查找结点的过程中向右走了, 则置leftmost为0
     * 否则说明一直再相左走, 最终将走到最左节点, 此时leftmost始终为1
     */
	while (*link) {
		parent = *link;
		// 利用container_of找到节点实例的首地址
		entry = rb_entry(parent, struct sched_entity, run_node);
		/*
		 * We dont care about collisions. Nodes with
		 * the same key stay together.
		 * 以se->vruntime值为键值进行红黑树结点的比较
		 */
		if (entity_before(se, entry)) {
			// 注意：vruntime可能会溢出，但不影响计算结果，见上文分析
			link = &parent->rb_left;
		} else {
			link = &parent->rb_right;
			leftmost = 0;
		}
	}

	/*
	 * Maintain a cache of leftmost tree entries (it is frequently
	 * used):
	 * 如果leftmost为1, 说明se是红黑树当前的最左结点, 即vruntime最小
     * 那么把这个节点保存在cfs就绪队列的rb_leftmost域中
	 */
	if (leftmost)
		cfs_rq->rb_leftmost = &se->run_node;

	//在红黑树中插入节点，即将node节点插入到parent节点的左树或者右树
	rb_link_node(&se->run_node, parent, link);
	//设置节点的颜色（触发rbtree平衡）
	rb_insert_color(&se->run_node, &cfs_rq->tasks_timeline);
}

void rb_insert_color(struct rb_node *node, struct rb_root *root)
{
	__rb_insert(node, root, dummy_rotate);
}

static void account_entity_enqueue(struct cfs_rq *cfs_rq, struct sched_entity *se)
{
	//更新就绪队列权重，就是将se权重加在就绪队列权重上面
	update_load_add(&cfs_rq->load, se->load.weight);  
	if (!parent_entity(se))
		//cpu就绪队列struct rq同样也需要更新权重信息
		update_load_add(&rq_of(cfs_rq)->load, se->load.weight);   
#ifdef CONFIG_SMP
	if (entity_is_task(se)) {
		struct rq *rq = rq_of(cfs_rq);
 
		account_numa_enqueue(rq, task_of(se));
		//将调度实体se加入链表
		list_add(&se->group_node, &rq->cfs_tasks);                 
	}
#endif
	//就绪队列中所有调度实体的个数+1
	cfs_rq->nr_running++;                                          
}

void scheduler_tick(void)
{
	int cpu = smp_processor_id();
	struct rq *rq = cpu_rq(cpu);
	struct task_struct *curr = rq->curr;

	sched_clock_tick();

	raw_spin_lock(&rq->lock);
	update_rq_clock(rq);
	//调用调度类对应的task_tick方法，针对CFS调度类该函数是task_tick_fair
	curr->sched_class->task_tick(rq, curr, 0);
	cpu_load_update_active(rq);
	calc_global_load_tick(rq);
	raw_spin_unlock(&rq->lock);

	perf_event_task_tick();

#ifdef CONFIG_SMP
	rq->idle_balance = idle_cpu(cpu);
	trigger_load_balance(rq);	//触发负载均衡
#endif
	rq_last_tick_reset(rq);
}

static void task_tick_fair(struct rq *rq, struct task_struct *curr, int queued)
{
	struct cfs_rq *cfs_rq;
	struct sched_entity *se = &curr->se;
	//for循环是针对组调度，组调度未打开的情况下，这里就是一层循环
	for_each_sched_entity(se) {
		cfs_rq = cfs_rq_of(se);
		entity_tick(cfs_rq, se, queued);
	}
}

static void entity_tick(struct cfs_rq *cfs_rq, struct sched_entity *curr, int queued)
{
	/*
	 * Update run-time statistics of the 'current'.
	 */
	//调用update_curr()更新当前运行的调度实体的虚拟时间等信息
	update_curr(cfs_rq);                    
 
	if (cfs_rq->nr_running > 1)
		//如果就绪队列就绪态的调度实体个数大于1需要检查是否满足抢占条件，如果可以抢占就设置TIF_NEED_RESCHED flag
		check_preempt_tick(cfs_rq, curr);     
}

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;
 
	//计算curr进程在本次调度周期中应该分配的时间片。时间片用完就应该被抢占
	ideal_runtime = sched_slice(cfs_rq, curr); 
	//delta_exec：是当前进程已经运行的实际时间
	//
	delta_exec = curr->sum_exec_runtime - curr->prev_sum_exec_runtime; 
	if (delta_exec > ideal_runtime) {
		//如果实际运行时间已经超过分配给进程的时间片，自然就需要抢占当前进程。设置TIF_NEED_RESCHED flag
		resched_curr(rq_of(cfs_rq));           
		clear_buddies(cfs_rq, curr);
		return;
	}
 
	// 为了防止频繁过度抢占，应该保证每个进程运行时间不应该小于最小粒度时间sysctl_sched_min_granularity
	// 因此如果运行时间小于最小粒度时间，不应该抢占
	if (delta_exec < sysctl_sched_min_granularity) 
		return;
 
    //从红黑树中找到虚拟时间最小的调度实体
	se = __pick_first_entity(cfs_rq);             
	delta = curr->vruntime - se->vruntime;
 
    //如果当前进程的虚拟时间仍然比红黑树中最左边调度实体虚拟时间小，也不应该发生调度
	if (delta < 0)                                
		return;

	//这里 delta 是 vruntime 差值（虚拟时间），而 ideal_runtime 是 sched_slice 得到的物理时间，二者量纲并不严格一致
	//这看似"bug"，实则是内核有意为之的近似：由于 vruntime 的增长速率与权重成反比，对权重小（低优先级）的任务而言相同物理时间会换算出更大的 vruntime 差值，因此该判断会让轻权重任务更容易被抢占，符合 CFS 让高优先级任务获得更多 CPU 的目标
	if (delta > ideal_runtime)                    
		resched_curr(rq_of(cfs_rq));
}

// schedule 方法入口
asmlinkage __visible void __sched schedule(void){
    struct task_struct *tsk = current;
    sched_submit_work(tsk);
    do {
        preempt_disable();
        __schedule(false);
        sched_preempt_enable_no_resched();
    } while (need_resched());
}

//主要逻辑是在 __schedule 函数中实现的
static void __sched notrace __schedule(bool preempt)
{
	struct task_struct *prev, *next;
	struct rq_flags rf;
	struct rq *rq;
	int cpu;
 	// 在当前cpu 上取出任务队列rq（其实是红黑树）
	cpu = smp_processor_id();
	rq = cpu_rq(cpu);

	//prev即 即将要被切换走的"正在运行"的进程
	prev = rq->curr;
 
	if (!preempt && prev->state) {
		if (unlikely(signal_pending_state(prev->state, prev))) {
			prev->state = TASK_RUNNING;
		} else {
			//针对主动放弃cpu进入睡眠的进程，需要从对应的就绪队列上删除该进程（见下文分析）
			deactivate_task(rq, prev, DEQUEUE_SLEEP | DEQUEUE_NOCLOCK);    
			prev->on_rq = 0;
		}
	}

	// 获取下一个待执行任务，其实就是从当前rq 的红黑树节点中选择vruntime最小的节点
	next = pick_next_task(rq, prev, &rf);   
	//清除TIF_NEED_RESCHED flag
	clear_tsk_need_resched(prev);           
 
	if (likely(prev != next)) {
		rq->curr = next;
		// 当选出的继任者和前任不同，就要进行上下文切换，继任者进程正式进入运行
		//上下文切换，从prev进程切换到next进程
		rq = context_switch(rq, prev, next, &rf);    
	}
 
	balance_callback(rq);
}

static struct task_struct *
pick_next_task_fair(struct rq *rq, struct task_struct *prev, struct rq_flags *rf)
{
	struct cfs_rq *cfs_rq = &rq->cfs;
	struct sched_entity *se;
	struct task_struct *p;
	int new_tasks;
 
again:
	if (!cfs_rq->nr_running)
		goto idle;
	
	//处理prev进程的后续工作，当进程让出cpu时就会调用该函数
	put_prev_task(rq, prev);                        
	do {
		//选择最适合运行的调度实体
		se = pick_next_entity(cfs_rq, NULL);
		//选择出来的调度实体se还需要继续加工一下才能投入运行，加工方法set_next_entity，见下文分析     
		set_next_entity(cfs_rq, se);              
		cfs_rq = group_cfs_rq(se);
		//针对没有使能组调度的情况下，循环一次即退出循环
	} while (cfs_rq);                           
 
	p = task_of(se);
#ifdef CONFIG_SMP
	list_move(&p->se.group_node, &rq->cfs_tasks);
#endif
 
	if (hrtick_enabled(rq))
		hrtick_start_fair(rq, p);
 
	return p;
idle:
	new_tasks = idle_balance(rq, rf);
 
	if (new_tasks < 0)
		return RETRY_TASK;
 
	if (new_tasks > 0)
		goto again;
 
	return NULL;
}

static void put_prev_task_fair(struct rq *rq, struct task_struct *prev)
{
	struct sched_entity *se = &prev->se;
	struct cfs_rq *cfs_rq;
	for_each_sched_entity(se) {         
		cfs_rq = cfs_rq_of(se);
		put_prev_entity(cfs_rq, se);      
	}
}

static void put_prev_entity(struct cfs_rq *cfs_rq, struct sched_entity *prev)
{
	/*
	 * If still on the runqueue then deactivate_task()
	 * was not called and update_curr() has to be done:
	 */
	/*
	如果prev进程依然在就绪队列上，极有可能是prev进程被强占的情况。在让出cpu之前需要更新进程虚拟时间等信息
	如果prev进程不在就绪队列上，这里可以直接跳过更新。因为，prev进程在deactivate_task()中已经调用了update_curr()，所以这里就可以省略了
	*/
	if (prev->on_rq)                            
		update_curr(cfs_rq);

	/*
	如果prev进程依然在就绪队列上，需要重新将prev进程插入红黑树等待调度
	*/
	if (prev->on_rq) {
		/* Put 'current' back into the tree. */

		/*
			重新将prev进程插入红黑树等待调度
		*/
		__enqueue_entity(cfs_rq, prev);         
		/* in !on_rq case, update occurred at dequeue */

		/*
		更新prev进程的负载信息，这些信息在负载均衡的时候会用到
		*/
		update_load_avg(cfs_rq, prev, 0);      
	}
	/*
	后事已经处理完毕，就绪队列的curr指针也应该指向NULL，代表当前就绪队列上没有正在运行的进程
	*/
	cfs_rq->curr = NULL;                        
}

static void
set_next_entity(struct cfs_rq *cfs_rq, struct sched_entity *se)
{
	/* 'current' is not kept within the tree. */
	if (se->on_rq) {
		/*
		__dequeue_entity()是将调度实体从红黑树中删除，针对即将运行的进程，都会从红黑树中删除当前进程。当进程被强占后，调用put_prev_entity()函数会重新插入红黑树。因此这个地方和put_prev_entity()函数中加入红黑树是个呼应
		*/
		__dequeue_entity(cfs_rq, se);            
		//更新进程的负载信息，负载均衡会使用       
		update_load_avg(cfs_rq, se, UPDATE_TG);  
	}

	//更新就绪队列curr成员，现在se是当前正在运行的进程
	cfs_rq->curr = se;
	//update_stats_curr_start更新调度实体exec_start成员，为update_curr()函数统计时间做准备                            
    update_stats_curr_start(cfs_rq, se);
	//check_preempt_tick()函数用到，统计当前进程已经运行的时间，以此判断是否能够被其他进程抢占
	se->prev_sum_exec_runtime = se->sum_exec_runtime;   
}

static void dequeue_task_fair(struct rq *rq, struct task_struct *p, int flags)
{
	struct cfs_rq *cfs_rq;
	struct sched_entity *se = &p->se;
	int task_sleep = flags & DEQUEUE_SLEEP;
	for_each_sched_entity(se) {                 
		cfs_rq = cfs_rq_of(se);
		//将调度实体se从对应的就绪队列cfs_rq上删除
		dequeue_entity(cfs_rq, se, flags);      
	}
	if (!se)
		sub_nr_running(rq, 1);
}

static void dequeue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int flags)
{
	//出就绪队列之前更新下cfs_rq已经curr当前正在运行进程的虚拟时间等信息
	update_curr(cfs_rq);                          
	if (se != cfs_rq->curr)
		//如果se不是当前正在运行的进程，其对应的调度实体还在cfs就绪队列红黑树上，调用__dequeue_entity()函数从红黑树上删除节点
		__dequeue_entity(cfs_rq, se);          
	//调度实体已经从就绪队列的红黑树上删除，因此更新on_rq成员
	se->on_rq = 0;                                

	//更新就绪队列相关信息，例如权重信息
	account_entity_dequeue(cfs_rq, se);           
	if (!(flags & DEQUEUE_SLEEP))
		//如果进程不是睡眠（例如从一个CPU迁移到另一个CPU），进程最小虚拟时间需要减去当前就绪队列对应的最小虚拟时间
		//迁移之后会在enqueue的时候加上对应CPU（可能是同个也可能是另外一个）的CFS就绪队列最小虚拟时间
		se->vruntime -= cfs_rq->min_vruntime;     
} 

static void account_entity_dequeue(struct cfs_rq *cfs_rq, struct sched_entity *se)
{
	//从就绪队列权重总和中减去当前dequeue调度实体的权重
	update_load_sub(&cfs_rq->load, se->load.weight); 
	if (!parent_entity(se))
		update_load_sub(&rq_of(cfs_rq)->load, se->load.weight);
#ifdef CONFIG_SMP
	if (entity_is_task(se)) {
		account_numa_dequeue(rq_of(cfs_rq), task_of(se));
		// 从链表中删除调度实体se
		list_del_init(&se->group_node);                   
	}
#endif
	//就绪队列中可运行调度实体计数减1
	cfs_rq->nr_running--;                                 
}

// net/core/dev.c
static inline void ____napi_schedule(struct softnet_data *sd,
				     struct napi_struct *napi)
{
	list_add_tail(&napi->poll_list, &sd->poll_list);
	__raise_softirq_irqoff(NET_RX_SOFTIRQ);   // 置位软中断 pending 位
}

// kernel/softirq.c
void irq_exit(void)
{
	......
	account_irq_exit_time(current);              // 结算本段硬中断时间（见下文 irqtime）
	preempt_count_sub(HARDIRQ_OFFSET);
	if (!in_interrupt() && local_softirq_pending())
		invoke_softirq();
	......
}

static inline void invoke_softirq(void)
{
	//若 ksoftirqd 已经在运行，则不在此就地处理，交给 ksoftirqd（避免重复/抢占）
	if (ksoftirqd_running())
		return;

	if (!force_irqthreads) {
#ifdef CONFIG_HAVE_IRQ_EXIT_ON_IRQ_STACK
		__do_softirq();                      // 就地在（软）中断栈上执行
#else
		do_softirq_own_stack();
#endif
	} else {
		wakeup_softirqd();                   // 强制线程化：唤醒 ksoftirqd
	}
}

// kernel/softirq.c
#define MAX_SOFTIRQ_TIME  msecs_to_jiffies(2)   // 软中断最长连续处理 2ms
#define MAX_SOFTIRQ_RESTART 10                  // 最多重启 10 轮

//https://elixir.bootlin.com/linux/v4.11.6/source/kernel/softirq.c#L241
asmlinkage __visible void __softirq_entry __do_softirq(void)
{
	unsigned long end = jiffies + MAX_SOFTIRQ_TIME;
	int max_restart = MAX_SOFTIRQ_RESTART;
	__u32 pending;
	int softirq_bit;

	pending = local_softirq_pending();

	//https://elixir.bootlin.com/linux/v4.11.6/source/kernel/softirq.c#L259
	//注意，下面会详细说明
	account_irq_enter_time(current);             // 软中断开始，结算前一段时间
	__local_bh_disable_ip(_RET_IP_, SOFTIRQ_OFFSET);
restart:
	set_softirq_pending(0);
	local_irq_enable();
	//... 遍历 pending 逐个执行 h->action(h)，NET_RX_SOFTIRQ 对应 net_rx_action ...
	local_irq_disable();

	pending = local_softirq_pending();
	if (pending) {
		//预算未耗尽且无需重新调度，则继续下一轮；否则唤醒 ksoftirqd 处理剩余软中断
		if (time_before(jiffies, end) && !need_resched() &&
		    --max_restart)
			goto restart;

		wakeup_softirqd();                   // 负载过高：下沉到 ksoftirqd
	}
	
	//https://elixir.bootlin.com/linux/v4.11.6/source/kernel/softirq.c#L309
	account_irq_exit_time(current);              // 软中断结束，结算本段时间
	__local_bh_enable(SOFTIRQ_OFFSET);
}

// net/core/dev.c
int netdev_budget __read_mostly = 300;           // 一轮 poll 最多处理的报文数

static __latent_entropy void net_rx_action(struct softirq_action *h)
{
	struct softnet_data *sd = this_cpu_ptr(&softnet_data);
	//v4.11.6 此处为硬编码的 2 jiffies；netdev_budget_usecs 是 4.12 才引入的可调 sysctl
	unsigned long time_limit = jiffies + 2;
	int budget = netdev_budget;
	LIST_HEAD(list);
	LIST_HEAD(repoll);

	local_irq_disable();
	list_splice_init(&sd->poll_list, &list);
	local_irq_enable();

	for (;;) {
		struct napi_struct *n;

		if (list_empty(&list)) {
			if (!sd_has_rps_ipi_waiting(sd) && list_empty(&repoll))
				goto out;
			break;
		}

		n = list_first_entry(&list, struct napi_struct, poll_list);
		budget -= napi_poll(n, &repoll);       // 调用驱动注册的 poll 收包

		/* If softirq window is exhausted then punt. */
		//预算或时间耗尽：记一次 time_squeeze，跳出（剩余留待下一轮软中断/ksoftirqd）
		if (unlikely(budget <= 0 ||
			     time_after_eq(jiffies, time_limit))) {
			sd->time_squeeze++;
			break;
		}
	}
	//... 若仍有 napi 待处理，重新 raise NET_RX_SOFTIRQ ...
	if (!list_empty(&sd->poll_list))
		__raise_softirq_irqoff(NET_RX_SOFTIRQ);
out:
	......
}

//https://elixir.bootlin.com/linux/v4.11.6/source/kernel/sched/cputime.c#L37
static void irqtime_account_delta(struct irqtime *irqtime, u64 delta,
				  enum cpu_usage_stat idx)
{
	u64 *cpustat = kcpustat_this_cpu->cpustat;

	u64_stats_update_begin(&irqtime->sync);

	//把中断耗时累加进 per-cpu 的 `struct irqtime`

	cpustat[idx] += delta;          // 供 /proc/stat 的 hi/si 展示
	irqtime->total += delta;        // 供调度器读取（irq_time_read）
	irqtime->tick_delta += delta;	
	u64_stats_update_end(&irqtime->sync);
}

//https://elixir.bootlin.com/linux/v4.11.6/source/kernel/sched/cputime.c#L53
void irqtime_account_irq(struct task_struct *curr)
{
	struct irqtime *irqtime = this_cpu_ptr(&cpu_irqtime);
	s64 delta;
	int cpu;

	if (!sched_clock_irqtime)       // 未开启 IRQ_TIME_ACCOUNTING 则直接返回
		return;

	cpu = smp_processor_id();
	delta = sched_clock_cpu(cpu) - irqtime->irq_start_time;
	irqtime->irq_start_time += delta;

	/*
	 * We do not account for softirq time from ksoftirqd here.
	 * We want to continue accounting softirq time to ksoftirqd thread
	 * in that case, so as not to confuse scheduler with a special task
	 * that do not consume any time, but still wants to run.
	 */
	//硬中断时间 -> CPUTIME_IRQ
	if (hardirq_count())
		irqtime_account_delta(irqtime, delta, CPUTIME_IRQ);
	//软中断时间 -> CPUTIME_SOFTIRQ，但【当且仅当】当前不是 ksoftirqd 时才计入
	else if (in_serving_softirq() && curr != this_cpu_ksoftirqd())
		irqtime_account_delta(irqtime, delta, CPUTIME_SOFTIRQ);
}

// kernel/sched/core.c
static void update_rq_clock_task(struct rq *rq, s64 delta)
{
#if defined(CONFIG_IRQ_TIME_ACCOUNTING) || defined(CONFIG_PARAVIRT_TIME_ACCOUNTING)
	s64 steal = 0, irq_delta = 0;
#endif
#ifdef CONFIG_IRQ_TIME_ACCOUNTING
	//本次时间片内新增的中断时间 = 当前累计 irqtime - 上次已结算的 prev_irq_time
	irq_delta = irq_time_read(cpu_of(rq)) - rq->prev_irq_time;

	/*
	 * Since irq_time is only updated on {soft,}irq_exit, we might run into
	 * this case when a previous update_rq_clock() happened inside a
	 * {soft,}irq region. ...
	 * 保证 ->clock_task 单调：若中断时间比本次 delta 还大，先只吃掉 delta 部分
	 */
	if (irq_delta > delta)
		irq_delta = delta;

	rq->prev_irq_time += irq_delta;
	delta -= irq_delta;             // 关键：从 delta 中扣除中断时间
#endif
#ifdef CONFIG_PARAVIRT_TIME_ACCOUNTING
	//虚拟化场景下再扣除 steal time（被 hypervisor 偷走的时间），思路完全一致
	if (static_key_false((&paravirt_steal_rq_enabled))) {
		steal = paravirt_steal_clock(cpu_of(rq));
		steal -= rq->prev_steal_time_rq;
		if (unlikely(steal > delta))
			steal = delta;
		rq->prev_steal_time_rq += steal;
		delta -= steal;
	}
#endif

	rq->clock_task += delta;        // 任务时钟只累加"纯任务执行时间"
	//...
}

//https://elixir.bootlin.com/linux/v4.11.6/source/kernel/sched/core.c#L226
void update_rq_clock(struct rq *rq)
{
	s64 delta;
	//...
	delta = sched_clock_cpu(cpu_of(rq)) - rq->clock;
	if (delta < 0)
		return;
	rq->clock += delta;             // rq->clock：墙上时间（含中断）
	update_rq_clock_task(rq, delta);// rq->clock_task：扣除中断/steal 后的任务时间
}

static void update_curr(struct cfs_rq *cfs_rq)
{
	struct sched_entity *curr = cfs_rq->curr;
	//注意：这里取的是 rq_clock_task（任务时钟），不是 rq_clock（墙上时钟）
	u64 now = rq_clock_task(rq_of(cfs_rq));
	u64 delta_exec;
	//...
	delta_exec = now - curr->exec_start;   // 因此 delta_exec 不含中断时间
	//...
	curr->vruntime += calc_delta_fair(delta_exec, curr);  // vruntime 也就不含中断时间
	update_min_vruntime(cfs_rq);
}

// kernel/sched/sched.h
static inline u64 rq_clock(struct rq *rq)        // 墙上时钟
{
	return rq->clock;
}
static inline u64 rq_clock_task(struct rq *rq)   // 任务时钟（已扣除中断/steal）
{
	return rq->clock_task;
}

// kernel/sched/cputime.c（irqtime_account_process_tick 节选）
	if (this_cpu_ksoftirqd() == p) {
		/*
		 * ksoftirqd time do not get accounted in cpu_softirq_time.
		 * So, we have to handle it separately here.
		 * Also, p->stime needs to be updated for ksoftirqd.
		 */
		account_system_index_time(p, cputime, CPUTIME_SOFTIRQ);
	}

void wake_up_new_task(struct task_struct *p)
{
	struct rq_flags rf;
	struct rq *rq;
 
	p->state = TASK_RUNNING;

	rq = __task_rq_lock(p, &rf);
	activate_task(rq, p, ENQUEUE_NOCLOCK);                                   
	p->on_rq = TASK_ON_RQ_QUEUED;
	// 既然唤醒了新进程，那么就检查是否能够抢占执行
	check_preempt_curr(rq, p, WF_FORK);                                      
}

void check_preempt_curr(struct rq *rq, struct task_struct *p, int flags)
{
	const struct sched_class *class;
 
	if (p->sched_class == rq->curr->sched_class) {
		//唤醒的进程和当前的进程同属于一个调度类，直接调用调度类的check_preempt_curr函数检查抢占条件
		rq->curr->sched_class->check_preempt_curr(rq, p, flags);   
	} else {
		//否则如果唤醒的进程和当前进程不属于一个调度类，就需要按照调度器类的优先级来选择
		//例如，当期进程是CFS调度类，唤醒的进程是RT调度类，自然实时进程是需要抢占当前进程的，因为优先级更高
		for_each_class(class) {                                    
			if (class == rq->curr->sched_class)
				break;
			if (class == p->sched_class) {
				resched_curr(rq);
				break;
			}
		}
	}
}

static void check_preempt_wakeup(struct rq *rq, struct task_struct *p, int wake_flags)
{
	struct sched_entity *se = &curr->se, *pse = &p->se;
	struct cfs_rq *cfs_rq = task_cfs_rq(curr);
 
	//重要：检查唤醒的进程是否满足抢占当前进程的条件
	if (wakeup_preempt_entity(se, pse) == 1)   
		goto preempt;
 
	return;
preempt:
	//如果可以抢占当前进程，设置TIF_NEED_RESCHED flag
	resched_curr(rq);                           
}

static int wakeup_preempt_entity(struct sched_entity *curr, struct sched_entity *se)
{
	s64 gran, vdiff = curr->vruntime - se->vruntime;
 
	if (vdiff <= 0)                    
		return -1;
 
	//默认情况下，wakeup_gran()函数返回的值是1ms根据调度实体se的权重计算的虚拟时间
	gran = wakeup_gran(se);
	if (vdiff > gran)                  
		return 1;
 
	return 0;
}

static unsigned long
wakeup_gran(struct sched_entity *curr, struct sched_entity *se)
{
	unsigned long gran = sysctl_sched_wakeup_granularity;

	/*
	 * Since its curr running now, convert the gran from real-time
	 * to virtual-time in his units.
	 *
	 * By using 'se' instead of 'curr' we penalize light tasks, so
	 * they get preempted easier. That is, if 'se' < 'curr' then
	 * the resulting gran will be larger, therefore penalizing the
	 * lighter, if otoh 'se' > 'curr' then the resulting gran will
	 * be smaller, again penalizing the lighter task.
	 *
	 * This is especially important for buddies when the leftmost
	 * task is higher priority than the buddy.
	 */
	return calc_delta_fair(gran, se);
}

static void __enqueue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se)
{
	//...
		//利用entity_before()函数比较两个调度实体se的vruntime值大小
		if (entity_before(se, entry)) {
			link = &parent->rb_left;
		}
	//...
}

static inline int entity_before(struct sched_entity *a, struct sched_entity *b)
{
	return (s64)(a->vruntime - b->vruntime) < 0;
}

static inline u64 max_vruntime(u64 max_vruntime, u64 vruntime)
{
	s64 delta = (s64)(vruntime - max_vruntime);
	if (delta > 0)
		max_vruntime = vruntime;
 
	return max_vruntime;
}

//通过 update_curr() 计算当前进程已运行的物理时间（delta_exec），并更新其 vruntime
void update_curr(struct cfs_rq *cfs_rq) {
	// ...
    struct sched_entity *curr = cfs_rq->curr;
    u64 now = rq_clock_task(rq_of(cfs_rq));
    u64 delta_exec = now - curr->exec_start;  // 计算实际运行时间
	// ...
    curr->vruntime += calc_delta_fair(delta_exec, curr); // 更新 vruntime
    curr->exec_start = now;
}

/*
 * Preempt the current task with a newly woken task if needed:
 */
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;

	ideal_runtime = sched_slice(cfs_rq, curr);
	// 作用：
	delta_exec = curr->sum_exec_runtime - curr->prev_sum_exec_runtime;
	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;

	// 获取当前cfs_rq红黑树上最左边的节点
	se = __pick_first_entity(cfs_rq);

	// 计算当前正在运行的进程vruntime 与红黑树vruntime最小节点的vruntime的差值
	delta = curr->vruntime - se->vruntime;

	if (delta < 0)
		//说明当前运行进程的vruntime较小
		return;

	// 如果差值delta大于ideal_runtime，那么则通过resched_curr标记抢占
	// 注意到ideal_runtime是sched_slice函数的结果
	if (delta > ideal_runtime)
		resched_curr(rq_of(cfs_rq));	//触发重新调度
}

// kernel/sched/sched.h
struct task_group {
	struct sched_entity	**se;        // 每 CPU 一个组调度实体
	struct cfs_rq		**cfs_rq;    // 每 CPU 一个组的 CFS 就绪队列
	unsigned long		shares;      // 组权重（对应 cpu.shares）
	......
};

#define for_each_sched_entity(se) \
		for (; se; se = se->parent)

// v4.11.6：sched_entity 内嵌 sched_avg（注意此版本尚无 runnable_weight/runnable_avg）
struct sched_avg {
	u64		last_update_time;
	u64		load_sum;
	u32		util_sum;
	u32		period_contrib;
	unsigned long	load_avg;    // 加权可运行负载均值
	unsigned long	util_avg;    // 利用率均值
};

// kernel/sched/core.c（快速路径：全是 CFS 任务时直接走 fair 类）
static inline struct task_struct *
pick_next_task(struct rq *rq, struct task_struct *prev, struct rq_flags *rf)
{
	const struct sched_class *class;
	struct task_struct *p;

	if (likely(prev->sched_class == &fair_sched_class &&
		   rq->nr_running == rq->cfs.h_nr_running)) {
		p = fair_sched_class.pick_next_task(rq, prev, rf);
		......
		return p;
	}
	//慢速路径：按调度类优先级依次尝试
	for_each_class(class) {
		p = class->pick_next_task(rq, prev, rf);
		if (p)
			return p;
	}
}