Linux调度器

调度器

调度器的实现基于两种调度:周期调度，主调度，这些基于可运行进程的优先级来获取cpu时间，这也就是优先级调度。周期性调度主要调用scheduler_tick方法:

void scheduler_tick()
{
    int cpu = smp_processor_id();
    struct rq *rq = cpu_rq(cpu);
    struct task_struct *curr = rq->curr;
    u64 next_tick = rq->tick_timestamp + TICK_NSEC;

    spin_lock(&rq->lock);
    __update_rq_clock(rq);//更新运行队列时钟
    if(unlikely(rq->clock < next_tick))
        rq->clock = next_tick;
    rq->tick_timestamp = rq->clock;
    update_cpu_load(rq);//更新cpu_load[]数组x`
    if(curr != rq->idle)
        curr->sched_class->task_tick(rq,curr);//调用所在调度类的方法
    spin_unlock(&rq->lock);
#ifdef CONFIG_SMP
    rq->idle_at_tick = idle_cpu(cpu);
    trigger_load_balance(rq,cpu);
#endif
}

而在每个具体调度类中进行时间片等判断,进行设置need_resched位,为schedule()埋下伏笔

在CFS中,调用关系如下:task_tick-->task_tick_fair-->entity_task:

static void task_tick_fair(struct rq *rq,struct task_struct *curr)
{
    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);
    }
}
static void entity_tick(struct cfs_rq *cfs_rq,struct sched_entity *curr)
{
    update_curr(cfs_rq);//更新队列统计参数
    if(cfs_rq->nr_running >1 || !sched_feat(WAKEUP_PREEMPT))
        check_preempt_tick(cfs_rq,curr);
}
static void check_preempt_tick(struct cfs_rq *cfs_rq,struct sched_entity *curr)
{
    unsigned long ideal_runtime,delta_exec;
    ideal_runtime = sched_slice(cfs_rq,curr);//按照权重计算出该进程的运行时间
    delta_exec = curr->sum_exec_runtime – curr->prev_sum_exec_runtime;
    if(delta_exec > ideal_runtime)
        //如果超过应当运行的时间,进行调度,也就是设置TIF_NEED_RESCHED
        resched_task(rq_of(cfs_rq)->curr);
}
static void update_curr(struct cfs_rq *cfs_rq)
{
    struct sched_entity *curr = cfs_rq->curr;
    u64 now = rq_of(cfs_rq)->clock;
    unsigned long delta_exec;
    if(unlikely(!curr))        return;
    //计算出当前进程运行的时间
    delta_exec = (unsigned long)(now – curr->exec_start);
    __update_curr(cfs_rq,curr,delta_exec);
    curr->exec_start = now;
    ….....
}
static inline void __update_curr(struct cfs_rq *cfs_rq,struct sched_entity *curr,
        unsigned long delta_exec)
{
    unsigned long delta_exec_weighted;
    u64 vruntime;
    //设置最长运行时间
    schedstat_set(curr->exec_max,max((u64)delta_exec,curr->exec_max));
    curr->sum_exec_runtime += delta_exec;
    //更新该运行队列的运行时间
    schedstat_add(cfs_rq,exec_clock,delta_exec);
    delta_exc_weighted = delta_exec;
    if(unlikely(curr->load.weight != NICE_0_LOAD)) {
        delta_exec_weighted = calc_delta_fair(delta_exec_weighted,
            &curr->load);
    }
    //更新该进程,根据权重(通过优先级获得),获取该进程所得运行时间
    curr->vruntime += delta_exec_weighted;
    if(first_fair(cfs_rq)) {
        //与红黑树最左端的运行时间进行比较,得到最小的
        vruntime = min_vruntime(curr->vruntime,
            __pick_next_entity(cfs_rq)->vruntime);
    }else  vruntime = curr->vruntime;
    //维护其单调递增特征,并非该运行队列中的最小应该运行的时间
    cfs_rq->min_vruntime = max_vruntime(cfs_rq->min_vruntime,vruntime);
}

上面的代码可以归结以下两点:

1.当当前进程处于运行状态时,运行时间会变大,它就会向红黑树的右端移动

2.当处于睡眠状态的进程运行时间不变,由于min_vruntime单调递增,这样它就会加快左端移动速度

而实时进程的定时调度如下:

static void task_tick_rt(struct rq *rq,struct task_struct *p)
{
    update_curr_rt(rq);
    if(p->policy != SCHED_RR)    return;//SCHED_FIFO没有时间片
    if(--p->time_slice)    return;
    p->time_slice = DEF_TIMESLICE;//时间片为0,重新调度
    if(p->run_list.prev != p->run_list.next) {//如果运行队列里面还有其他进程
        requeue_task_rt(rq,p);//将该进程放到链表末尾
        set_tsk_need_resched(p);//设置可调度标记
    }
}

主调度器

当从系统调用返回时，调度器就会检查当前进程的TIF_NEED_RESCHED标记，如果设置，则内核调用schedule函数，来替换当前运行的进程，每个潜在调用schedule的函数都有一个__schedule的前缀，包括schedule函数本身.

