基于CFS算法的schedule()源码分析

penghuan · 发表于 2013-11-21 09:30:18

本文转自：http://edsionte.com/techblog/archives/3819

内核中的调度算法在不断变化，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.从当前进程切换到新进程

基于CFS算法的schedule()源码分析 [复制链接]

浏览过的版块

		自动登录	找回密码
密码