运行队列函数入队操作分析enqueue_task_fair

在linux2.6.23版本以后，内核在进程调度方面引入了一个新的算法，即完全公平调度程序(CFS),有关CFS的详细介绍，请参见本博客：

http://blog.chinaunix.net/u2/73521/showart.php?id=2020147

下面将对enqueue_task_fair函数进行分析，这个函数的功能是将指定进程加入到运行队列中.
/*
    enqueue_task函数在nr_running增加之前被调用.在这个函数中更新公平调度状态值，之后
    将对应的进程放置到rbtree中
*/
static void enqueue_task_fair(struct rq *rq,struct task_struct *p,int wakeup)
{
    struct cfs_rq *cfs_rq;
    struct sched_entity *se = &p->se;
   
    for_each_sched_entity(se) {
        if(se->on_rq)
            break;
        /*
            通过sched_entity来获得完全公平运行队列cfs_rq.
        */
        cfs_rq = cfs_rq_of(se);
        enqueue_entity(cfs_rq,se,wakeup);
    }
}

static void enqueue_entity(struct cfs_rq *cfs_rq,struct sched_entity &se,int wakeup)
{
    /*
        更新公平时钟
    */
    update_curr(cfs_rq);
   
    if(wakeup)
        enqueue_sleeper(cfs_rq,se);
    /*
        更新将要插入cfs_rq中的进程的转台值
    */
    update_stats_enqueue(cfs_rq,se);
    __enqueue_entity(cfs_rq,se);
}

static inline void__enqueue_entity(struct cfs_rq *cfs_rq,struct sched_entoty *se)
{
    struct rb_node **link = &cfs_rq->tasks_timeline.rb_node;
    struct rb_node *parent = NULL;
    struct sched_entity *entry;
    s64 key = se->fair_key;
    int leftmost = 1;
    /*
        下面的循环是对rb_tree插入节点的操作
    */
    while(*link) {
        parent = *link;
        entry = rb_entry(parent , struct sched_entity,run_node);
       
        if(key - entry->fair_key < 0) {
            link = &parent->rb_left;
        } else {
            link = &parent->rb_right;
            leftmost = 0;
        }
    }
    /*
        此判断语句是用来对rb_tree进行直接插入操作的,因为如果树的左子树为空，就直接
        插入就可以了
    */
    if(leftmost) {
        cfs_rq->rb_leftmost = &se->run_node;
    }
   
    rb_link_node(&se->run_node,parent,link);
    /*
        static inline void rb_link_node(struct rb_node *node,
                        struct rb_node *parent,
                        struct rb_node **rb_link)
        {
            node->rb_parent_color = (unsigned long)parent;
            node->rb_left = node->rb_right = NULL;
            *rb_link = node;
        }
    */
    /*
        rb_insert_color函数使用来对整棵rb_tree的颜色进行更新的
        这个函数涉及到了一个具体的算法，需要加以研究
    */
    rb_insert_color(&se->run_node,&cfs_rq->tasks_timeline);
    update_load_add(&cfs_rq->load,se->load.weight);
    /*
        统计rb_tree中运行进程的数量，即自增1
    */
    cfs_rq->nr_running ++;
    /*
        使当前进程对应的sched_entity的nr_rq置1，表明当前操作的进程已处于运行状态
    */
    se->on_rq = 1;
}