kk Blog —— 通用基础

date [-d @int|str] [+%s|"+%F %T"]

mod_timer会切换cpu

https://lkml.org/lkml/2009/4/16/45

Ingo, Thomas, all,

In an SMP system, tasks are scheduled on different CPUs by the scheduler, interrupts are managed by irqbalancer daemon, but timers are still stuck to the CPUs that they have been initialised. Timers queued by tasks gets re-queued on the CPU where the task gets to run next, but timers from IRQ context like the ones in device drivers are still stuck on the CPU they were initialised. This framework will help move all ‘movable timers’ using a sysctl interface.

kernel/timer.c 中 __mod_timer函数的部分patch:

1
2
3
4
5
6
7
8
9
10
11
+    cpu = smp_processor_id();
+ if (get_sysctl_timer_migration() && idle_cpu(cpu) && !pinned) {
+#if defined(CONFIG_NO_HZ) && (CONFIG_SMP)
+     preferred_cpu = get_nohz_load_balancer();
+#endif
+     if (preferred_cpu >= 0)
+         cpu = preferred_cpu;
+ }
+
+ new_base = per_cpu(tvec_bases, cpu);
+

也就是说:如果当前进程是idle(函数idle_cpu(cpu)判定),那么在mod_timer时会根据cpu的struct rq runqueues;中的 struct sched_domain *sd; 来选一个不是idle的cpu,然后把timer移到他上去。如果都是idle,就还在本cpu。
禁用该功能可以 echo 0 > /proc/sys/kernel/timer_magration,默认的启用是1。

也就是说:系统默认状态下mod_timer有可能会mod_timer到其他cpu上。


但是基本只有softirq时(如 /blog/2015/01/14/debug-softirq-time-count/),这时会的当前进程就是idle,但cpu实际并不空闲。这样的话softirq的timer在mod_timer时,会被加到其他cpu的定时器队列。如果这些timer是不允许切换cpu的(如对per_cpu变量的操作),那么就会产生bug。

中断时间统计

软中断运行在中断上下文,不会被抢占调度,只会被硬中断打断,但硬中断退出时还是继续执行没结束的软中断。

因为软中断不是运行在进程上下文,不具备被调度的前提,也不具备统计运行时间。系统是将softirq的时间加到当前被他打断的进程上(还是不统计softirq时间???有待学习)。

如果当前系统只运行数据包的接收服务,那么系统很可能显示的是100%idle,因为被softirq打断的进程就是idle。

如果softirq足够多,导致启动了ksoftirqd进程来协助处理,那么softirq的时间会被记到ksoftirqd的进程上,显示有“有点正常”了。

这样就会出现:当cpu个数充足时显示100%idle,然后减少到一半cpu就显示X%si。也就是说显示100%idle是不对,应该是近似的(x/2)%si

linux内核分析之调度算法(一)

http://blog.csdn.net/bullbat/article/details/7160246

linux调度算法在2.6.32中采用调度类实现模块式的调度方式。这样,能够很好的加入新的调度算法。

linux调度器是以模块方式提供的,这样做的目的是允许不同类型的进程可以有针对性地选择调度算法。这种模块化结构被称为调度器类,他允许多种不同哦可动态添加的调度算法并存,调度属于自己范畴的进程。每个调度器都有一个优先级,调度代码会按照优先级遍历调度类,拥有一个可执行进程的最高优先级的调度器类胜出,去选择下面要执行的那个程序。

linux上主要有两大类调度算法,CFS(完全公平调度算法)和实时调度算法。宏SCHED_NOMAL主要用于CFS调度,而SCHED_FIFO和SCHED_RR主要用于实时调度。如下面的宏定义:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/*
 * Scheduling policies
 */
 /*支援Real-Time Task的排程,包括有SCHED_FIFO與SCHED_RR. 
 */
 
 /*(也稱為SCHED_OTHER): 主要用以排程
 一般目的的Task.*/
#define SCHED_NORMAL      0
#define SCHED_FIFO        1
/*task預設的 Time Slice長度為100 msecs*/
#define SCHED_RR      2
/*主要用以讓Task可以延長執行的時間
(Time Slice),減少被中斷發生Task Context-Switch
的次數.藉此可以提高 Cache的利用率 
(每次Context-Switch都會導致Cache-Flush). 比
較適合用在固定週期執行的Batch Jobs任
務主機上,而不適合用在需要使用者互
動的產品 (會由於Task切換的延遲,而
感覺到系統效能不佳或是反應太慢).*/
#define SCHED_BATCH       3
/* SCHED_ISO: reserved but not implemented yet */
/*為系統中的Idle Task排程.*/
#define SCHED_IDLE        5

linux调度算法实现的高层数据结构主要有运行实体、调度类、运行队列,下面我们主要看看这几个数据结构的字段和意义。
运行实体,rq结构体每个cpu有一个,主要存储一些基本的用于调度的信息,包括实时调度的和CFS调度的

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
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
 /*每个处理器都会配置一个rq*/
struct rq {
	/* runqueue lock: */
	spinlock_t lock;

