内核源码分析之进程调度机制,进程管理之CFS调度器

  权重信息即为调度实体的权重,为了计算方便,内核约定nice值为0的权重值为1024,其他的nice值对应相应的权重值可以通过查表的方式来获取,表即为prio_to_weight。

 1 void scheduler_tick(void)
 2 {
 3     int cpu = smp_processor_id();
 4     struct rq *rq = cpu_rq(cpu);
 5     struct task_struct *curr = rq->curr;
 6 
 7     sched_clock_tick();
 8 
 9     raw_spin_lock(&rq->lock);
10     update_rq_clock(rq);
11     curr->sched_class->task_tick(rq, curr, 0);
12     update_cpu_load_active(rq);
13     raw_spin_unlock(&rq->lock);
14 
15     perf_event_task_tick();
16 
17 #ifdef CONFIG_SMP
18     rq->idle_balance = idle_cpu(cpu);
19     trigger_load_balance(rq);
20 #endif
21     rq_last_tick_reset(rq);
22 }

《奔跑吧linux内核》3.2笔记,不足之处还望大家批评指正

struct cfs_rq

问题四:CFS调度器中的vruntime是如何计算的?

2.调度实体(include/linux/sched.h)

  O(N)调度器发布与1992年,从就绪队列中比较所有进程的优先级,然后选择一个最高优先级的进程作为下一个调度进程。每一个进程有一个固定时间片,当进程时间片使用完之后,调度器会选择下一个调度进程,当所有进程都运行一遍后再重新分配时间片。这个调度器选择下一个调度进程前需要遍历整个就绪队列,花费O(N)时间。

www.350.vip 1www.350.vip 2

  进程大致可以分为交互式进程批处理进程实时进程。对于不同的进程采用不同的调度策略,目前Linux内核中默认实现了4种调度策略,分别是deadline、realtime、CFS和idle,分别适用struct
sched_class来定义调度类。

 1 struct sched_class {
 2     const struct sched_class *next;
 3 
 4     void (*enqueue_task) (struct rq *rq, struct task_struct *p, int flags);
 5     void (*dequeue_task) (struct rq *rq, struct task_struct *p, int flags);
 6     void (*yield_task) (struct rq *rq);
 7     bool (*yield_to_task) (struct rq *rq, struct task_struct *p, bool preempt);
 8 
 9     void (*check_preempt_curr) (struct rq *rq, struct task_struct *p, int flags);
10 
11     /*
12      * It is the responsibility of the pick_next_task() method that will
13      * return the next task to call put_prev_task() on the @prev task or
14      * something equivalent.
15      *
16      * May return RETRY_TASK when it finds a higher prio class has runnable
17      * tasks.
18      */
19     struct task_struct * (*pick_next_task) (struct rq *rq,
20                         struct task_struct *prev);
21     void (*put_prev_task) (struct rq *rq, struct task_struct *p);
22 
23 #ifdef CONFIG_SMP
24     int  (*select_task_rq)(struct task_struct *p, int task_cpu, int sd_flag, int flags);
25     void (*migrate_task_rq)(struct task_struct *p, int next_cpu);
26 
27     void (*post_schedule) (struct rq *this_rq);
28     void (*task_waking) (struct task_struct *task);
29     void (*task_woken) (struct rq *this_rq, struct task_struct *task);
30 
31     void (*set_cpus_allowed)(struct task_struct *p,
32                  const struct cpumask *newmask);
33 
34     void (*rq_online)(struct rq *rq);
35     void (*rq_offline)(struct rq *rq);
36 #endif
37 
38     void (*set_curr_task) (struct rq *rq);
39     void (*task_tick) (struct rq *rq, struct task_struct *p, int queued);
40     void (*task_fork) (struct task_struct *p);
41     void (*task_dead) (struct task_struct *p);
42 
43     void (*switched_from) (struct rq *this_rq, struct task_struct *task);
44     void (*switched_to) (struct rq *this_rq, struct task_struct *task);
45     void (*prio_changed) (struct rq *this_rq, struct task_struct *task,
46                  int oldprio);
47 
48     unsigned int (*get_rr_interval) (struct rq *rq,
49                      struct task_struct *task);
50 
51 #ifdef CONFIG_FAIR_GROUP_SCHED
52     void (*task_move_group) (struct task_struct *p, int on_rq);
53 #endif
54 };

  O(1)调度器用于Linux2.6.23内核之前,它为每个CPU维护一组进程优先级队列,每个优先级一个队列,这样在选择下一个进程时,只要查询优先级队列相应的位图即可知道哪个队列中有就绪进程,查询时间常数为O(1)。

