Chinaunix首页 | 论坛 | 博客
  • 博客访问: 448761
  • 博文数量: 72
  • 博客积分: 1851
  • 博客等级: 上尉
  • 技术积分: 1464
  • 用 户 组: 普通用户
  • 注册时间: 2010-09-16 17:50
文章分类

全部博文(72)

文章存档

2013年(1)

2012年(17)

2011年(51)

2010年(3)

分类: LINUX

2011-09-14 20:09:08

调度器

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

  1. void scheduler_tick()
  2. {
  3.     int cpu = smp_processor_id();
  4.     struct rq *rq = cpu_rq(cpu);
  5.     struct task_struct *curr = rq->curr;
  6.     u64 next_tick = rq->tick_timestamp + TICK_NSEC;
  7.     
  8.     spin_lock(&rq->lock);
  9.     __update_rq_clock(rq);//更新运行队列时钟
  10.     if(unlikely(rq->clock < next_tick))
  11.         rq->clock = next_tick;
  12.     rq->tick_timestamp = rq->clock;
  13.     update_cpu_load(rq);//更新cpu_load[]数组x`
  14.     if(curr != rq->idle)
  15.         curr->sched_class->task_tick(rq,curr);//调用所在调度类的方法
  16.     spin_unlock(&rq->lock);
  17. #ifdef CONFIG_SMP
  18.     rq->idle_at_tick = idle_cpu(cpu);
  19.     trigger_load_balance(rq,cpu);
  20. #endif
  21. }

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

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

  1. static void task_tick_fair(struct rq *rq,struct task_struct *curr)
  2. {
  3.     struct cfs_rq *cfs_rq;
  4.     struct sched_entity *se = &curr->se;
  5.     for_each_sched_entity(se) {//默认只有一条运行队列,如果有按组调度的话,就会有很多条运行队列了
  6.         cfs_rq = cfs_rq_of(se);
  7.         entity_tick(cfs_rq,se);
  8.     }
  9. }
  10. static void entity_tick(struct cfs_rq *cfs_rq,struct sched_entity *curr)
  11. {    
  12.     update_curr(cfs_rq);//更新队列统计参数
  13.     if(cfs_rq->nr_running >1 || !sched_feat(WAKEUP_PREEMPT))
  14.         check_preempt_tick(cfs_rq,curr);
  15. }
  16. static void check_preempt_tick(struct cfs_rq *cfs_rq,struct sched_entity *curr)
  17. {
  18.     unsigned long ideal_runtime,delta_exec;
  19.     ideal_runtime = sched_slice(cfs_rq,curr);//按照权重计算出该进程的运行时间
  20.     delta_exec = curr->sum_exec_runtime – curr->prev_sum_exec_runtime;
  21.     if(delta_exec > ideal_runtime)
  22.         //如果超过应当运行的时间,进行调度,也就是设置TIF_NEED_RESCHED
  23.         resched_task(rq_of(cfs_rq)->curr);
  24. }
  25. static void update_curr(struct cfs_rq *cfs_rq)
  26. {
  27.     struct sched_entity *curr = cfs_rq->curr;
  28.     u64 now = rq_of(cfs_rq)->clock;
  29.     unsigned long delta_exec;
  30.     if(unlikely(!curr))        return;
  31.     //计算出当前进程运行的时间
  32.     delta_exec = (unsigned long)(now – curr->exec_start);
  33.     __update_curr(cfs_rq,curr,delta_exec);
  34.     curr->exec_start = now;
  35.     ….....
  36. }
  37. static inline void __update_curr(struct cfs_rq *cfs_rq,struct sched_entity *curr,
  38.         unsigned long delta_exec)
  39. {
  40.     unsigned long delta_exec_weighted;
  41.     u64 vruntime;
  42.     //设置最长运行时间
  43.     schedstat_set(curr->exec_max,max((u64)delta_exec,curr->exec_max));
  44.     curr->sum_exec_runtime += delta_exec;
  45.     //更新该运行队列的运行时间
  46.     schedstat_add(cfs_rq,exec_clock,delta_exec);
  47.     delta_exc_weighted = delta_exec;
  48.     if(unlikely(curr->load.weight != NICE_0_LOAD)) {
  49.         delta_exec_weighted = calc_delta_fair(delta_exec_weighted,
  50.             &curr->load);
  51.     }
  52.     //更新该进程,根据权重(通过优先级获得),获取该进程所得运行时间
  53.     curr->vruntime += delta_exec_weighted;
  54.     if(first_fair(cfs_rq)) {
  55.         //与红黑树最左端的运行时间进行比较,得到最小的
  56.         vruntime = min_vruntime(curr->vruntime,
  57.             __pick_next_entity(cfs_rq)->vruntime);
  58.     }else vruntime = curr->vruntime;
  59.     //维护其单调递增特征,并非该运行队列中的最小应该运行的时间
  60.     cfs_rq->min_vruntime = max_vruntime(cfs_rq->min_vruntime,vruntime);
  61. }

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

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

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

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

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