	/*
	 * nr_running and cpu_load should be in the same cacheline because
	 * remote CPUs use both these fields when doing load calculation.
	 */
	 /*用以记录目前处理器rq中执行task的数量*/
	unsigned long nr_running;
	#define CPU_LOAD_IDX_MAX 5
	/*用以表示处理器的负载,在每个处理器的rq中
	都会有对应到该处理器的cpu_load参数配置,在每次
	处理器触发scheduler tick时,都会呼叫函数
	update_cpu_load_active,进行cpu_load的更新。在系统初始化的时候
	会呼叫函数sched_init把rq的cpu_load array初始化为0.
	了解他的更新方式最好的方式是通过函数update_cpu_load,公式如下澹?
	cpu_load[0]会直接等待rq中load.weight的值。
	cpu_load[1]=(cpu_load[1]*(2-1)+cpu_load[0])/2
	cpu_load[2]=(cpu_load[2]*(4-1)+cpu_load[0])/4
	cpu_load[3]=(cpu_load[3]*(8-1)+cpu_load[0])/8
	cpu_load[4]=(cpu_load[4]*(16-1)+cpu_load[0]/16
	呼叫函数this_cpu_load时,所返回的cpu load值是cpu_load[0]
	而在进行cpu blance或migration时,就会呼叫函数
	source_load target_load取得对该处理器cpu_load index值,
	来进行计算*/
	unsigned long cpu_load[CPU_LOAD_IDX_MAX];
#ifdef CONFIG_NO_HZ
	unsigned long last_tick_seen;
	unsigned char in_nohz_recently;
#endif
	/* capture load from *all* tasks on this cpu: */
	/*load->weight值,会是目前所执行的schedule entity的
	load->weight的总和,也就是说rq的load->weight越高,
	也表示所负责的排程单元load->weight总和越高
	表示处理器所负荷的执行单元也越重*/
	struct load_weight load;
	/*在每次scheduler tick中呼叫update_cpu_load时,
	这个值就增加一,可以用来反馈目前cpu
	load更新的次数*/
	unsigned long nr_load_updates;
	/*用来累加处理器进行context switch的次数,会在
	函数schedule呼叫时进行累加,并可以通过函数
	nr_context_switches统计目前所有处理器总共的context switch
	次数,或是可以透过查看档案/proc/stat中的ctxt位得知目前
	整个系统触发context switch的次数*/
	u64 nr_switches;

	u64 nr_migrations_in;
	/*为cfs fair scheduling class 的rq*/
	struct cfs_rq cfs;
	/*为real-time scheduling class 的rq*/
	struct rt_rq rt;

/*用以支援可以group cfs tasks的机制*/
#ifdef CONFIG_FAIR_GROUP_SCHED
	/* list of leaf cfs_rq on this cpu: */
	/*在有设置fair group scheduling 的环境下,
	会基于原本cfs rq中包含有若干task的group
	所成的排程集合,也就是说当有一个group a
	就会有自己的cfs rq用来排程自己所属的tasks,
	而属于这group a的tasks所使用到的处理器时间
	就会以这group a总共所分的的时间为上限。
	基于cgroup的fair group scheduling 架构,可以创造出
	有阶层性的task组织,根据不同task的功能群组化
	在配置给该群主对应的处理器资源,让属于
	该群主下的task可以透过rq机制排程。使用属于
	该群主下的资源。
	这个变数主要是管理CFS RQ list,操作上可以透过函数
	list_add_leaf_cfs_rq把一个group cfs rq加入到list中,或透过
	函数list_del_leaf_cfs_rq把一个group cfs rq移除,并可以
	透过for_each_leaf_cfs_rq把一个rq上得所有leaf cfs_rq走一遍
	*/
	struct list_head leaf_cfs_rq_list;
#endif
/*用以支援可以group real-time tasks的机制*/
#ifdef CONFIG_RT_GROUP_SCHED
	/*类似leaf_cfs_rq_list所扮演的角色,只是这里
	是针对属于real-time的task,在实际操作上可以
	透过函数list_add_leaf_rt_rq,list_del_leaf_rt_rq或
	巨集for_each_leaf_rt_rq*/
	struct list_head leaf_rt_rq_list;
#endif

