Linux Scheduling

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

 1 /* 进程组，用于实现组调度 */
 2 struct task_group {
 3     /* 用于进程找到其所属进程组结构 */
 4     struct cgroup_subsys_state css;
 5
 6 #ifdef CONFIG_FAIR_GROUP_SCHED
 7     /* CFS调度器的进程组变量，在 alloc_fair_sched_group() 中进程初始化及分配内存 */
 8     /* 该进程组在每个CPU上都有对应的一个调度实体，因为有可能此进程组同时在两个CPU上运行(它的A进程在CPU0上运行，B进程在CPU1上运行) */
 9     struct sched_entity **se;
10     /* 进程组在每个CPU上都有一个CFS运行队列(为什么需要，稍后解释) */
11     struct cfs_rq **cfs_rq;
12     /* 用于保存优先级默认为NICE 0的优先级 */
13     unsigned long shares;
14
15 #ifdef    CONFIG_SMP
16     atomic_long_t load_avg;
17     atomic_t runnable_avg;
18 #endif
19 #endif
20
21 #ifdef CONFIG_RT_GROUP_SCHED
22     /* 实时进程调度器的进程组变量，同 CFS */
23     struct sched_rt_entity **rt_se;
24     struct rt_rq **rt_rq;
25
26     struct rt_bandwidth rt_bandwidth;
27 #endif
28
29     struct rcu_head rcu;
30     /* 用于建立进程链表(属于此调度组的进程链表) */
31     struct list_head list;
32
33     /* 指向其上层的进程组，每一层的进程组都是它上一层进程组的运行队列的一个调度实体，在同一层中，进程组和进程被同等对待 */
34     struct task_group *parent;
35     /* 进程组的兄弟结点链表 */
36     struct list_head siblings;
37     /* 进程组的儿子结点链表 */
38     struct list_head children;
39
40 #ifdef CONFIG_SCHED_AUTOGROUP
41     struct autogroup *autogroup;
42 #endif
43
44     struct cfs_bandwidth cfs_bandwidth;
45 };

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

 1 struct task_struct {
 2     ........
 3     /* 表示是否在运行队列 */
 4     int on_rq;
 5
 6     /* 进程优先级
 7      * prio: 动态优先级，范围为100~139，与静态优先级和补偿(bonus)有关
 8      * static_prio: 静态优先级，static_prio = 100 + nice + 20 (nice值为-20~19,所以static_prio值为100~139)
 9      * normal_prio: 没有受优先级继承影响的常规优先级，具体见normal_prio函数，跟属于什么类型的进程有关
10      */
11     int prio, static_prio, normal_prio;
12     /* 实时进程优先级 */
13     unsigned int rt_priority;
14     /* 调度类，调度处理函数类 */
15     const struct sched_class *sched_class;
16     /* 调度实体(红黑树的一个结点) */
17     struct sched_entity se;
18     /* 调度实体(实时调度使用) */
19     struct sched_rt_entity rt;
20 #ifdef CONFIG_CGROUP_SCHED
21     /* 指向其所在进程组 */
22     struct task_group *sched_task_group;
23 #endif
24     ........
25 }

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74

 1 struct sched_class {
 2     /* 下一优先级的调度类
 3      * 调度类优先级顺序: stop_sched_class -> dl_sched_class -> rt_sched_class -> fair_sched_class -> idle_sched_class
 4      */
 5     const struct sched_class *next;
 6
 7     /* 将进程加入到运行队列中，即将调度实体（进程）放入红黑树中，并对 nr_running 变量加1 */
 8     void (*enqueue_task) (struct rq *rq, struct task_struct *p, int flags);
 9     /* 从运行队列中删除进程，并对 nr_running 变量中减1 */
10     void (*dequeue_task) (struct rq *rq, struct task_struct *p, int flags);
11     /* 放弃CPU，在 compat_yield sysctl 关闭的情况下，该函数实际上执行先出队后入队；在这种情况下，它将调度实体放在红黑树的最右端 */
12     void (*yield_task) (struct rq *rq);
13     bool (*yield_to_task) (struct rq *rq, struct task_struct *p, bool preempt);
14
15     /* 检查当前进程是否可被新进程抢占 */
16     void (*check_preempt_curr) (struct rq *rq, struct task_struct *p, int flags);
17
18     /*
19      * It is the responsibility of the pick_next_task() method that will
20      * return the next task to call put_prev_task() on the @prev task or
21      * something equivalent.
22      *
23      * May return RETRY_TASK when it finds a higher prio class has runnable
24      * tasks.
25      */
26     /* 选择下一个应该要运行的进程运行 */
27     struct task_struct * (*pick_next_task) (struct rq *rq,
28                         struct task_struct *prev);
29     /* 将进程放回运行队列 */
30     void (*put_prev_task) (struct rq *rq, struct task_struct *p);
31
32 #ifdef CONFIG_SMP
33     /* 为进程选择一个合适的CPU */
34     int (*select_task_rq)(struct task_struct *p, int task_cpu, int sd_flag, int flags);
35     /* 迁移任务到另一个CPU */
36     void (*migrate_task_rq)(struct task_struct *p, int next_cpu);
37     /* 用于上下文切换后 */
38     void (*post_schedule) (struct rq *this_rq);
39     /* 用于进程唤醒 */
40     void (*task_waking) (struct task_struct *task);
41     void (*task_woken) (struct rq *this_rq, struct task_struct *task);
42     /* 修改进程的CPU亲和力(affinity) */
43     void (*set_cpus_allowed)(struct task_struct *p,
44                  const struct cpumask *newmask);
45     /* 启动运行队列 */
46     void (*rq_online)(struct rq *rq);
47     /* 禁止运行队列 */
48     void (*rq_offline)(struct rq *rq);
49 #endif
50     /* 当进程改变它的调度类或进程组时被调用 */
51     void (*set_curr_task) (struct rq *rq);
52     /* 该函数通常调用自 time tick 函数；它可能引起进程切换。这将驱动运行时（running）抢占 */
53     void (*task_tick) (struct rq *rq, struct task_struct *p, int queued);
54     /* 在进程创建时调用，不同调度策略的进程初始化不一样 */
55     void (*task_fork) (struct task_struct *p);
56     /* 在进程退出时会使用 */
57     void (*task_dead) (struct task_struct *p);
58
59     /* 用于进程切换 */
60     void (*switched_from) (struct rq *this_rq, struct task_struct *task);
61     void (*switched_to) (struct rq *this_rq, struct task_struct *task);
62     /* 改变优先级 */
63     void (*prio_changed) (struct rq *this_rq, struct task_struct *task,
64              int oldprio);
65
66     unsigned int (*get_rr_interval) (struct rq *rq,
67                      struct task_struct *task);
68
69     void (*update_curr) (struct rq *rq);
70
71 #ifdef CONFIG_FAIR_GROUP_SCHED
72     void (*task_move_group) (struct task_struct *p, int on_rq);
73 #endif
74 };

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99

 1 /* CFS调度的运行队列，每个CPU的rq会包含一个cfs_rq，而每个组调度的sched_entity也会有自己的一个cfs_rq队列 */
 2 struct cfs_rq {
 3     /* CFS运行队列中所有进程的总负载 */
 4     struct load_weight load;
 5     /*
 6      * nr_running: cfs_rq中调度实体数量
 7      * h_nr_running: 只对进程组有效，其下所有进程组中cfs_rq的nr_running之和
 8      */
 9     unsigned int nr_running, h_nr_running;
10
11     u64 exec_clock;
12     /* 当前CFS队列上最小运行时间，单调递增
13      * 两种情况下更新该值:
14      * 1、更新当前运行任务的累计运行时间时
15      * 2、当任务从队列删除去，如任务睡眠或退出，这时候会查看剩下的任务的vruntime是否大于min_vruntime，如果是则更新该值。
16      */
17     u64 min_vruntime;
18 #ifndef CONFIG_64BIT
19     u64 min_vruntime_copy;
20 #endif
21     /* 该红黑树的root */
22     struct rb_root tasks_timeline;
23     /* 下一个调度结点(红黑树最左边结点，最左边结点就是下个调度实体) */
24     struct rb_node *rb_leftmost;
25
26     /*
27      * 'curr' points to currently running entity on this cfs_rq.
28      * It is set to NULL otherwise (i.e when none are currently running).
29      */
30     /*
31      * curr: 当前正在运行的sched_entity（对于组虽然它不会在cpu上运行，但是当它的下层有一个task在cpu上运行，那么它所在的cfs_rq就把它当做是该cfs_rq上当前正在运行的sched_entity）
32      * next: 表示有些进程急需运行，即使不遵从CFS调度也必须运行它，调度时会检查是否next需要调度，有就调度next
33      *
34      * skip: 略过进程(不会选择skip指定的进程调度)
35      */
36     struct sched_entity *curr, *next, *last, *skip;
37
38 #ifdef    CONFIG_SCHED_DEBUG
39     unsigned int nr_spread_over;
40 #endif
41
42 #ifdef CONFIG_SMP
43     /*
44      * CFS Load tracking
45      * Under CFS, load is tracked on a per-entity basis and aggregated up.
46      * This allows for the description of both thread and group usage (in
47      * the FAIR_GROUP_SCHED case).
48      */
49     unsigned long runnable_load_avg, blocked_load_avg;
50     atomic64_t decay_counter;
51     u64 last_decay;
52     atomic_long_t removed_load;
53
54 #ifdef CONFIG_FAIR_GROUP_SCHED
55     /* Required to track per-cpu representation of a task_group */
56     u32 tg_runnable_contrib;
57     unsigned long tg_load_contrib;
58
59     /*
60      * h_load = weight * f(tg)
61      *
62      * Where f(tg) is the recursive weight fraction assigned to
63      * this group.
64      */
65     unsigned long h_load;
66     u64 last_h_load_update;
67     struct sched_entity *h_load_next;
68 #endif /* CONFIG_FAIR_GROUP_SCHED */
69 #endif /* CONFIG_SMP */
70
71 #ifdef CONFIG_FAIR_GROUP_SCHED
72     /* 所属于的CPU rq */
73     struct rq *rq;    /* cpu runqueue to which this cfs_rq is attached */
74
75     /*
76      * leaf cfs_rqs are those that hold tasks (lowest schedulable entity in
77      * a hierarchy). Non-leaf lrqs hold other higher schedulable entities
78      * (like users, containers etc.)
79      *
80      * leaf_cfs_rq_list ties together list of leaf cfs_rq's in a cpu. This
81      * list is used during load balance.
82      */
83     int on_list;
84     struct list_head leaf_cfs_rq_list;
85     /* 拥有该CFS运行队列的进程组 */
86     struct task_group *tg;    /* group that "owns" this runqueue */
87
88 #ifdef CONFIG_CFS_BANDWIDTH
89     int runtime_enabled;
90     u64 runtime_expires;
91     s64 runtime_remaining;
92
93     u64 throttled_clock, throttled_clock_task;
94     u64 throttled_clock_task_time;
95     int throttled, throttle_count;
96     struct list_head throttled_list;
97 #endif /* CONFIG_CFS_BANDWIDTH */
98 #endif /* CONFIG_FAIR_GROUP_SCHED */
99 };

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157

  1 /* CPU运行队列，每个CPU包含一个struct rq */
  2 struct rq {
  3     /* 处于运行队列中所有就绪进程的load之和 */
  4     raw_spinlock_t lock;
  5
  6     /*
  7      * nr_running and cpu_load should be in the same cacheline because
  8      * remote CPUs use both these fields when doing load calculation.
  9      */
 10     /* 此CPU上总共就绪的进程数，包括cfs，rt和正在运行的 */
 11     unsigned int nr_running;
 12 #ifdef CONFIG_NUMA_BALANCING
 13     unsigned int nr_numa_running;
 14     unsigned int nr_preferred_running;
 15 #endif
 16     #define CPU_LOAD_IDX_MAX 5
 17     /* 根据CPU历史情况计算的负载，cpu_load[0]一直等于load.weight，当达到负载平衡时，cpu_load[1]和cpu_load[2]都应该等于load.weight */
 18     unsigned long cpu_load[CPU_LOAD_IDX_MAX];
 19     /* 最后一次更新 cpu_load 的时间 */
 20     unsigned long last_load_update_tick;
 21 #ifdef CONFIG_NO_HZ_COMMON
 22     u64 nohz_stamp;
 23     unsigned long nohz_flags;
 24 #endif
 25 #ifdef CONFIG_NO_HZ_FULL
 26     unsigned long last_sched_tick;
 27 #endif
 28     /* 是否需要更新rq的运行时间 */
 29     int skip_clock_update;
 30
 31     /* capture load from *all* tasks on this cpu: */
 32     /* CPU负载，该CPU上所有可运行进程的load之和，nr_running更新时这个值也必须更新 */
 33     struct load_weight load;
 34     unsigned long nr_load_updates;
 35     /* 进行上下文切换次数，只有proc会使用这个 */
 36     u64 nr_switches;
 37
 38     /* cfs调度运行队列，包含红黑树的根 */
 39     struct cfs_rq cfs;
 40     /* 实时调度运行队列 */
 41     struct rt_rq rt;
 42     struct dl_rq dl;
 43
 44 #ifdef CONFIG_FAIR_GROUP_SCHED
 45     /* list of leaf cfs_rq on this cpu: */
 46     struct list_head leaf_cfs_rq_list;
 47
 48     struct sched_avg avg;
 49 #endif /* CONFIG_FAIR_GROUP_SCHED */
 50
 51     /*
 52      * This is part of a global counter where only the total sum
 53      * over all CPUs matters. A task can increase this counter on
 54      * one CPU and if it got migrated afterwards it may decrease
 55      * it on another CPU. Always updated under the runqueue lock:
 56      */
 57      /* 曾经处于队列但现在处于TASK_UNINTERRUPTIBLE状态的进程数量 */
 58     unsigned long nr_uninterruptible;
 59
 60     /*
 61      * curr: 当前正在此CPU上运行的进程
 62      * idle: 当前CPU上idle进程的指针，idle进程用于当CPU没事做的时候调用，它什么都不执行
 63      */
 64     struct task_struct *curr, *idle, *stop;
 65     /* 下次进行负载平衡执行时间 */
 66     unsigned long next_balance;
 67     /* 在进程切换时用来存放换出进程的内存描述符地址 */
 68     struct mm_struct *prev_mm;
 69
 70     /* rq运行时间 */
 71     u64 clock;
 72     u64 clock_task;
 73
 74     atomic_t nr_iowait;
 75
 76 #ifdef CONFIG_SMP
 77     struct root_domain *rd;
 78     /* 当前CPU所在基本调度域，每个调度域包含一个或多个CPU组，每个CPU组包含该调度域中一个或多个CPU子集，负载均衡都是在调度域中的组之间完成的，不能跨域进行负载均衡 */
 79     struct sched_domain *sd;
 80
 81     unsigned long cpu_capacity;
 82
 83     unsigned char idle_balance;
 84     /* For active balancing */
 85     int post_schedule;
 86     /* 如果需要把进程迁移到其他运行队列，就需要设置这个位 */
 87     int active_balance;
 88     int push_cpu;
 89     struct cpu_stop_work active_balance_work;
 90
 91     /* 该运行队列所属CPU */
 92     int cpu;
 93     int online;
 94
 95     struct list_head cfs_tasks;
 96
 97     u64 rt_avg;
 98     /* 该运行队列存活时间 */
 99     u64 age_stamp;
100     u64 idle_stamp;
101     u64 avg_idle;
102
103     /* This is used to determine avg_idle's max value */
104     u64 max_idle_balance_cost;
105 #endif
106
107 #ifdef CONFIG_IRQ_TIME_ACCOUNTING
108     u64 prev_irq_time;
109 #endif
110 #ifdef CONFIG_PARAVIRT
111     u64 prev_steal_time;
112 #endif
113 #ifdef CONFIG_PARAVIRT_TIME_ACCOUNTING
114     u64 prev_steal_time_rq;
115 #endif
116
117     /* calc_load related fields */
118     /* 用于负载均衡 */
119     unsigned long calc_load_update;
120     long calc_load_active;
121
122 #ifdef CONFIG_SCHED_HRTICK
123 #ifdef CONFIG_SMP
124     int hrtick_csd_pending;
125     struct call_single_data hrtick_csd;
126 #endif
127     /* 调度使用的高精度定时器 */
128     struct hrtimer hrtick_timer;
129 #endif
130
131 #ifdef CONFIG_SCHEDSTATS
132     /* latency stats */
133     struct sched_info rq_sched_info;
134     unsigned long long rq_cpu_time;
135     /* could above be rq->cfs_rq.exec_clock + rq->rt_rq.rt_runtime ? */
136
137     /* sys_sched_yield() stats */
138     unsigned int yld_count;
139
140     /* schedule() stats */
141     unsigned int sched_count;
142     unsigned int sched_goidle;
143
144     /* try_to_wake_up() stats */
145     unsigned int ttwu_count;
146     unsigned int ttwu_local;
147 #endif
148
149 #ifdef CONFIG_SMP
150     struct llist_head wake_list;
151 #endif
152
153 #ifdef CONFIG_CPU_IDLE
154     /* Must be inspected within a rcu lock section */
155     struct cpuidle_state *idle_state;
156 #endif
157 };