完全公平调度

struct task_struct {
    ...
    int     prio;    // 动态优先级
    int     static_prio;    // 静态优先级
    int    normal_prio;    // 普通优先级
    unsigned int     rt_priority;    //实时优先级
     unsigned int     policy;    // 优先级策略
    ...
}

static int effective_prio(struct task_struct *p)
{
	p->normal_prio = normal_prio(p);
	/*
	 * If we are RT tasks or we were boosted to RT priority,
	 * keep the priority unchanged. Otherwise, update priority
	 * to the normal priority:
	 */
	if (!rt_prio(p->prio))
		return p->normal_prio;
	return p->prio;
}

进程创建的时候优先级初始化
copy_process
    sched_fork
        p->prio = current->normal_prio;

nice系统调用调整静态优先级
nice
    set_user_nice
        p->static_prio = NICE_TO_PRIO(nice);
        p->prio = effective_prio(p);

static const int 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,
};

static const u32 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;    //  优化数值，避免除法运算  weight * inv_weight = 2^32
};

static void set_load_weight(struct task_struct *p)
{
    int prio = p->static_prio - MAX_RT_PRIO;
    struct load_weight *load = &p->se.load;

    load->weight = scale_load(prio_to_weight[prio]);
    load->inv_weight = prio_to_wmult[prio];
}

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

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

	return delta;
}

struct rq {
    ...
    struct load_weight load; /* capture load from *all* tasks on this cpu: */
    ...
}

struct cfs_rq {
    ...
    struct load_weight load;
    ...
}
static inline void update_load_add(struct load_weight *lw, unsigned long inc);
static inline void update_load_sub(struct load_weight *lw, unsigned long dec);
static inline void update_load_set(struct load_weight *lw, unsigned long w);

static u64 __sched_period(unsigned long nr_running)
{
	if (unlikely(nr_running > sched_nr_latency))
		return nr_running * sysctl_sched_min_granularity; // 0.75ms
	else
		return sysctl_sched_latency;
}

struct task_struct
{
    /*  ......  */
    struct sched_entity se;
    /*  ......  */
}

struct sched_entity {
  struct load_weight	load; 实体权重
	unsigned int		on_rq;  是否在运行队列上
	u64			exec_start;  本次调度开始执行时间
	u64			sum_exec_runtime;  总的执行时间,真实物理时间
	u64			vruntime;  总的虚拟运行时间
	u64			prev_sum_exec_runtime; 进程退出运行队列时会把sum_exec_runtime存放到这里
}

struct rq  {
  nr_running 可运行的进程总数，包含普通进程和实时进程；任务enqueue时 ++; 任务dequeu时--
  load         所有task的load 总和
  cpu_load  历史负载记录
  cfs / rt   CFS队列和RT队列
  curr    当前正在运行的task
  idle    指向idle线程
  clock   运行时钟总数
  clock_task  开启中断统计的话，就会剔除花在中断上的时间  
}

/*
 * Update the current task's runtime statistics.
 */
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;

	delta_exec = now - curr->exec_start;  // 上次更新和本次更新 时间戳差值

	curr->exec_start = now;    // 更新启动时间戳

	curr->sum_exec_runtime += delta_exec;  // 计入总的实际运行时间

	curr->vruntime += calc_delta_fair(delta_exec, curr);  // 更新虚拟运行时间
	update_min_vruntime(cfs_rq); // 更新队列 min_vruntime

  ...
}

static void update_min_vruntime(struct cfs_rq *cfs_rq)
{
	u64 vruntime = cfs_rq->min_vruntime;

	if (cfs_rq->curr)
		vruntime = cfs_rq->curr->vruntime;

	if (cfs_rq->rb_leftmost) {
		struct sched_entity *se = rb_entry(cfs_rq->rb_leftmost,
						   struct sched_entity,
						   run_node);

		if (!cfs_rq->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);
  ...
}

dequeue_entity()：
    if (!(flags & DEQUEUE_SLEEP))
        se->vruntime -= cfs_rq->min_vruntime;

task_fork_fair():
    se->vruntime -= cfs_rq->min_vruntime;

switched_from_fair():
    if (!se->on_rq && p->state != TASK_RUNNING)
    {
        /*
         * Fix up our vruntime so that the current sleep doesn't
         * cause 'unlimited' sleep bonus.
         */
        place_entity(cfs_rq, se, 0);
        se->vruntime -= cfs_rq->min_vruntime;
    }

enqueue_entity:
    if (!(flags & ENQUEUE_WAKEUP) || (flags & ENQUEUE_WAKING))
        se->vruntime += cfs_rq->min_vruntime;

attach_task_cfs_rq:

if (!vruntime_normalized(p))

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.
	 */
	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. */
	se->vruntime = max_vruntime(se->vruntime, vruntime);
}

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); // 更新 rq->clock 和 rq->clock_task
	curr->sched_class->task_tick(rq, curr, 0);   // task_tick_fair
	update_cpu_load_active(rq);  // 更新队列的cpu_load[]
  ...
}

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_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(cfs_rq); // 更新vruntime

	/*
	 * Ensure that runnable average is periodically updated.
	 */
	update_load_avg(curr, 1);
	update_cfs_shares(cfs_rq);

	if (cfs_rq->nr_running > 1)
		check_preempt_tick(cfs_rq, curr); // 根据运行时间检查当前进程是否需要被调度出去
}

static void __sched notrace __schedule(bool preempt)
{
	struct task_struct *prev, *next;
	unsigned long *switch_count;
	struct rq *rq;
	int cpu;

  ...

	if (task_on_rq_queued(prev))
		update_rq_clock(rq);

	next = pick_next_task(rq, prev);  // 从就绪队列选择一个最合适的进程next
	clear_tsk_need_resched(prev); // 清除TIF_NEED_RESCHED标记
	clear_preempt_need_resched();
	rq->clock_skip_update = 0;

	if (likely(prev != next)) {
		rq->nr_switches++;
		rq->curr = next;
		++*switch_count;

		rq = context_switch(rq, prev, next); // 切换到next进程运行
		cpu = cpu_of(rq);
	} else {
		lockdep_unpin_lock(&rq->lock);
		raw_spin_unlock_irq(&rq->lock);
	}

	balance_callback(rq);  // 负责均衡
}

static void task_fork_fair(struct task_struct *p)
{
  ...

	place_entity(cfs_rq, se, 1);

	if (sysctl_sched_child_runs_first && curr && entity_before(curr, se)) {
		swap(curr->vruntime, se->vruntime);
		resched_curr(rq);
	}

	se->vruntime -= cfs_rq->min_vruntime;
}