	/*
	 * This is part of a global counter where only the total sum
	 * over all CPUs matters. A task can increase this counter on
	 * one CPU and if it got migrated afterwards it may decrease
	 * it on another CPU. Always updated under the runqueue lock:
	 */
	 /*一般来说,linux kernel 的task状态可以为TASK_RUNNING
	 TASK_INTERRUPTIBLE(sleep),
	 TASK_UNINTERRUPTIBLE(Deactivate Task,此时Task会从rq中
	 移除)或TASK_STOPPED.
	 透过这个变数会统计目前rq中有多少task属于
	 TASK_UNINTERRUPTIBLE的状态。当呼叫函数
	 active_task时,会把nr_uninterruptible值减一,并透过 该函数
	enqueue_task把对应的task依据所在的scheduling class
	放在 对应的rq中,并把目前rq中nr_running值加一*/
	unsigned long nr_uninterruptible;
	/*curr:指向目前处理器正在执行的task;
	idle:指向属于idle-task scheduling class 的idle task;
	stop:指向目前最高等级属于stop-task scheduling class
	的task;*/
	struct task_struct *curr, *idle;
	/*基于处理器的jiffies值,用以记录下次进行处理器
	balancing 的时间点*/
	unsigned long next_balance;
	/*用以存储context-switch发生时,前一个task的memory management
	结构并可用在函数finish_task_switch中,透过函数mmdrop释放前一个
	task的记忆体资源*/  
	struct mm_struct *prev_mm;
	/*用以记录目前rq的clock值,基本上该值会等于透过sched_clock_cpu
	(cpu_of(rq))的回传值,并会在每次呼叫scheduler_tick时透过
	函数update_rq_clock更新目前rq clock值。
	在实作部分,函数sched_clock_cpu会透过sched_clock_local或
	ched_clock_remote取得对应的sched_clock_data,而处理的sched_clock_data
	值,会透过函数sched_clock_tick在每次呼叫scheduler_tick时进行更新;
	*/
	u64 clock;
	/*用以记录目前rq中有多少task处于等待i/o的sleep状态
	在实际的使用上,例如当driver接受来自task的调用,但处于等待i/o
	回复的阶段时,为了充分利用处理器的执行资源,这时
	就可以在driver中呼叫函数io_schedule,此时
	就会把目前rq中的nr_iowait加一,并设定目前task的io_wait为1
	然后触发scheduling 让其他task有机会可以得到处理器执行时间*/
	atomic_t nr_iowait;

#ifdef CONFIG_SMP
	/*root domain是基于多核心架构下的机制,
	会由rq结构记住目前采用的root domain,其中包括了
	目前的cpu mask(包括span,online rt overload), reference count 跟cpupri
	当root domain有被rq参考到时,refcount 就加一,反之就减一。而cpu
	mask span表示rq可挂上的cpu mask,noline为rq目前已经排程的
	cpu mask cpu上执行real-time task.可以参考函数pull_rt_task,当一个rq中属于
	real-time的task已经执行完毕,就会透过函数pull_rt_task从该
	rq中属于rto_mask cpu mask 可以执行的处理器上,找出是否有一个处理器
	有大于一个以上的real-time task,若有就会转到目前这个执行完成
	real-time task 的处理器上
	而cpupri不同于Task本身有区分140個(0-139)
	Task Priority (0-99為RT Priority 而 100-139為Nice值 -20-19). 
	CPU Priority本身有102個Priority (包括,-1 為Invalid,
	0為Idle,1為Normal,2-101對應到Real-Time Priority 0-99).
	參考函式convert_prio, Task Priority如果是 140就會對應到
	CPU Idle,如果是大於等於100就會對應到CPU Normal,
	若是Task Priority介於0-99之間,就會對應到CPU Real-Time Priority 101-2之間.) 
	在實際的操作上,例如可以透過函式cpupri_find
	帶入一個要插入的Real-Time Task,此時就會依據cpupri中
	pri_to_cpu選擇一個目前執行Real-Time Task且該Task
	的優先級比目前要插入的Task更低的處理器,
	並透過CPU Mask(lowest_mask)返回目前可以選擇的處理器Mask.
	實作的部份可以參考檔案kernel/sched_cpupri.c.
	在初始化的過程中,會透過函式sched_init呼叫函式init_defrootdomain,
	對Root Domain與 CPU Priority機制進行初始化.
	*/
	struct root_domain *rd;
	/*Schedule Domain是基於多核心架構下的機制.
	每個處理器都會有一個基礎的Scheduling Domain,
	Scheduling Domain可以有階層性的架構,透過parent
	可以找到上一層的Domain,或是透過child找到
	下一層的 Domain (NULL表示結尾.).並可透過span
	栏位,表示這個Domain所能涵蓋的處理器範圍.
	通常Base Domain會涵蓋系統中所有處理器的個數,
	而Child Domain所能涵蓋的處理器個數不超過它的
	Parent Domain. 而當在進行Scheduling Domain 中的Task Balance
	時,就會以該Domain所能涵蓋的處理器為最大範圍.
	同時,每個Schedule Domain都會包括一個或一個以上的
	CPU Groups (結構為struct sched_group),並透過next變數把
	CPU Groups串連在一起(成為一個單向的Circular linked list),
	每個CPU Group都會有變數cpumask來定义這個CPU Group
	所涵蓋的處理器範圍.並且CPU Group所包括的處理器
	範圍,必需涵蓋在所屬的Schedule Domain處理器範圍中.
	當進行Scheduling Domain的Balancing時,會以其下的CPU Groups
	為單位,根據cpu_power (會是該Group所涵蓋的處理器
	Tasks Loading的總和)來比較不同的CPU Groups的負荷,
	以進行Tasks的移動,達到Balancing的目的.
	在有支援SMP的架構下,會在函式sched_init中,呼叫open_softirq,
	註冊 SCHED_SOFTIRQ Software IRQ与其对应的 Callback函式 
	run_rebalance_domains. 並會在每次呼叫函式scheduler_tick時,
	透過函式trigger_load_balance确认是否目前的jiffies值已經
	大於RunQueue下一次要觸發Load Balance的next_balance時間值,
	並透過函式raise_softirq觸發SCHED_SOFTIRQ Software IRQ. 
	在Software IRQ觸發後,就會呼叫函式run_rebalance_domains,
	並在函式rebalance_domains中,進行后续處理器上的
	Scheduling Domain Load Balance動作.
	有關Scheduling Domain進一步的內容,也可以參考
	Linux Kernel文件 Documentation/scheduler/sched-domains.txt.
	*/
	struct sched_domain *sd;
	/*這值會等於函式idle_cpu的返回值,如果為1表示
	目前CPU RunQueue中執行的為Idle Task. 反之為0,
	則表示處理器執行的不是Idle Task (也就是說
	處理器正在忙碌中.).*/
	unsigned char idle_at_tick;
	/* For active balancing */
	/*若這值不為0,表示會有在Schedule排程動作
	結束前,要呼叫的收尾函式. (实作為inline函式
	post_schedule in kernel/sched.c),目前只有Real-Time Scheduling 
	Class有支援這個機制(會呼叫函式has_pushable_tasks 
	in kernel/sched_rt.c).*/
	int post_schedule;
	/*當RunQueue中此值為1,表示這個RunQueue正在進行
	Fair Scheduling的Load Balance,此時會呼叫stop_one_cpu_nowait
	暫停該RunQueue所屬處理器的排程,並透過函式
	active_load_balance_cpu_stop,把Tasks從最忙碌的處理器,
	移到Idle的處理器上執行.*/
	int active_balance;
	/*用以儲存目前進入Idle且負責進行 Load Balance
	流程的處理器ID. 呼叫的流程為,在呼叫函式schedule時,
	若該處理器RunQueue的nr_running為0 (也就是目前沒有
	正在執行的Task),就會呼叫idle_balance,並觸發後續Load 
	Balance流程.*/
	int push_cpu;
	/* cpu of this runqueue: */
	/*用以儲存目前运作這個RunQueue的處理器ID*/
	int cpu;
	/*為1表示目前此RunQueue有在對應的處理器掛上
	並執行.*/
	int online;
	/*如果RunQueue中目前有Task正在執行,這個值會
	等於目前該RunQueue的Load Weight除以目前RunQueue
	中Task數目的均值. 
	(rq->avg_load_per_task = rq->load.weight / nr_running;).*/
	unsigned long avg_load_per_task;