进程调度所使用到的数据结构:

  prio_to_wmult表记录的是nice值对应的权重值倒转后的值inv_weight=2^32/weight。

struct rt_rq

  runnable_avg_sum为调度实体的可运行状态下总衰减累加时间。

内核为每一个cpu创建一个进程就绪队列,该队列上的进程均由该cpu执行,代码如下(kernel/sched/core.c)。

  runnable_avg_period记录的是上一次更新时的总周期数(一个周期是1024us),即调度实体在调度器中的总衰减累加时间。

www.350.vip 3www.350.vip 4

  nice值从-20~19,进程默认的nice值为0。这可以理解为40个等级,nice值越高,则优先级越低,反之亦然。(nice每变化1,则相应的进程获得CPU的时间就改变10%)。

只列出了和进程调度有关的成员。第6行三个变量代表了普通进程的三个优先级,第7行的变量代表了实时进程的优先级。关于进程优先级的概念,大家可以看看《深入理解linux内核架构》这本书的进程管理章节。第8-10行就是我们上边提到的那些结构体在进程描述符中的定义。第17行的policy代表了当前进程的调度策略,内核给出了宏定义,它可以在这些宏中取值,关于详细的讲解还是去看《深入理解linux内核架构》这本书的进程管理部分。policy取了什么值,sched_class也应该取相应的调度类指针。

   一个进程等待很长时间之后(过了很多个period),原来的runnable_avg_sum和runable_ave_period值衰减后可能变成0,相当于之前的统计值被清0。

3.调度类(kernel/sched/sched.h)

问题二:请简述进程优先级、nice和权重之间的关系。

定义了一个struct
rq结构体数组,每个数组元素是一个就绪队列,对应一个cpu。下面看下struct rq结构体(kernel/sched/sched.h):

  runnable_avg_yN_sum表为1024*(y+y^2+…+y^n),y为实际衰减因子,n取1~32。(实际衰减因子下图所示)

1.2实时进程的就绪队列struct rt_rq(kernel/sched/sched.h)

建议阅读博文理解linux
cfs调度器

进程调度过程分析:

问题七:CFS调度器对新创建的进程和刚唤醒的进程有何关照?

 1 /* CFS-related fields in a runqueue */
 2 struct cfs_rq {
 3     struct load_weight load;
 4     unsigned int nr_running, h_nr_running;
 5 
 6     u64 exec_clock;
 7     u64 min_vruntime;
 8 #ifndef CONFIG_64BIT
 9     u64 min_vruntime_copy;
10 #endif
11 
12     struct rb_root tasks_timeline;
13     struct rb_node *rb_leftmost;
14 
15     /*
16      * 'curr' points to currently running entity on this cfs_rq.
17      * It is set to NULL otherwise (i.e when none are currently running).
18      */
19     struct sched_entity *curr, *next, *last, *skip;
20 
21 #ifdef    CONFIG_SCHED_DEBUG
22     unsigned int nr_spread_over;
23 #endif
24 
25 #ifdef CONFIG_SMP
26     /*
27      * CFS Load tracking
28      * Under CFS, load is tracked on a per-entity basis and aggregated up.
29      * This allows for the description of both thread and group usage (in
30      * the FAIR_GROUP_SCHED case).
31      */
32     unsigned long runnable_load_avg, blocked_load_avg;
33     atomic64_t decay_counter;
34     u64 last_decay;
35     atomic_long_t removed_load;
36 
37 #ifdef CONFIG_FAIR_GROUP_SCHED
38     /* Required to track per-cpu representation of a task_group */
39     u32 tg_runnable_contrib;
40     unsigned long tg_load_contrib;
41 
42     /*
43      *   h_load = weight * f(tg)
44      *
45      * Where f(tg) is the recursive weight fraction assigned to
46      * this group.
47      */
48     unsigned long h_load;
49     u64 last_h_load_update;
50     struct sched_entity *h_load_next;
51 #endif /* CONFIG_FAIR_GROUP_SCHED */
52 #endif /* CONFIG_SMP */
53 
54 #ifdef CONFIG_FAIR_GROUP_SCHED
55     struct rq *rq;    /* cpu runqueue to which this cfs_rq is attached */
56 
57     /*
58      * leaf cfs_rqs are those that hold tasks (lowest schedulable entity in
59      * a hierarchy). Non-leaf lrqs hold other higher schedulable entities
60      * (like users, containers etc.)
61      *
62      * leaf_cfs_rq_list ties together list of leaf cfs_rq's in a cpu. This
63      * list is used during load balance.
64      */
65     int on_list;
66     struct list_head leaf_cfs_rq_list;
67     struct task_group *tg;    /* group that "owns" this runqueue */
68 
69 #ifdef CONFIG_CFS_BANDWIDTH
70     int runtime_enabled;
71     u64 runtime_expires;
72     s64 runtime_remaining;
73 
74     u64 throttled_clock, throttled_clock_task;
75     u64 throttled_clock_task_time;
76     int throttled, throttle_count;
77     struct list_head throttled_list;
78 #endif /* CONFIG_CFS_BANDWIDTH */
79 #endif /* CONFIG_FAIR_GROUP_SCHED */
80 };

  min_vruntime在CFS就绪队列数据结构中,单步递增,用于跟踪该就绪队列红黑树中最小的vruntime。

