Linux Complete Fair Scheduler (CFS) 进程调度器学习笔记（针对内核版本3.6.11）

首先声明，本文参考了peimichael的文章: 《CFS 调度器学习笔记》http://blog.csdn.net/peimichael/article/details/5218335

文章结构也和peimichael的类似。

情景分析1：创建新进程。

/*
 * wake_up_new_task - wake up a newly created task for the first time.                                                                                        
 *
 * This function will do some initial scheduler statistics housekeeping
 * that must be done for every newly created context, then puts the task
 * on the runqueue and wakes it.
 */
void wake_up_new_task(struct task_struct *p)
{
        unsigned long flags;
        struct rq *rq;

        raw_spin_lock_irqsave(&p->pi_lock, flags);
#ifdef CONFIG_SMP
        /*
         * Fork balancing, do it here and not earlier because:
         *  - cpus_allowed can change in the fork path
         *  - any previously selected cpu might disappear through hotplug
         */
        set_task_cpu(p, select_task_rq(p, SD_BALANCE_FORK, 0));
#endif

        rq = __task_rq_lock(p);
        activate_task(rq, p, 0);
        p->on_rq = 1;
        trace_sched_wakeup_new(p, true);
        check_preempt_curr(rq, p, WF_FORK);
#ifdef CONFIG_SMP
        if (p->sched_class->task_woken)
                p->sched_class->task_woken(rq, p);
#endif
        task_rq_unlock(rq, p, &flags);
}

我们先不考虑SMP的情况，所以#ifdef中的语句全都忽略。那么前两句语就是先获得task的自旋锁，然后获得task所在的cpu的runqueue，并且获得该runqueue的自旋锁。

这个runqueue是在sched.c中定义的per_cpu的struct。我的理解是每个CPU有一个这样的struct。

activate_task函数会把新创建的进程放进rq中。

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

equeue_task 函数会更新runqueue的时间，以便后面使用。

static void enqueue_task(struct rq *rq, struct task_struct *p, int flags)
{
        update_rq_clock(rq);                                                                                                                                                               
        sched_info_queued(p);
        p->sched_class->enqueue_task(rq, p, flags);
}

/*
 * Enqueue an entity into the rb-tree:
 */
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:
         */
        while (*link) {
                parent = *link;
                entry = rb_entry(parent, struct sched_entity, run_node);
                /*
                 * We dont care about collisions. Nodes with
                 * the same key stay together.
                 */
                if (entity_before(se, entry)) {
                        link = &parent->rb_left;
                } else {
                        link = &parent->rb_right;
                        leftmost = 0;
                }
        }

        /*
         * Maintain a cache of leftmost tree entries (it is frequently
         * used):
         */
        if (leftmost)                                                                                                                                                                      
                cfs_rq->rb_leftmost = &se->run_node;

        rb_link_node(&se->run_node, parent, link);
        rb_insert_color(&se->run_node, &cfs_rq->tasks_timeline);
}

（未完待续）