	struct task_struct *migration_thread;
	struct list_head migration_queue;
	/*這個值會由Real-Time Scheduling Class呼叫函式
	update_curr_rt,用以統計目前Real-Time Task執行時間的
	均值,在這函式中會以目前RunQueue的clock_task
	減去目前Task執行的起始時間,取得執行時間的
	Delta值. (delta_exec = rq->clock_task – curr->se.exec_start; ).
	在透過函式sched_rt_avg_update把這Delta值跟原本
	RunQueue中的rt_avg值取平均值. 以運作的週期來看,
	這個值可反應目前系統中Real-Time Task平均被
	分配到的執行時間值.*/
	u64 rt_avg;
	/*這個值主要在函式sched_avg_update更新,以笔者手中
	的Linux Kernel 2.6.38.6的實作來說,當RunQueue Clock
	減去age_stamp大於 0.5秒 (=sched_avg_period),就會把這值
	累加0.5秒 (單位都是nanoseconds). 從函式scale_rt_power
	的實作來說,age_stamp值離RunQueue Clock越遠,表示total
	值越大,available值也越大,而函式scale_rt_power返回的
	div_u64計算結果也越大,最終 RunQueue的cpu_power
	與Scheduling Domain中的Scheduling Group的cpu_power
	值也就越大. (可參考函式update_cpu_power的實作).*/
	u64 age_stamp;
	/*這值會在觸發Scheduling時,若判斷目前處理器
	RunQueue沒有正在運作的Task,就會透過函式
	idle_balance更新這值為為目前RunQueue的clock值.
	可用以表示這個處理器是何時進入到Idle的
	狀態*/
	u64 idle_stamp;
	/*會在有Task運作且idle_stamp不為0 (表示前一個
	狀態是在Idle)時以目前RunQueue的clock減去
	idle_stmp所計算出的Delta值為依據,更新這個值
	. 可反應目前處理器進入Idle狀態的時間長短*/
	u64 avg_idle;
#endif

	/* calc_load related fields */
	/*用以記錄下一次計算CPU Load的時間,初始值
	為目前的jiffies加上五秒與1次的Scheduling Tick的
	間隔 (=jiffies + LOAD_FREQ,且LOAD_FREQ=(5*HZ+1))*/
	unsigned long calc_load_update;
	/*會等於RunQueue中nr_running與nr_uninterruptible的
	總和.(可參考函式calc_load_fold_active).*/
	long calc_load_active;

#ifdef CONFIG_SCHED_HRTICK
#ifdef CONFIG_SMP
	/*在函式init_rq_hrtick初始化RunQueue High-Resolution 
	Tick時,此值預設為0.
	在函式hrtick_start中,會判斷目前觸發的RunQueue
	跟目前處理器所使用的RunQueue是否一致,
	若是,就直接呼叫函式hrtimer_restart,反之就會
	依據RunQueue中hrtick_csd_pending的值,如果
	hrtick_csd_pending為0,就會透過函式
	__smp_call_function_single讓RunQueue所在的另一個
	處理器執行rq->hrtick_csd.func 所指到的函式 
	__hrtick_start. 並等待該處理器執行完畢後,
	才重新把hrtick_csd_pending設定為1.
	也就是說, RunQueue的hrtick_csd_pending是用來作為
	SMP架構下,由處理器A觸發處理器B執行
	_hrtick_start函式的一個保護機制.而有關在
	SMP下如何由一個處理器觸發另一個處理器
	執行函式的機制,可以參考kernel/smp.c中
	相關smp_call_function_xxxxxxx的實作.s*/
	int hrtick_csd_pending;
	/*用以儲存hrtick機制中,要跨處理器執行的
	函式結構.*/
	struct call_single_data hrtick_csd;
#endif
	/*為High-Resolution Tick的结构,會透過函式
	hrtimer_init初始化.*/
	struct hrtimer hrtick_timer;
#endif

#ifdef CONFIG_SCHEDSTATS
	/* latency stats */
	/*為Scheduling Info.的統計結構,可以參考
	include/linux/sched.h中的宣告. 例如在每次觸發
	Schedule時,呼叫函式schedule_debug對上一個Task
	的lock_depth進行確認(Fork一個新的Process 時,
	會把此值預設為-1就是No-Lock,當呼叫
	Kernel Lock時, 就會把Current Task的lock_depth加一.),
	若lock_depth>=0,就會累加Scheduling Info.的bkl_count值,
	用以代表Task Blocking的次數.*/
	struct sched_info rq_sched_info;
	/*可用以表示RunQueue中的Task所得到CPU執行
	時間的累加值.
	在發生Task Switch時,會透過sched_info_switch呼叫
	sched_info_arrive並以目前RunQueue Clock值更新
	Task 的sched_info.last_arrival時間,而在Task所分配時間
	結束後,會在函式sched_info_depart中以現在的
	RunQueue Clock值減去Task的sched_info.last_arrival
	時間值,得到的 Delta作為變數rq_cpu_time的累
	加值.*/
	unsigned long long rq_cpu_time;
	/* could above be rq->cfs_rq.exec_clock + rq->rt_rq.rt_runtime ? */