主调度器

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

  1. asmlinkage void __sched schedule(void)
  2. {
  3.     struct task_struct *prev,*next;
  4.     long *switch_count;
  5.     struct rq *rq;
  6.     int cpu;
  7. need_resched:
  8.     preempt_dissable();
  9.     cpu = smp_processor_id();//获取当前cpu
  10.     rq = cpu_rq(cpu);//得到当前cpu的运行队列
  11.     rcu_qsctr_inc(cpu);
  12.     prev = rq->curr;//prev设置为当前运行进程
  13.     switch_count = &prev->nivcsw;
  14.     release_kernel_lock(prev);
  15. need_resched_nonpremptible:
  16.     schedule_debug(prev);
  17.     local_irq_disable();
  18.     __update_rq_clock(rq);//更新当前运行队列时钟
  19.     spin_lock(&rq->lock);
  20.     clear_tsk_need_resched(prev);//清除抢占标志
  21.     //当前进程处于非运行状态
  22.     if(prev->state && !(preempt_count() & PREEMPT_ACTIVE)) {
  23.         //如果有未处理的信号,则调度为运行状态
  24.         if(unlikely((prev->state &TASK_INTERRUPTIBLE) \
  25.             && unlikely(signal_pending(prev)))) {
  26.             prev->state = TASK_RUNNING;
  27.         }else {
  28.             //否则被抢占
  29.             deactivate_task(rq,prev,1);
  30.         }
  31.         switch_count = &prev->nvcsw;
  32.     }
  33.     //如果当前没有可运行的进程数目,则进行负载均衡
  34.     if(unlikely(!rq->nr_running))
  35.         idle_balance(cpu,rq);
  36.     //更新统计信息
  37.     prev->sched_class->put_prev_task(rq,prev);
  38.     //选择下一个可运行的进程
  39.     next = pick_next_task(rq,prev);
  40.     //开始进行切换
  41.     sched_info_switch(prev,next);
  42.     //如果不是同一个进程就进行硬件级别上的进程切换
  43.     if(unlikely(prev != next)) {
  44.         rq->nr_switches ++;
  45.         rq->curr = next;
  46.         ++ *switch_count;
  47.         context_switch(rq,prev,next);//这个需要进行详细分析
  48.     } else spin_unlock_irq(&rq->lock);
  49.     if(unlikely(reacquire_kernel_lock(current) < 0)) {
  50.         cpu = smp_processor_id();
  51.         rq = cpu_rq(cpu);
  52.         goto need_resched_nonpremptible;//重新调度
  53.     }
  54.     preempt_enable_no_resched();
  55.     //如果当前进程的重新调度被设置,则再次进行调度
  56.     if(unlikely(test_thread_flag(TIF_NEED_RESCHED)))
  57.         goto need_sched;    
  58. }

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

  1. static void put_prev_task_fair(struct rq *rq,struct task_struct *prev)
  2. {
  3.     struct sched_entity *se = &prev->se;
  4.     struct cfs_rq *cfs_rq;
  5.     for_each_sched_entity(se){
  6.         cfs_rq = cfs_rq_of(se);
  7.         put_prev_entity(cfs_rq,se);
  8.     }
  9. }
  10. static void put_prev_entity(struct cfs_rq *cfs_rq,struct sched_entity *prev)
  11. {
  12.     if(prev->on_rq)
  13.         update_curr(cfs_rq);
  14.     check_spread(cfs_rq,prev);
  15.     if(prev->on_rq) {
  16.         update_stats_wait_start(cfs_rq,prev);
  17.         __enqueue_entity(cfs_rq,prev);//将会重新寻找一个新的最左节点
  18.     }
  19.     cfs_rq->curr = NULL;
  20. }
  21. static inline struct task_struct *
  22. pick_next_task(struct rq *rq,struct task_struct *prev)
  23. {
  24.     const struct sched_class *class;
  25.     struct task_struct *p;
  26.     if(likely(rq->nr_running == rq->cfs.nr_running)) {
  27.         //这里的fair_sched_class来自sched_fair.c中的变量,而且还是静态变量!!(因为其包含了sched_fair.c的头文件)
  28.         p = fair_sched_class.pick_next_task(rq);
  29.         if(likely(p))    return p;
  30.     }
  31.     class = sched_class_highest;//直接赋值为实时调度
  32.     for(;;) {
  33.         //直接从运行位图中找到第一位
  34.         p = class->pick_next_task(rq);
  35.         if(p)    return p;
  36.         class = class->next;
  37.     }
  38. }
  39. static struct task_struct *pick_next_task_fair(struct rq *rq)
  40. {
  41.     struct cfs_rq *cfs_rq = &rq->cfs;
  42.     struct sched_entity *se;
  43.     
  44.     if(unlikely(!cfs_rq ->nr_running))
  45.         return NULL;
  46.     do {
  47.         //直接返回的是保存在红黑树中的最左端
  48.         se = pick_next_entity(cfs_rq);
  49.         //默认只有一条队列,只循环一次
  50.         cfs_rq = group_cfs_rq(se);
  51.     }while(cfs_rq);
  52.     return task_of(se);
  53. }

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

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

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

  1. static void __enqueue_entity(struct cfs_rq *cfs_rq,struct sched_entity *se)
  2. {    
  3.     struct rb_node **link = &cfs_rq->task_timeline.rb_node;
  4.     struct rb_node *parent = NULL;
  5.     struct sched_entity *entry;
  6.     s64 key = entity_key(cfs_rq,se);
  7.     int leftmost = 1;
  8.     
  9.     while(*link) {
  10.         parent = *link;
  11.         entry = rb_entry(parent,struct sched_entity,run_node);
  12.         if(key < entity_key(cfs_rq,entry)) {
  13.             link = &parent->rb_left;    
  14.         } else {
  15.             link = &parent->rb_right;
  16.             leftmost = 0;
  17.         }
  18.     }
  19.     if(leftmost)    
  20.         cfs_rq->rb_leftmost = &se->run_node;
  21.     rb_link_node(&se->run_node,parent,link);
  22.     rb_insert_color(&se->run_node,&cfs_rq->tasks_timeline);
  23. }

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

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

参考资料:

1.linux-2.4.26.3内核源码

2.professional linux kernel architecture

阅读(1545) | 评论(0) | 转发(0) |
0

上一篇:动态规划小结

下一篇:简单的平衡树-treaps

给主人留下些什么吧!~~