Linux內核分析之調度算法

linux調度算法在2.6.32中采用調度類實現模塊式的調度方式。這樣，能夠很好的加入新的調度算法。

linux調度器是以模塊方式提供的，這樣做的目的是允許不同類型的進程可以有針對性地選擇調度算法。這種模塊化結構被稱為調度器類，他允許多種不同哦可動態添加的調度算法並存，調度屬於自己范疇的進程。每個調度器都有一個優先級，調度代碼會按照優先級遍歷調度類，擁有一個可執行進程的最高優先級的調度器類勝出，去選擇下面要執行的那個程序。

linux上主要有兩大類調度算法，CFS(完全公平調度算法）和實時調度算法。宏SCHED_NOMAL主要用於CFS調度，而SCHED_FIFO和SCHED_RR主要用於實時調度。如下面的宏定義：

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

linux調度算法實現的高層數據結構主要有運行實體、調度類、運行隊列，下面我們主要看看這幾個數據結構的字段和意義。

運行實體，rq結構體每個cpu有一個，主要存儲一些基本的用於調度的信息，包括實時調度的和CFS調度的

1. /*每個處理器都會配置一個rq*/
2. struct rq {
3. /* runqueue lock: */
4. spinlock_t lock;
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. /*用以記錄目前處理器rq中執行task的數量*/
11. unsigned long nr_running;
12. #define CPU_LOAD_IDX_MAX 5
13. /*用以表示處理器的負載，在每個處理器的rq中
14. 都會有對應到該處理器的cpu_load參數配置，在每次
15. 處理器觸發scheduler tick時，都會呼叫函數
16. update_cpu_load_active,進行cpu_load的更新。在系統初始化的時候
17. 會呼叫函數sched_init把rq的cpu_load array初始化為0.
18. 了解他的更新方式最好的方式是通過函數update_cpu_load,公式如下澹?
19. cpu_load[0]會直接等待rq中load.weight的值。
20. cpu_load[1]=(cpu_load[1]*(2-1)+cpu_load[0])/2
21. cpu_load[2]=(cpu_load[2]*(4-1)+cpu_load[0])/4
22. cpu_load[3]=(cpu_load[3]*(8-1)+cpu_load[0])/8
23. cpu_load[4]=(cpu_load[4]*(16-1)+cpu_load[0]/16
24. 呼叫函數this_cpu_load時，所返回的cpu load值是cpu_load[0]
25. 而在進行cpu blance或migration時，就會呼叫函數
26. source_load target_load取得對該處理器cpu_load index值，
27. 來進行計算*/
28. unsigned long cpu_load[CPU_LOAD_IDX_MAX];
29. #ifdef CONFIG_NO_HZ
30. unsigned long last_tick_seen;
31. unsigned char in_nohz_recently;
32. #endif
33. /* capture load from *all* tasks on this cpu: */
34. /*load->weight值，會是目前所執行的schedule entity的
35. load->weight的總和，也就是說rq的load->weight越高，
36. 也表示所負責的排程單元load->weight總和越高
37. 表示處理器所負荷的執行單元也越重*/
38. struct load_weight load;
39. /*在每次scheduler tick中呼叫update_cpu_load時，
40. 這個值就增加一，可以用來反饋目前cpu
41. load更新的次數*/
42. unsigned long nr_load_updates;
43. /*用來累加處理器進行context switch的次數，會在
44. 函數schedule呼叫時進行累加，並可以通過函數
45. nr_context_switches統計目前所有處理器總共的context switch
46. 次數，或是可以透過查看檔案/proc/stat中的ctxt位得知目前
47. 整個系統觸發context switch的次數*/
48. u64 nr_switches;
50. u64 nr_migrations_in;
51. /*為cfs fair scheduling class 的rq*/
52. struct cfs_rq cfs;
53. /*為real-time scheduling class 的rq*/
54. struct rt_rq rt;
56. /*用以支援可以group cfs tasks的機制*/
57. #ifdef CONFIG_FAIR_GROUP_SCHED
58. /* list of leaf cfs_rq on this cpu: */
59. /*在有設置fair group scheduling 的環境下，
60. 會基於原本cfs rq中包含有若干task的group
61. 所成的排程集合，也就是說當有一個group a
62. 就會有自己的cfs rq用來排程自己所屬的tasks,
63. 而屬於這group a的tasks所使用到的處理器時間
64. 就會以這group a總共所分的的時間為上限。
65. 基於cgroup的fair group scheduling 架構，可以創造出
66. 有階層性的task組織，根據不同task的功能群組化
67. 在配置給該群主對應的處理器資源，讓屬於
68. 該群主下的task可以透過rq機制排程。使用屬於
69. 該群主下的資源。
70. 這個變數主要是管理CFS RQ list，操作上可以透過函數
71. list_add_leaf_cfs_rq把一個group cfs rq加入到list中，或透過
72. 函數list_del_leaf_cfs_rq把一個group cfs rq移除，並可以
73. 透過for_each_leaf_cfs_rq把一個rq上得所有leaf cfs_rq走一遍
74. */
75. struct list_head leaf_cfs_rq_list;
76. #endif
77. /*用以支援可以group real-time tasks的機制*/
78. #ifdef CONFIG_RT_GROUP_SCHED
79. /*類似leaf_cfs_rq_list所扮演的角色，只是這裡
80. 是針對屬於real-time的task,在實際操作上可以
81. 透過函數list_add_leaf_rt_rq,list_del_leaf_rt_rq或
82. 巨集for_each_leaf_rt_rq*/
83. struct list_head leaf_rt_rq_list;
84. #endif
86. /*
87. * This is part of a global counter where only the total sum
88. * over all CPUs matters. A task can increase this counter on
89. * one CPU and if it got migrated afterwards it may decrease
90. * it on another CPU. Always updated under the runqueue lock:
91. */
92. /*一般來說，linux kernel 的task狀態可以為TASK_RUNNING
93. TASK_INTERRUPTIBLE(sleep),
94. TASK_UNINTERRUPTIBLE(Deactivate Task,此時Task會從rq中
95. 移除)或TASK_STOPPED.
96. 透過這個變數會統計目前rq中有多少task屬於
97. TASK_UNINTERRUPTIBLE的狀態。當呼叫函數
98. active_task時，會把nr_uninterruptible值減一，並透過 該函數
99. enqueue_task把對應的task依據所在的scheduling class
100. 放在 對應的rq中，並把目前rq中nr_running值加一*/
101. unsigned long nr_uninterruptible;
102. /*curr:指向目前處理器正在執行的task;
103. idle:指向屬於idle-task scheduling class 的idle task;
104. stop:指向目前最高等級屬於stop-task scheduling class
105. 的task;*/
106. struct task_struct *curr, *idle;
107. /*基於處理器的jiffies值，用以記錄下次進行處理器
108. balancing 的時間點*/
109. unsigned long next_balance;
110. /*用以存儲context-switch發生時，前一個task的memory management
111. 結構並可用在函數finish_task_switch中，透過函數mmdrop釋放前一個
112. task的記憶體資源*/
113. struct mm_struct *prev_mm;
114. /*用以記錄目前rq的clock值，基本上該值會等於透過sched_clock_cpu
115. (cpu_of(rq))的回傳值，並會在每次呼叫scheduler_tick時透過
116. 函數update_rq_clock更新目前rq clock值。
117. 在實作部分，函數sched_clock_cpu會透過sched_clock_local或
118. ched_clock_remote取得對應的sched_clock_data,而處理的sched_clock_data
119. 值，會透過函數sched_clock_tick在每次呼叫scheduler_tick時進行更新；
120. */
121. u64 clock;
122. /*用以記錄目前rq中有多少task處於等待i/o的sleep狀態
123. 在實際的使用上，例如當driver接受來自task的調用，但處於等待i/o
124. 回復的階段時，為了充分利用處理器的執行資源，這時
125. 就可以在driver中呼叫函數io_schedule，此時
126. 就會把目前rq中的nr_iowait加一，並設定目前task的io_wait為1
127. 然後觸發scheduling 讓其他task有機會可以得到處理器執行時間*/
128. atomic_t nr_iowait;
130. #ifdef CONFIG_SMP
131. /*root domain是基於多核心架構下的機制，
132. 會由rq結構記住目前采用的root domain，其中包括了
133. 目前的cpu mask(包括span,online rt overload), reference count 跟cpupri
134. 當root domain有被rq參考到時，refcount 就加一，反之就減一。而cpu
135. mask span表示rq可掛上的cpu mask,noline為rq目前已經排程的
136. cpu mask cpu上執行real-time task.可以參考函數pull_rt_task，當一個rq中屬於
137. real-time的task已經執行完畢，就會透過函數pull_rt_task從該
138. rq中屬於rto_mask cpu mask 可以執行的處理器上，找出是否有一個處理器
139. 有大於一個以上的real-time task，若有就會轉到目前這個執行完成
140. real-time task 的處理器上
141. 而cpupri不同於Task本身有區分140個(0-139)
142. Task Priority (0-99為RT Priority 而 100-139為Nice值 -20-19).
143. CPU Priority本身有102個Priority (包括,-1 為Invalid,
144. 0為Idle,1為Normal,2-101對應到Real-Time Priority 0-99).
145. 參考函式convert_prio, Task Priority如果是 140就會對應到
146. CPU Idle,如果是大於等於100就會對應到CPU Normal,
147. 若是Task Priority介於0-99之間,就會對應到CPU Real-Time Priority 101-2之間.)
148. 在實際的操作上,例如可以透過函式cpupri_find
149. 帶入一個要插入的Real-Time Task,此時就會依據cpupri中
150. pri_to_cpu選擇一個目前執行Real-Time Task且該Task
151. 的優先級比目前要插入的Task更低的處理器,
152. 並透過CPU Mask(lowest_mask)返回目前可以選擇的處理器Mask.
153. 實作的部份可以參考檔案kernel/sched_cpupri.c.
154. 在初始化的過程中,會透過函式sched_init呼叫函式init_defrootdomain,
155. 對Root Domain與 CPU Priority機制進行初始化.
156. */
157. struct root_domain *rd;
158. /*Schedule Domain是基於多核心架構下的機制.
159. 每個處理器都會有一個基礎的Scheduling Domain,
160. Scheduling Domain可以有階層性的架構,透過parent
161. 可以找到上一層的Domain,或是透過child找到
162. 下一層的 Domain (NULL表示結尾.).並可透過span
163. 欄位,表示這個Domain所能涵蓋的處理器範圍.
164. 通常Base Domain會涵蓋系統中所有處理器的個數,
165. 而Child Domain所能涵蓋的處理器個數不超過它的
166. Parent Domain. 而當在進行Scheduling Domain 中的Task Balance
167. 時,就會以該Domain所能涵蓋的處理器為最大範圍.
168. 同時,每個Schedule Domain都會包括一個或一個以上的
169. CPU Groups (結構為struct sched_group),並透過next變數把
170. CPU Groups串連在一起(成為一個單向的Circular linked list),
171. 每個CPU Group都會有變數cpumask來定義這個CPU Group
172. 所涵蓋的處理器範圍.並且CPU Group所包括的處理器
173. 範圍,必需涵蓋在所屬的Schedule Domain處理器範圍中.
174. 當進行Scheduling Domain的Balancing時,會以其下的CPU Groups
175. 為單位,根據cpu_power （會是該Group所涵蓋的處理器
176. Tasks Loading的總和）來比較不同的CPU Groups的負荷,
177. 以進行Tasks的移動,達到Balancing的目的.
178. 在有支援SMP的架構下,會在函式sched_init中,呼叫open_softirq,
179. 註冊 SCHED_SOFTIRQ Software IRQ與其對應的 Callback函式
180. run_rebalance_domains. 並會在每次呼叫函式scheduler_tick時,
181. 透過函式trigger_load_balance確認是否目前的jiffies值已經
182. 大於RunQueue下一次要觸發Load Balance的next_balance時間值,
183. 並透過函式raise_softirq觸發SCHED_SOFTIRQ Software IRQ.
184. 在Software IRQ觸發後,就會呼叫函式run_rebalance_domains,
185. 並在函式rebalance_domains中,進行後續處理器上的
186. Scheduling Domain Load Balance動作.
187. 有關Scheduling Domain進一步的內容,也可以參考
188. Linux Kernel文件 Documentation/scheduler/sched-domains.txt.
189. */
190. struct sched_domain *sd;
191. /*這值會等於函式idle_cpu的返回值,如果為1表示
192. 目前CPU RunQueue中執行的為Idle Task. 反之為0,
193. 則表示處理器執行的不是Idle Task (也就是說
194. 處理器正在忙碌中.).*/
195. unsigned char idle_at_tick;
196. /* For active balancing */
197. /*若這值不為0,表示會有在Schedule排程動作
198. 結束前,要呼叫的收尾函式. (實作為inline函式
199. post_schedule in kernel/sched.c),目前只有Real-Time Scheduling
200. Class有支援這個機制(會呼叫函式has_pushable_tasks
201. in kernel/sched_rt.c).*/
202. int post_schedule;
203. /*當RunQueue中此值為1,表示這個RunQueue正在進行
204. Fair Scheduling的Load Balance,此時會呼叫stop_one_cpu_nowait
205. 暫停該RunQueue所屬處理器的排程,並透過函式
206. active_load_balance_cpu_stop,把Tasks從最忙碌的處理器,
207. 移到Idle的處理器上執行.*/
208. int active_balance;
209. /*用以儲存目前進入Idle且負責進行 Load Balance
210. 流程的處理器ID. 呼叫的流程為,在呼叫函式schedule時,
211. 若該處理器RunQueue的nr_running為0 (也就是目前沒有
212. 正在執行的Task),就會呼叫idle_balance,並觸發後續Load
213. Balance流程.*/
214. int push_cpu;
215. /* cpu of this runqueue: */
216. /*用以儲存目前運作這個RunQueue的處理器ID*/
217. int cpu;
218. /*為1表示目前此RunQueue有在對應的處理器掛上
219. 並執行.*/
220. int online;
221. /*如果RunQueue中目前有Task正在執行,這個值會
222. 等於目前該RunQueue的Load Weight除以目前RunQueue
223. 中Task數目的均值.
224. (rq->avg_load_per_task = rq->load.weight / nr_running;).*/
225. unsigned long avg_load_per_task;
227. struct task_struct *migration_thread;
228. struct list_head migration_queue;
229. /*這個值會由Real-Time Scheduling Class呼叫函式
230. update_curr_rt,用以統計目前Real-Time Task執行時間的
231. 均值,在這函式中會以目前RunQueue的clock_task
232. 減去目前Task執行的起始時間,取得執行時間的
233. Delta值. (delta_exec = rq->clock_task – curr->se.exec_start; ).
234. 在透過函式sched_rt_avg_update把這Delta值跟原本
235. RunQueue中的rt_avg值取平均值. 以運作的週期來看,
236. 這個值可反應目前系統中Real-Time Task平均被
237. 分配到的執行時間值.*/
238. u64 rt_avg;
239. /*這個值主要在函式sched_avg_update更新,以筆者手中
240. 的Linux Kernel 2.6.38.6的實作來說,當RunQueue Clock
241. 減去age_stamp大於 0.5秒 (=sched_avg_period),就會把這值
242. 累加0.5秒 (單位都是nanoseconds). 從函式scale_rt_power
243. 的實作來說,age_stamp值離RunQueue Clock越遠,表示total
244. 值越大,available值也越大,而函式scale_rt_power返回的
245. div_u64計算結果也越大,最終 RunQueue的cpu_power
246. 與Scheduling Domain中的Scheduling Group的cpu_power
247. 值也就越大. (可參考函式update_cpu_power的實作).*/
248. u64 age_stamp;
249. /*這值會在觸發Scheduling時,若判斷目前處理器
250. RunQueue沒有正在運作的Task,就會透過函式
251. idle_balance更新這值為為目前RunQueue的clock值.
252. 可用以表示這個處理器是何時進入到Idle的
253. 狀態*/
254. u64 idle_stamp;
255. /*會在有Task運作且idle_stamp不為0 (表示前一個
256. 狀態是在Idle)時以目前RunQueue的clock減去
257. idle_stmp所計算出的Delta值為依據,更新這個值
258. . 可反應目前處理器進入Idle狀態的時間長短*/
259. u64 avg_idle;
260. #endif
262. /* calc_load related fields */
263. /*用以記錄下一次計算CPU Load的時間,初始值
264. 為目前的jiffies加上五秒與1次的Scheduling Tick的
265. 間隔 (=jiffies + LOAD_FREQ,且LOAD_FREQ=(5*HZ+1))*/
266. unsigned long calc_load_update;
267. /*會等於RunQueue中nr_running與nr_uninterruptible的
268. 總和.（可參考函式calc_load_fold_active）.*/
269. long calc_load_active;
271. #ifdef CONFIG_SCHED_HRTICK
272. #ifdef CONFIG_SMP
273. /*在函式init_rq_hrtick初始化RunQueue High-Resolution
274. Tick時,此值預設為0.
275. 在函式hrtick_start中,會判斷目前觸發的RunQueue
276. 跟目前處理器所使用的RunQueue是否一致,
277. 若是,就直接呼叫函式hrtimer_restart,反之就會
278. 依據RunQueue中hrtick_csd_pending的值,如果
279. hrtick_csd_pending為0,就會透過函式
280. __smp_call_function_single讓RunQueue所在的另一個
281. 處理器執行rq->hrtick_csd.func 所指到的函式
282. __hrtick_start. 並等待該處理器執行完畢後,
283. 才重新把hrtick_csd_pending設定為1.
284. 也就是說, RunQueue的hrtick_csd_pending是用來作為
285. SMP架構下,由處理器A觸發處理器B執行
286. _hrtick_start函式的一個保護機制.而有關在
287. SMP下如何由一個處理器觸發另一個處理器
288. 執行函式的機制,可以參考kernel/smp.c中
289. 相關smp_call_function_xxxxxxx的實作.s*/
290. int hrtick_csd_pending;
291. /*用以儲存hrtick機制中,要跨處理器執行的
292. 函式結構.*/
293. struct call_single_data hrtick_csd;
294. #endif
295. /*為High-Resolution Tick的結構,會透過函式
296. hrtimer_init初始化.*/
297. struct hrtimer hrtick_timer;
298. #endif
300. #ifdef CONFIG_SCHEDSTATS
301. /* latency stats */
302. /*為Scheduling Info.的統計結構,可以參考
303. include/linux/sched.h中的宣告. 例如在每次觸發
304. Schedule時,呼叫函式schedule_debug對上一個Task
305. 的lock_depth進行確認(Fork一個新的Process 時,
306. 會把此值預設為-1就是No-Lock,當呼叫
307. Kernel Lock時, 就會把Current Task的lock_depth加一.),
308. 若lock_depth>=0,就會累加Scheduling Info.的bkl_count值,
309. 用以代表Task Blocking的次數.*/
310. struct sched_info rq_sched_info;
311. /*可用以表示RunQueue中的Task所得到CPU執行
312. 時間的累加值.
313. 在發生Task Switch時,會透過sched_info_switch呼叫
314. sched_info_arrive並以目前RunQueue Clock值更新
315. Task 的sched_info.last_arrival時間,而在Task所分配時間
316. 結束後,會在函式sched_info_depart中以現在的
317. RunQueue Clock值減去Task的sched_info.last_arrival
318. 時間值,得到的 Delta作為變數rq_cpu_time的累
319. 加值.*/
320. unsigned long long rq_cpu_time;
321. /* could above be rq->cfs_rq.exec_clock + rq->rt_rq.rt_runtime ? */
323. /* sys_sched_yield() stats */
324. /*用以統計呼叫System Call sys_sched_yield的次數.*/
325. unsigned int yld_count;
327. /* schedule() stats */
328. unsigned int sched_switch;
329. /*可用以統計觸發Scheduling的次數. 在每次觸發
330. Scheduling時,會透過函式schedule呼叫schedule_debug,
331. 呼叫schedstat_inc對這變數進行累加.*/
332. unsigned int sched_count;
333. /*可用以統計進入到Idle Task的次數. 會在函式
334. pick_next_task_idle中,呼叫schedstat_inc對這變數進行
335. 累加.*/
336. unsigned int sched_goidle;
338. /* try_to_wake_up() stats */
339. /*用以統計Wake Up Task的次數.*/
340. unsigned int ttwu_count;
341. /*用以統計Wake Up 同一個處理器Task的次數.*/
342. unsigned int ttwu_local;
344. /* BKL stats */
345. unsigned int bkl_count;
346. #endif
347. };