	/* sys_sched_yield() stats */
	/*用以統計呼叫System Call sys_sched_yield的次數.*/
	unsigned int yld_count;

	/* schedule() stats */
	unsigned int sched_switch;
	/*可用以統計觸發Scheduling的次數. 在每次觸發
	Scheduling時,會透過函式schedule呼叫schedule_debug,
	呼叫schedstat_inc對這變數進行累加.*/
	unsigned int sched_count;
	/*可用以統計進入到Idle Task的次數. 會在函式
	pick_next_task_idle中,呼叫schedstat_inc對這變數進行
	累加.*/
	unsigned int sched_goidle;

	/* try_to_wake_up() stats */
	/*用以統計Wake Up Task的次數.*/
	unsigned int ttwu_count;
	/*用以統計Wake Up 同一個處理器Task的次數.*/
	unsigned int ttwu_local;

	/* BKL stats */
	unsigned int bkl_count;
#endif
};

调度类,sched_class为对模块编程的上层支持,对于每个linux新添加进来的调度算法都需要有自己的调度类实例。

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
/*CFS排程機制在設計時,考慮到排程機制的
彈性,定義了Scheduler Class的機制,讓排程機制
可以根據設計的需求,延伸不同的排程模
組進來,每個新加入的排程機制都必須要
提供Scheduler Class的實作,結構為 struct sched_class*/
struct sched_class {
	/*會指向下一個Scheduling Class,以筆者所採用
	的Linux Kernel 2.6.38.6而言,Scheduling Class的順序為
	stop_sched_class->rt_sched_class->fair_sched_class->idle_sched_class*/
	const struct sched_class *next;
	/*當Task屬於Runnable狀態時,就會呼叫這個函式
	把Task配置到RunQueue RBTree中,進行排程動作,
	並呼叫inc_nr_running將RunQueue中nr_running的值
	加一.(nr_running用以代表目前RunQueue有多少
	Runnable Task進行排程)*/
	void (*enqueue_task) (struct rq *rq, struct task_struct *p, int wakeup);
	/*當Task不需要執行時,就會呼叫這個函式
	把Task從RunQueue RBTree中移除,並呼叫
	dec_nr_running將RunQueue中nr_running的值減一.*/
	void (*dequeue_task) (struct rq *rq, struct task_struct *p, int sleep);
	/*用以暫停目前正在執行中的Task,如果
	sysctl_sched_compat_yield有設定,就會找出目前
	RBTree中最右邊的Task(也就是vrruntime最多
	的Task),讓目前Task的vrruntime值等於最右邊
	Task值的vrruntime加一(可參考:
	se->vruntime = rightmost->vruntime + 1),如此在下次
	排程觸發時就會透過函式put_prev_task把目前
	的Task放到RBTree的最右邊,也就等同於暫停
	Task,讓該Task下次被執行到的機會最低.*/
	void (*yield_task) (struct rq *rq);
	/*用以決定一個Task是否可以中斷目前正在
	運作的Task,取得執行權.以CFS本身的實作來說
	(in sched_fair.c).如果想要取代目前Task的Task本身
	的Scheduling Policy為 Batch或是Idle時,會直接返回,
	不會用來取代目前正在執行中的Task.反之,
	如果目前正在執行中的Task的Scheduling Policy
	為Idle,就會直接由所傳入的Task取代目前正
	在執行的Task.*/
	void (*check_preempt_curr) (struct rq *rq, struct task_struct *p, int flags);
	/*用以在排程觸發時,從RunQueue RBTree中,
	取出符合目前Scheduling邏輯的下一個要
	被執行的Task.*/
	struct task_struct * (*pick_next_task) (struct rq *rq);
	/*用以在排程觸發時,把上一個執行完畢的
	Task放到目前RunQueue RBTree中對應的位置.*/
	void (*put_prev_task) (struct rq *rq, struct task_struct *p);

#ifdef CONFIG_SMP
	/*通常用在執行一個新的程序,或是WakeUp
	一個Task時,會根據目前SMP下每個處理器的
	負荷,決定Task是否要切換到另一個處理器
	的RunQueue去執行,執行時會返回最後目標
	處理器的值.*/
	int  (*select_task_rq)(struct task_struct *p, int sd_flag, int flags);

	unsigned long (*load_balance) (struct rq *this_rq, int this_cpu,
			struct rq *busiest, unsigned long max_load_move,
			struct sched_domain *sd, enum cpu_idle_type idle,
			int *all_pinned, int *this_best_prio);

	int (*move_one_task) (struct rq *this_rq, int this_cpu,
				  struct rq *busiest, struct sched_domain *sd,
				  enum cpu_idle_type idle);
	void (*pre_schedule) (struct rq *this_rq, struct task_struct *task);
	void (*post_schedule) (struct rq *this_rq);
	void (*task_wake_up) (struct rq *this_rq, struct task_struct *task);

	void (*set_cpus_allowed)(struct task_struct *p,
				 const struct cpumask *newmask);

