本文共 7337 字,大约阅读时间需要 24 分钟。
当CPU中没有rt任务时,那么从cfs队列中挑选合适的进程以待切换进CPU,因为是cfs调度类,所以最终调度的函数是pick_next_task_fair:
来看一下pick_next_entity:
- static struct task_struct *pick_next_task_fair(struct rq *rq)
- {
- struct task_struct *p;
- struct cfs_rq *cfs_rq = &rq->cfs;
- struct sched_entity *se;
- if (!cfs_rq->nr_running)
- return NULL;
- do {
- se = pick_next_entity(cfs_rq); //挑选下一个调度实体,详解见下文
- set_next_entity(cfs_rq, se); //
- cfs_rq = group_cfs_rq(se);
- } while (cfs_rq); <span style="color:#FF0000;">//如果被调度的进程仍属于当前组,那么选取下一个可能被调度的任务,以保证组间调度的公平性???</span>
- p = task_of(se);
- hrtick_start_fair(rq, p);
- return p;
- }
- /*
- * Pick the next process, keeping these things in mind, in this order:
- * 1) keep things fair between processes/task groups 1. 首先要确保任务组之间的公平,这也是设置组的原因之一;
- * 2) pick the "next" process, since someone really wants that to run 2. 其次,挑选下一个合适的(优先级比较高的)进程,因为它确实需要马上运行;
- * 3) pick the "last" process, for cache locality 3. 如果没有找到条件2中的进程,那么为了保持良好的局部性,则选中上一次执行的进程;
- * 4) do not run the "skip" process, if something else is available 4. 只要有任务存在,就不要让CPU空转,也就是让CPU运行idle进程。
- */
- static struct sched_entity *pick_next_entity(struct cfs_rq *cfs_rq)
- {
- struct sched_entity *se = __pick_first_entity(cfs_rq); //摘取红黑树最左边的进程
- struct sched_entity *left = se;
- /*
- * Avoid running the skip buddy, if running something else can
- * be done without getting too unfair.
- */
- if (cfs_rq->skip == se) { //如果是被取到的进程自动放弃运行权利
- /*
- *cfs_rq队列中的*skip指向暂时不需要被调度执行的进程,这样的进程一般通过sched_yield()
- *(在CFS中是通过yield_task_fair)放弃执行权的,同时在sched_yield设置skip之前,总是将上一个被设置为skip的进程清除掉,以防止放弃
- *运行权利的进程永远得不到调度。
- */
- struct sched_entity *second = __pick_next_entity(se); //摘取红黑树上第二左的进程节点
- if (second && wakeup_preempt_entity(second, left) < 1) //left应该抢占second么?这个函数的具体实现会在下文详述。
- se = second; //left不会抢占second,则se = second.
- }
- /*
- * Prefer last buddy, try to return the CPU to a preempted task.
- */
- if (cfs_rq->last && wakeup_preempt_entity(cfs_rq->last, left) < 1)
- //如果上一次执行的进程尚在cfs_rq队列中,并且left不能抢占它,这里我们应该能够想到为什么内核线程的active_mm要借用
- //上一个进程的active_mm。这样的话上一个activ_mm就不用从tlb中清洗掉,而下一次调度的时候有可能重新调度到该进程,增加了tlb的命中率。
- se = cfs_rq->last;
- /*
- * Someone really wants this to run. If it's not unfair, run it.
- */
- if (cfs_rq->next && wakeup_preempt_entity(cfs_rq->next, left) < 1)//如果cfs_rq中指向下一个即将被调度进来的进程的指针不为空,并且left不能抢占它
- se = cfs_rq->next;
- clear_buddies(cfs_rq, se); //清空last, next, skip指针
- return se;
- }
我们首先要关注的是 pick_next_entity中调用的第一个函数__pick_first_entity:
- static struct sched_entity *__pick_first_entity(struct cfs_rq *cfs_rq)
- {
- struct rb_node *left = cfs_rq->rb_leftmost; //挑选cfs队列红黑树中最左的元素
- if (!left)
- return NULL;
- return rb_entry(left, struct sched_entity, run_node);
- }
现在,有必要对CFS调度机制有一个深入的了解了。推荐参考网站:http://blog.csdn.net/peimichael/article/details/5218335或者《独辟蹊径》一书。
接着,来看一下在pick_next_entity中被反复用到的一个函数:
- /*
- * Should 'se' preempt 'curr'.
- *
- * |s1
- * |s2
- * |s3
- * g
- * |<--->|c
- *
- * w(c, s1) = -1
- * w(c, s2) = 0
- * w(c, s3) = 1
- *
- */
- static int
- wakeup_preempt_entity(struct sched_entity *curr, struct sched_entity *se)
- {
- s64 gran, vdiff = curr->vruntime - se->vruntime; //curr和se之间虚拟时钟的差别
- if (vdiff <= 0) //如果curr的虚拟时钟小于se的虚拟时钟
- return -1; //则se不能抢占curr
- gran = wakeup_gran(curr, se); //计算粒度,详述见下文
- if (vdiff > gran) //如果vdiff大于粒度,则允许se抢占curr
- return 1;
- return 0;
- }
这个函数返回-1表示新进程vruntime大于当前进程,当然不能抢占,返回0表示虽然新进程vruntime比当前进程小,但是没有小到调度粒度,一般也不能抢占。返回1表示新进程vruntime比当前进程小的超过了调度粒度,可以抢占。 调度粒度是什么概念呢?进程调度的时候每次都简单选择vruntime最小的进程调度,其实也不完全是这样。 假设进程A和B的vruntime很接近,那么A先运行了一个tick,vruntime比B大了,B又运行一个tick,vruntime又比A大了,又切换到A,这样就会在AB间频繁切换,对性能影响很大,因此如果当前进程的时间没有用完,就只有当有进程的vruntime比当前进程小超过调度粒度时,才能进行进程切换。 函数上面注释中那个图就是这个意思,我们看下: 横坐标表示vruntime,s1 s2 s3分别表示新进程,c表示当前进程,g表示调度粒度。 s3肯定能抢占c;而s1不可能抢占c。 s2虽然vruntime比c小,但是在调度粒度之内,能否抢占要看情况,像现在这种状况就不能抢占。
(摘自:http://blog.csdn.net/peimichael/article/details/5218335)
在选中了下一个将被调度执行的进程之后,回到pick_next_task_fair中,执行set_next_entity():
- static void
- set_next_entity(struct cfs_rq *cfs_rq, struct sched_entity *se)
- {
- /* 'current' is not kept within the tree. */
- if (se->on_rq) { //如果se尚在rq队列上
- /*
- * Any task has to be enqueued before it get to execute on
- * a CPU. So account for the time it spent waiting on the
- * runqueue.
- */
- update_stats_wait_end(cfs_rq, se);
- __dequeue_entity(cfs_rq, se); //将se从rq队列中删除
- /*
- *static void __dequeue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se)
- *{
- * if (cfs_rq->rb_leftmost == &se->run_node) {
- * struct rb_node *next_node;
- * next_node = rb_next(&se->run_node);
- * cfs_rq->rb_leftmost = next_node; //挑选下一个leftmost
- * }
- * rb_erase(&se->run_node, &cfs_rq->tasks_timeline); //调整rb树
- *}
- */
- }
- update_stats_curr_start(cfs_rq, se); //We are picking a new current task.更新sched_entity中的exec_start字段为当前clock_task.
- cfs_rq->curr = se; //将se设置为curr进程
- #ifdef CONFIG_SCHEDSTATS
- /*
- * Track our maximum slice length, if the CPU's load is at
- * least twice that of our own weight (i.e. dont track it
- * when there are only lesser-weight tasks around):
- */
- if (rq_of(cfs_rq)->load.weight >= 2*se->load.weight) {
- se->statistics.slice_max = max(se->statistics.slice_max,
- se->sum_exec_runtime - se->prev_sum_exec_runtime);
- }
- #endif
- se->prev_sum_exec_runtime = se->sum_exec_runtime; //更新task上一次投入运行的从时间。
- }
以上,我们讨论了公平调度的情况,回到pick_next_task中,如果rq队列中进程的数量不等于CFS中进程的数量,那么说明有其它类型的任务需要被优先调度。
对于for_each_class:
我们可以得到这样的结论,不同类型的任务被调度的顺序是:
- #define sched_class_highest (&stop_sched_class)
- #define for_each_class(class) \
- for (class = sched_class_highest; class; class = class->next)
stop_sched_class ----> rt_sched_class ----> fair_sched_class ----> idle_sched_class ----> NULL
首先看一下stop_sched_class选取下一个进程的过程:
然后,看rt_sched_class挑选下一个进程的过程:
- static struct task_struct *pick_next_task_stop(struct rq *rq)
- {
- struct task_struct *stop = rq->stop; //直接将rq队列中的stop指向的进程作为即将被调度进来的进程。
- if (stop && stop->on_rq)
- return stop;
- return NULL;
- }
其中的关键操作自然是_pick_next_task_rt:
- static struct task_struct *pick_next_task_rt(struct rq *rq)
- {
- struct task_struct *p = _pick_next_task_rt(rq);
- /* The running task is never eligible for pushing */
- if (p)
- dequeue_pushable_task(rq, p);
- #ifdef CONFIG_SMP
- /*
- * We detect this state here so that we can avoid taking the RQ
- * lock again later if there is no need to push
- */
- rq->post_schedule = has_pushable_tasks(rq);
- #endif
- return p;
- }
- static struct sched_rt_entity *pick_next_rt_entity(struct rq *rq,
- struct rt_rq *rt_rq)
- {
- struct rt_prio_array *array = &rt_rq->active;
- struct sched_rt_entity *next = NULL;
- struct list_head *queue;
- int idx;
- idx = sched_find_first_bit(array->bitmap); //找到active->bitmap中第一个置位的比特位,即高优先级。
- BUG_ON(idx >= MAX_RT_PRIO);
- queue = array->queue + idx;
- next = list_entry(queue->next, struct sched_rt_entity, run_list);
- return next;
- }
实时进程的调度用的是和CFS不同的调度方法,不过想比于CFS,它更简单。详细的可以参看《深入Linux内核架构》P117.
到目前为止,我们终于将下一个要执行的进程挑选出来了!