一直对CFS（Completely Fair Scheduling，完全公平调度）中的虚拟运行时间（vruntime）不太理解，最近在看cgroup中的cpu子系统算是搞清楚了它是怎么回事。

先简单说一下CFS调度算法的思想：理想状态下每个进程都能获得相同的时间片，并且同时运行在CPU上，但实际上一个CPU同一时刻运行的进程只能有一个。也就是说，当一个进程占用CPU时，其他进程就必须等待。CFS为了实现公平，必须惩罚当前正在运行的进程，以使那些正在等待的进程下次被调度。

具体实现时，CFS通过每个进程的虚拟运行时间（vruntime）来衡量哪个进程最值得被调度。CFS中的就绪队列是一棵以vruntime为键值的红黑树，虚拟时间越小的进程越靠近整个红黑树的最左端。因此，调度器每次选择位于红黑树最左端的那个进程，该进程的vruntime最小。

虚拟运行时间是通过进程的实际运行时间和进程的权重（weight）计算出来的。在CFS调度器中，将进程优先级这个概念弱化，而是强调进程的权重。一个进程的权重越大，则说明这个进程更需要运行，因此它的虚拟运行时间就越小，这样被调度的机会就越大。

那么，在用户态进程的优先级nice值与CFS调度器中的权重又有什么关系？在内核中通过prio_to_weight数组进行nice值和权重的转换。

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

而在内核中，进程的虚拟运行时间是自进程诞生以来进行累加的，每个时钟周期内一个进程的虚拟运行时间是通过下面的方法计算的：

一次调度间隔的虚拟运行时间=实际运行时间*（NICE_0_LOAD/权重）

其中，NICE_0_LOAD是nice为0时的权重。也就是说，nice值为0的进程实际运行时间和虚拟运行时间相同。通过这个公式可以看到，权重越大的进程获得的虚拟运行时间越小，那么它将被调度器所调度的机会就越大。

内核中的调度算法在不断变化，2.4内核中的调度器是在所有的进程中选择优先级最高的进程，2.6内核前期的调度器是基于O(1)算法的，而2.6.23版本之后的内核采用CFS调度算法，并同时对调度器进行了比较大的改善。内核主要是引入了调度器类来增加调度器的可扩展性。调度器类将各种调度策略模块化，封装了对不同调度策略的具体实现。

内核中对进程调度的方法有两种，其一为周期性调度器（generic scheduler），它对进行进行周期性的调度，以固定的频率运行；其二为主调度器（main scheduler），如果进程要进行睡眠或因为其他原因主动放弃CPU，那么就直接调用主调度器。

内核的主调度器是通过schedule()实现的，该函数的主要工作就是挑选下一个应该被调度的进程next。
该函数首先禁止内核抢占，并且依次获取当前CPU编号cpu、当前CPU对应的运行队列rq、当前进程的切换次数switch_count以及当前进程的描述符prev。

asmlinkage void __sched schedule(void)
{
	struct task_struct *prev, *next;
	unsigned long *switch_count;
	struct rq *rq;
	int cpu;

need_resched:
	preempt_disable();
	cpu = smp_processor_id();
	rq = cpu_rq(cpu);
	rcu_sched_qs(cpu);
	prev = rq->curr;
	switch_count = &prev->nivcsw;

	release_kernel_lock(prev);
need_resched_nonpreemptible:

	schedule_debug(prev);

	if (sched_feat(HRTICK))
		hrtick_clear(rq);

接下来通过update_rq_clock()更新就绪队列上的时钟，接着通过clear_tsk_need_resched()清除当前进程prev的重新调度标志TIF_NEED_RESCHED。

	raw_spin_lock_irq(&rq->lock);
	update_rq_clock(rq);
	clear_tsk_need_resched(prev);

如果当前进程是可中断睡眠状态（可运性状态TASK_RUNNING宏的值为0），但它却收到了某个唤醒它的信号，那么当前进程的标志被更新为TASK_RUNNING,等待再次被调度。否则，通过deactivate_task()将当前进程prev从就绪队列中删除。

这里的deactivate_task()根据调度类的不同实现也有所不同，但这些差异对主调度器是透明的，因为调度器类在各种调度实例和调度器之间起到了连接作用。该函数的核心语句即为：

p->sched_class->dequeue_task(rq, p, sleep);

sched_class是进程描述符中描述当前进程所属调度类的字段，通过这个字段回调钩子函数dequeue_task()。

	if (prev->state && !(preempt_count() & PREEMPT_ACTIVE)) {
		if (unlikely(signal_pending_state(prev->state, prev)))
			prev->state = TASK_RUNNING;
		else
			deactivate_task(rq, prev, 1);
		switch_count = &prev->nvcsw;
	}

	pre_schedule(rq, prev);

	if (unlikely(!rq->nr_running))
		idle_balance(cpu, rq);

通过put_prev_task()将prev进程重新插入到就绪队列合适的位置中。再通过pick_next_task()在当前的就绪队列中挑选下一个应该被执行的进程next。这两个函数都属于调度器类中的钩子函数，它们的具体实现根据调度实例的不同而不同。

	put_prev_task(rq, prev);
	next = pick_next_task(rq);

有时候，调度器所选的下一个被执行的进程恰好就是当前进程，那么调度器就不必耗费精力去执行上下文切换，但这种情况不是经常发生的。如果prev和next不是同一个进程，那么先通过sched_info_switch()更新两个进程描述符的相关字段，并且更新可运行队列的相关字段。

接下来调用context_switch()进行prev和next两个进程的上下文切换，该函数由一段汇编代码组成。

	if (likely(prev != next)) {
		sched_info_switch(prev, next);
		perf_event_task_sched_out(prev, next);

		rq->nr_switches++;
		rq->curr = next;
		++*switch_count;

		context_switch(rq, prev, next); /* unlocks the rq */
		/*
		 * the context switch might have flipped the stack from under
		 * us, hence refresh the local variables.
		 */
		cpu = smp_processor_id();
		rq = cpu_rq(cpu);
	} else
		raw_spin_unlock_irq(&rq->lock);

切换完毕后，当前的进程就是新选择的进程，它会开始执行。而被切换出去的进程重新运行时会从切换函数的下一条语句开始执行。

	post_schedule(rq);

	if (unlikely(reacquire_kernel_lock(current) < 0)) { 		prev = rq->curr;
		switch_count = &prev->nivcsw;
		goto need_resched_nonpreemptible;
	}

	preempt_enable_no_resched();
	if (need_resched())
		goto need_resched;
}

根据上述对主调度器函数源码的分析，可以总结出主调度器的主要功能如下：

1.获取当前进程的描述符以及本地CPU的运行队列

2.将当前进程prev放入可运行队列中，等待下一次被重新调度

3.在当前的可运行队列中选取下一个被调度的新进程next

4.从当前进程切换到新进程