	void (*rq_online)(struct rq *rq);
	void (*rq_offline)(struct rq *rq);
#endif
	/*這個函式用以改變Task目前所屬的Scheduling
	Class與改變Task Group.*/
	void (*set_curr_task) (struct rq *rq);
	/*這是Scheduler的 Timer Tick來源,系統中觸發的
	Scheduling Tick會呼叫這個函式 (看HZ設定多少,
	100就是每秒呼叫這函式100次,1000就是每秒
	呼叫這函式1000次),
	用以讓排程機制可以決定哪些Task應該要配
	執行與哪些Task應該要被移出RunQueue.*/
	void (*task_tick) (struct rq *rq, struct task_struct *p, int queued);
	void (*task_new) (struct rq *rq, struct task_struct *p);

	void (*switched_from) (struct rq *this_rq, struct task_struct *task,
				   int running);
	void (*switched_to) (struct rq *this_rq, struct task_struct *task,
				 int running);
	void (*prio_changed) (struct rq *this_rq, struct task_struct *task,
				 int oldprio, int running);

	unsigned int (*get_rr_interval) (struct task_struct *task);

#ifdef CONFIG_FAIR_GROUP_SCHED
	void (*moved_group) (struct task_struct *p);
#endif
};

调度实体,调度实体用于调度时间记账,linux中CFS和实时调度使用不同的调度实体。调度运行队列,对于不用的调度算法同样运用不用的运行队列,对于CFS调度,运用的是红黑树,而对于实时调度为组链表。在后面具体的调度算法介绍中我们会看到他们的运用。

Idle进程的切换过程

http://blog.chinaunix.net/uid-27767798-id-3577069.html

每个cpu都有自己的运行队列,如果当前cpu上运行的任务都已经dequeue出运行队列,而且idle_balance也没有移动到当前运行队列的任务,那么schedule函数中,按照rt ,cfs,idle这三种调度方式顺序,寻找各自的运行任务,那么如果rt和cfs都未找到运行任务,那么最后会调用idle schedule的idle进程,作为schedule函数调度的下一个任务。

kernel/sched.c 中的schedule()函数中的片段

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
if (prev->state && !(preempt_count() & PREEMPT_ACTIVE)) {   
	//state大于0代表prev也就是当前运行的任务不是running状态,并且没有标记 PREEMPT_ACTIVE,就表示当前的运行的任务没有必要停留在运行队列中了
	if (unlikely(signal_pending_state(prev->state, prev)))  //如果当前进程标记了状态是TASK_INTERRUPTIBLE,并且还有信号未处理,那么没有必要从运行队列中移除这个进程
		prev->state = TASK_RUNNING;
	else
		deactivate_task(rq, prev, DEQUEUE_SLEEP);        //从运行队列中移除这个进程
	switch_count = &prev->nvcsw;
}

pre_schedule(rq, prev);

if (unlikely(!rq->nr_running)) //如果当前运行队列没有进程可以运行了,就balance其他运行队列的任务到当前运行队列,这里balance的具体过程暂时不说
	idle_balance(cpu, rq);

put_prev_task(rq, prev);
next = pick_next_task(rq);     //按照rt,cfs,idle优先级的顺序挑选进程,如果在rt和cfs中都没有找到能够运行的任务,那么当前cpu会切换到idle进程。

这里 PREEMPT_ACTIVE是个标志位,由于进程由于系统调用或者中断异常返回到用户态之前,都要判断是否可以被抢占,会首先判断preempt_count,等于0的时候表示没有禁止抢占,然后再去判断是否标记了need_resched,如果标记了,在去调用schedule函数,如果在某些时候禁止了抢占,禁止了一次就要preempt_count加1。可以肯定的一点是进程的state和是否在运行队列的因果关系并不是十分同步的,修改了进程的状态后,可能还需要做一些其他的工作才去调用schedule函数。引用一下其他人的例子。

1
2
3
4
5
6
for (;;) {
   prepare_to_wait(&wq, &__wait,TASK_UNINTERRUPTIBLE);
   if (condition)
	 break;
   schedule();
}

可以看出在修改了进程的state之后,并不会立刻调用schedule函数,即使立刻调用了schedule函数,也不能保证在schedule函数之前的禁止抢占开启之前有其他的抢占动作。毕竟修改进程的state和从运行队列中移除任务不是一行代码(机器码)就能搞定的事情。所以如果在修改了进程的状态之后和schedule函数禁止抢占之前有抢占动作(可能是中断异常返回),如果这个时候进程被其他进程抢占,这个时候把当前进程移除运行队列,那么这个进程将永远没有机会运行后面的代码。所以这个时候在抢占的过程之前将preempt_count标记PREEMPT_ACTIVE,这样抢占中调用schedule函数将不会从当前运行队列中移除当前进程,这样才有前面分析schedule函数代码,有判断进程state同时判断preempt_count未标记PREEMPT_ACTIVE的情况。

在当前进程被移除出运行队列之前还需要判断是否有挂起的信号需要处理,如果当前进程的状态是TASK_INTERRUPTIBLE或者TASK_WAKEKILL的时候,如果还有信号未处理,那么当前进程就不需要被移除运行队列,并且将state置为running。