asmlinkage void __sched  schedule(void)
{
    struct task_struct *prev,*next;
    long *switch_count;
    struct rq *rq;
    int cpu;
need_resched:
    preempt_dissable();
    cpu = smp_processor_id();//获取当前cpu
    rq = cpu_rq(cpu);//得到当前cpu的运行队列
    rcu_qsctr_inc(cpu);
    prev = rq->curr;//prev设置为当前运行进程
    switch_count = &prev->nivcsw;
    release_kernel_lock(prev);
need_resched_nonpremptible:
    schedule_debug(prev);
    local_irq_disable();
    __update_rq_clock(rq);//更新当前运行队列时钟
    spin_lock(&rq->lock);
    clear_tsk_need_resched(prev);//清除抢占标志
    //当前进程处于非运行状态
    if(prev->state && !(preempt_count() & PREEMPT_ACTIVE)) {
        //如果有未处理的信号，则调度为运行状态
        if(unlikely((prev->state &TASK_INTERRUPTIBLE) \
            && unlikely(signal_pending(prev))))  {
            prev->state = TASK_RUNNING;
        }else {
            //否则被抢占
            deactivate_task(rq,prev,1);
        }
        switch_count = &prev->nvcsw;
    }
    //如果当前没有可运行的进程数目，则进行负载均衡
    if(unlikely(!rq->nr_running))
        idle_balance(cpu,rq);
    //更新统计信息
    prev->sched_class->put_prev_task(rq,prev);
    //选择下一个可运行的进程
    next = pick_next_task(rq,prev);
    //开始进行切换
    sched_info_switch(prev,next);
    //如果不是同一个进程就进行硬件级别上的进程切换
    if(unlikely(prev != next)) {
        rq->nr_switches ++;
        rq->curr = next;
        ++ *switch_count;
        context_switch(rq,prev,next);//这个需要进行详细分析
    } else  spin_unlock_irq(&rq->lock);
    if(unlikely(reacquire_kernel_lock(current) < 0)) {
        cpu = smp_processor_id();
        rq = cpu_rq(cpu);
        goto need_resched_nonpremptible;//重新调度
    }
    preempt_enable_no_resched();
    //如果当前进程的重新调度被设置,则再次进行调度
    if(unlikely(test_thread_flag(TIF_NEED_RESCHED)))
        goto need_sched;
}

当cfs 调用put_prev_task时，具体代码如下:

static void put_prev_task_fair(struct rq *rq,struct task_struct *prev)
{
    struct sched_entity *se = &prev->se;
    struct cfs_rq *cfs_rq;
    for_each_sched_entity(se){
        cfs_rq = cfs_rq_of(se);
        put_prev_entity(cfs_rq,se);
    }
}
static void put_prev_entity(struct cfs_rq *cfs_rq,struct sched_entity *prev)
{
    if(prev->on_rq)
        update_curr(cfs_rq);
    check_spread(cfs_rq,prev);
    if(prev->on_rq) {
        update_stats_wait_start(cfs_rq,prev);
        __enqueue_entity(cfs_rq,prev);//将会重新寻找一个新的最左节点
    }
    cfs_rq->curr = NULL;
}
static inline struct task_struct *
pick_next_task(struct rq *rq,struct task_struct *prev)
{
    const struct sched_class *class;
    struct task_struct *p;
    if(likely(rq->nr_running == rq->cfs.nr_running)) {
        //这里的fair_sched_class来自sched_fair.c中的变量，而且还是静态变量!!(因为其包含了sched_fair.c的头文件)
        p = fair_sched_class.pick_next_task(rq);
        if(likely(p))    return p;
    }
    class = sched_class_highest;//直接赋值为实时调度
    for(;;) {
        //直接从运行位图中找到第一位
        p = class->pick_next_task(rq);
        if(p)    return p;
        class = class->next;
    }
}
static struct task_struct *pick_next_task_fair(struct rq *rq)
{
    struct cfs_rq *cfs_rq = &rq->cfs;
    struct sched_entity *se;

    if(unlikely(!cfs_rq ->nr_running))
        return NULL;
    do {
        //直接返回的是保存在红黑树中的最左端
        se = pick_next_entity(cfs_rq);
        //默认只有一条队列，只循环一次
        cfs_rq = group_cfs_rq(se);
    }while(cfs_rq);
    return task_of(se);
}

现在的问题是,cfs中的调度何时进入红黑树?每task_tick调用一次,时间将会发生改变,这样红黑树是否需要进行调整?

1.当任务被激活时,也就是进入运行队列之后,就会插入红黑树,调用方法为:activate_task,当任务从运行队列上删除时(从运行状态改为不可运行状态),就会删除该节点,调用方法为:deactivate_task.

在每一次周期性调度,都会重新计算最左边节点:

static void __enqueue_entity(struct cfs_rq *cfs_rq,struct sched_entity *se)
{
    struct rb_node **link = &cfs_rq->task_timeline.rb_node;
    struct rb_node *parent = NULL;
    struct sched_entity *entry;
    s64 key = entity_key(cfs_rq,se);
    int leftmost = 1;

    while(*link) {
        parent = *link;
        entry = rb_entry(parent,struct sched_entity,run_node);
        if(key < entity_key(cfs_rq,entry)) {
            link = &parent->rb_left;
        } else {
            link = &parent->rb_right;
            leftmost = 0;
        }
    }
    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);
}

看来选择红黑树的最左端节点通过函数entity_key来作为key实现:

static inline s64 entity_key(struct cfs_rq *cfs_rq,struct sched_entity *se)
{
    //该进程应该运行的时间 – 运行队列中最少运行时间,也就是说已运行时间越少的进程会优先运行
    //cfs_rq->min_vruntime在每一次task_tick时,都会被计算一次
    return se->vrumtime – cfs_rq->min_vruntime;
}

参考资料:

1.linux-2.4.26.3内核源码

2.professional linux kernel architecture