2.1普通进程的调度实体sched_entity

问题五:vruntime是何时更新的?

该结构体是本地cpu所有进程组成的就绪队列,在linux内核中,进程被分为普通进程和实时进程,这两种进程的调度策略是不同的,因此在31-32行可以看到rq结构体中又内嵌了struct cfs_rq
cfs和struct
rt_rq
rt两个子就绪队列,分别来组织普通进程和实时进程(普通进程将采用完全公平调度策略cfs,而实时进程将采用实时调度策略),第33行struct dl_rq
dl调度空闲进程,暂且不讨论。所以,如果咱们研究的是普通进程的调度,需要关心的就是struct cfs_rq
cfs队列;如果研究的是实时进程,就只关心struct rt_rq
rt队列。

  vruntime=(delta_exec*nice_0_weight)/weight。其中,delta_exec为实际运行时间,nice_0_weight为nice为0的权重值,weight表示该进程的权重值。在update_curr()函数中,完成了该值的计算,此时,为了计算高效,将计算方式变成了乘法和移位vruntime=(delta_exec*nice_0_weight*www.350.vip ,inv_weight)>>shift,其中inv_weight=2^32/weight,是预先计算好存放在prio_to_wmult中的。

1.就绪队列

  4种调度类通过next指针串联在一起,用户空间程序可以使用调度策略API函数(sched_setscheduler())来设定用户进程的调度策略。

www.350.vip 5www.350.vip 6

问题九:内核代码中定义了若干个表,请分别说出它们的含义,比如prio_to_weight、prio_to_wmult、runnable_avg_yN_inv、runnable_avg_yN_sum。

每个进程描述符中均包含一个该结构体变量,内核使用该结构体来将普通进程组织到采用完全公平调度策略的就绪队列中(struct
rq中的cfs队列中,上边提到过),该结构体有两个作用,一是包含有进程调度的信息(比如进程的运行时间,睡眠时间等等,调度程序参考这些信息决定是否调度进程),二是使用该结构体来组织进程,第3行的struct
rb_node类型结构体变量run_node是红黑树节点,因此struct
sched_entity调度实体将被组织成红黑树的形式,同时意味着普通进程也被组织成红黑树的形式。第18-25行是和组调度有关的成员,需要开启组调度。第20行parent顾名思义指向了当前实体的上一级实体,后边再介绍。第22行的cfs_rq指向了该调度实体所在的就绪队列。第24行my_q指向了本实体拥有的就绪队列(调度组),该调度组(包括组员实体)属于下一个级别,和本实体不在同一个级别,该调度组中所有成员实体的parent域指向了本实体,这就解释了上边的parent,此外,第19行depth代表了此队列(调度组)的深度,每个调度组都比其parent调度组深度大1。内核依赖my_q域实现组调度。

  prio_to_weight表记录的是nice值对应的权重值。

4.进程描述符task_struct(include/linux/sched.h)

发表评论

电子邮件地址不会被公开。 必填项已用*标注