1
2
3
4
5
6
7
8
9
static inline int signal_pending_state(long state, struct task_struct *p)
{
	if (!(state & (TASK_INTERRUPTIBLE | TASK_WAKEKILL))) //首先判断状态不是这两个可以处理信号的状态就直接返回0,后面的逻辑不考虑了
		return 0;
	if (!signal_pending(p))             //如果没有信号挂起就不继续了
		return 0;

	return (state & TASK_INTERRUPTIBLE) || __fatal_signal_pending(p); //如果有信号
}
说下 put_prev_task的逻辑,按照道理说应该是rt,cfs,idle的顺序寻找待运行态的任务。
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
pick_next_task(struct rq *rq)
{
	const struct sched_class *class;
	struct task_struct *p;

	/*
	 * Optimization: we know that if all tasks are in
	 * the fair class we can call that function directly:
	 */
	//这里注释的意思都能看懂,如果rq中的cfs队列的运行个数和rq中的运行个数相同,直接调用cfs中 的pick函数,因为默认的调度策略是cfs。
	if (likely(rq->nr_running == rq->cfs.nr_running)) {
		p = fair_sched_class.pick_next_task(rq);
		if (likely(p))
		return p;
	}

	//这里 sched_class_highest就是rt_sched_class,所以前面没有选择出任务,那么从rt开始挑选任务,直到idle
	class = sched_class_highest;
      for ( ; ; ) {
		p = class->pick_next_task(rq);
		if (p)
			return p;
		/*
		 * Will never be NULL as the idle class always
		 * returns a non-NULL p:
		 */
		class = class->next;
	}
}

从每个调度类的代码的最后可以看出这个next关系

sched_rt.c中:

1
2
static const struct sched_class rt_sched_class = {
.next = &fair_sched_class,

sched_fair.c中:

1
2
static const struct sched_class fair_sched_class = {
.next = &idle_sched_class,

那么可以试想如果rt和cfs都没有可以运行的任务,那么最后就是调用idle的pick_next_task函数

sched_idletask.c:

1
2
3
4
5
6
static struct task_struct *pick_next_task_idle(struct rq *rq)
{
	schedstat_inc(rq, sched_goidle);
	calc_load_account_idle(rq);
	return rq->idle;    //可以看到就是返回rq中idle进程。
}

这idle进程在启动start_kernel函数的时候调用init_idle函数的时候,把当前进程(0号进程)置为每个rq的idle上。

kernel/sched.c:5415

1
rq->curr = rq->idle = idle;

这里idle就是调用start_kernel函数的进程,就是0号进程。

0号进程在fork完init进程等之后,进入cpu_idle函数,大概的逻辑是for循环调用hlt指令,每次hlt返回后,调用schedule函数,具体的流程现在还没太看懂,可以看到的是在具体的逻辑在default_idle函数中,调用了safe_halt函数

1
2
3
4
static inline void native_safe_halt(void)
{
	asm volatile("sti; hlt": : :"memory");
}

关于hlt指令的作用是:引用wiki百科

In the x86 computer architecture, HLT (halt) is an assembly language instruction which halts the CPU until the next external interrupt is fired.[1] Interrupts are signals sent by hardware devices to the CPU alerting it that an event occurred to which it should react. For example, hardware timers send interrupts to the CPU at regular intervals.

The HLT instruction is executed by the operating system when there is no immediate work to be done, and the system enters its idle state. In Windows NT, for example, this instruction is run in the “System Idle Process”.

可以看到注释的意思是,hlt指令使得cpu挂起,直到有中断产生这个时候cpu重新开始运行。所以时钟中断会唤醒正在hlt中的cpu,让它调用schedule函数,检测是否有新的任务在rq中,如果有的话切换到新的任务,否则继续执行hlt,cpu继续挂起。

参考文章
1.http://blog.csdn.net/dog250/article/details/5303547

2.http://en.wikipedia.org/wiki/HLT

NMI 看门狗

http://blog.csdn.net/arethe/article/details/6153143

[X86和X86-64体系结构均支持NMI看门狗]

你的系统是不是会经常被锁住(Lock up)?直至解锁,系统不再响应键盘?你希望帮助我们解决类似的问题吗?如果你对所有的问题都回答“yes”,那么此文档正是为你而写。

在很多X86/X86-64结构的硬件上,我们都可以使用一种被称为“看门狗NMI中断”的机制。(NMI:Non Maskable Interrupt. 这种中断即使在系统被锁住时,也能被响应)。这种机制可以被用来调试内核锁住现象。通过周期性地执行NMI中断,内核能够监测到是否有CPU被锁住。当有处理器被锁住时,打印调试信息。

为了使用NMI看门狗,首先需要在内核中支持APIC。对于SMP内核,APIC的相关支持已自动地被编译进内核。对于UP内核,需要在内核配置中使能CONFIG_X86_UP_APIC (Processor type and features -> Local APIC support on uniprocessors) 或 CONFIG_X86_UP_IOAPIC (Processor type and features -> IO-APIC support on uniprocessors)。在没有IO-APIC的单处理器系统中,配置CONFIG_X86_UP_APIC。在有IO-APIC的单处理器系统中,则需配置CONFIG_X86_UP_IOAPIC。[注意:某些与内核调试相关选项可能会禁用NMI看门狗。如:Kernel Stack Meter或Kernel Tracer]。

对于X86-64系统,APIC已被编进内核。

使用本地APIC(nmi_watchdog=2)时,需要占用第一个性能寄存器,因而此寄存器不能再被另作它用(如高精度的性能分析)。Oprofile与perfctr的驱动已自动地禁用了本地APIC的NMI看门狗。

可以通过启动参数“nmi_watchdog=N”使能NMI看门狗。即在lilo.conf的相关项中添加如下语句:

1
  append=”nmi_watchdog=1”

对于具有IO-APIC的SMP与UP机器,设置nmi_watchdog=1。对于没有IO-APIC的UP机器,设置nmi_watchdog=2,但仅在某些处理器上可以起作用。如果有疑问,在用nmi_watchdog=1启动后,再查看/proc/interrupts文件中的NMI项,如果该项为0,那么便用nmi_watchdog=2重新启动,并再次检查NMI项。如果还是0,问题就比较严重了,你的处理器很可能不支持NMI。

“锁住(Lockup)”是指如下的情况:如果系统中的任何一个CPU不能处理周期性的本地时钟中断,并持续5秒钟以上,那么NMI的处理函数将产生一个oops并杀死当前进程。这是一种“可控崩溃”(Controlled Crash,所谓可控,是指发生崩溃时,能够输出内核信息),可以用此机制来调试“锁住”现象。那么,无论什么时候发生“锁住”,5秒钟之后都会自动地输出oops。如果内核没有输出信息,说明此时发生的崩溃过于严重(如:hardware-wise),以至于NMI中断都无法被响应,或者此次崩溃使得内核无法打印信息。

在使用本地APIC时要注意,NMI中断被触发的频率依赖于系统的当前负载。由于缺乏更好的时钟源,本地APIC中的NMI看门狗使用的是“有效周期(Cycle unhalted,这个词的翻译似乎不太确切,如果某位朋友有更佳的建议,请告知在下。)”事件。也许你已经猜到了,当CPU处于halted(空等)状态时,该时钟是不计数的。处理器处于空闲状态的时候,常出现这样的情况。如果你的系统在被锁住时,执行的不是hlt指令,看门狗中断很快就会被触发,因为每个时钟周期都会发生“有效周期”事件。如果不幸,处理器在被锁住时,执行的恰是“hlt”指令,那么“有效周期”事件永远都不会发生,看门狗自然也不会被触发。这是本地APIC看门狗的缺陷,在倒霉的时候,永远不会进行时钟计数。而I/O APIC中的看门狗由于采用外部时钟进行驱动,便不存在这个缺陷。但是,它的NMI频率非常高,会显著地影响系统的性能。

X86的nmi_watchdog在默认情况下是禁用的,因此你需要在系统启动的时候使能它。

在系统运行期间,可以禁用NMI看门狗,只要向文件“/proc/sys/kernel/nmi_watchdog”中写“0”即可。向该文件写“1”,将重新使能看门狗。即使如此,你仍然需要在启动时使用参数“nmi_watchdog=”。

注意:在2.4.2-ac18之前的内核中,X86 SMP平台会无条件地使能NMI-oopser。


www.2cto.com/kf/201311/260704.html

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
//  使能hard lockup探测
//  调用路径:watchdog_enable->watchdog_nmi_enable
//  函数任务:
//      1.初始化hard lockup检测事件
//          2.hard lockup阈值为10s
//      2.向performance monitoring子系统注册hard lockup检测事件
//      3.使能hard lockup检测事件
//  注:
//      performance monitoring,x86中的硬件设备,当cpu clock经过了指定个周期后发出一个NMI中断。
1.1 static int watchdog_nmi_enable(unsigned int cpu)
{
	//hard lockup事件
	struct perf_event_attr *wd_attr;
	struct perf_event *event = per_cpu(watchdog_ev, cpu);
	....
	wd_attr = &wd_hw_attr;
	//hard lockup检测周期,10s
	wd_attr->sample_period = hw_nmi_get_sample_period(watchdog_thresh);
	//向performance monitoring注册hard lockup检测事件
	event = perf_event_create_kernel_counter(wd_attr, cpu, NULL, watchdog_overflow_callback, NULL);
	....
	//使能hard lockup的检测
	per_cpu(watchdog_ev, cpu) = event;
	perf_event_enable(per_cpu(watchdog_ev, cpu));
	return 0;
}
 
//  换算hard lockup检测周期到cpu频率
1.2 u64 hw_nmi_get_sample_period(int watchdog_thresh)
{
	return (u64)(cpu_khz) * 1000 * watchdog_thresh;
}
 
//  hard lockup检测事件发生时的nmi回调函数
//  函数任务:
//      1.判断是否发生了hard lockup
//          1.1 dump hard lockup信息
1.3 static void watchdog_overflow_callback(struct perf_event *event,
	 struct perf_sample_data *data,
	 struct pt_regs *regs)
{
	//判断是否发生hard lockup
	if (is_hardlockup()) {
		int this_cpu = smp_processor_id();
 
		//打印hard lockup信息
		if (hardlockup_panic)
			panic("Watchdog detected hard LOCKUP on cpu %d", this_cpu);
		else
			WARN(1, "Watchdog detected hard LOCKUP on cpu %d", this_cpu);
 
		return;
	}
	return;
}
 
//  判断是否发生hard lockup
//  注:
//      如果时钟中断在指定阈值范围内为运行,核心认为可屏蔽中断被屏蔽时间过长
1.4 static int is_hardlockup(void)
{
	//获取watchdog timer的运行次数
	unsigned long hrint = __this_cpu_read(hrtimer_interrupts);
	//在一个hard lockup检测时间阈值内,如果watchdog timer未运行,说明cpu中断被屏蔽时间超过阈值
	if (__this_cpu_read(hrtimer_interrupts_saved) == hrint)
		return 1;
	//记录watchdog timer运行的次数
	__this_cpu_write(hrtimer_interrupts_saved, hrint);
	return 0;
}
 
//  关闭hard lockup检测机制
//  函数任务:
//      1.向performance monitoring子系统注销hard lockup检测控制块
//      2.清空per-cpu hard lockup检测控制块
//      3.释放hard lock检测控制块
2.1 static void watchdog_nmi_disable(unsigned int cpu)
{
	struct perf_event *event = per_cpu(watchdog_ev, cpu);
	if (event) {
		//向performance monitoring子系统注销hard lockup检测控制块
		perf_event_disable(event);
		//清空per-cpu hard lockup检测控制块
		per_cpu(watchdog_ev, cpu) = NULL;
		//释放hard lock检测控制块
		perf_event_release_kernel(event);
	}
	return;
}