Linux内核分析之调度算法.doc

Linux内核分析之调度算法inux调度算法在2.6.32中采用调度类实现模块式的调度方式。这样，能够很好的加入新的调度算法。linux调度器是以模块方式提供的，这样做的目的是允许不同类型的进程可以有针对性地选择调度算法。这种模块化结构被称为调度器类，他允许多种不 同哦可动态添加的调度算法并存，调度属于自己范畴的进程。每个调度器都有一个优先级，调度代码会按照优先级遍历调度类，拥有一个可执行进程的最高优先级的 调度器类胜出，去选择下面要执行的那个程序。linux上主要有两大类调度算法，CFS(完全公平调度算法）和实时调度算法。宏SCHED_NOMAL主要用于CFS调度，而SCHED_FIFO和SCHED_RR主要用于实时调度。如下面的宏定义：1. /*2. *Schedulingpolicies3. */4. /*支援Real-TimeTask的排程,包括有SCHED_FIFO與SCHED_RR.5. */6. 7. /*(也稱為SCHED_OTHER):主要用以排程8. 一般目的的Task.*/9. #defineSCHED_NORMAL0 10. #defineSCHED_FIFO1 11. /*task預設的TimeSlice長度為100msecs*/12. #defineSCHED_RR2 13. /*主要用以讓Task可以延長執行的時間14. (TimeSlice),減少被中斷發生TaskContext-Switch15. 的次數.藉此可以提高Cache的利用率16. (每次Context-Switch都會導致Cache-Flush).比17. 較適合用在固定週期執行的BatchJobs任18. 務主機上,而不適合用在需要使用者互19. 動的產品(會由於Task切換的延遲,而20. 感覺到系統效能不佳或是反應太慢).*/21. #defineSCHED_BATCH3 22. /*SCHED_ISO:reservedbutnotimplementedyet*/23. /*為系統中的IdleTask排程.*/24. #defineSCHED_IDLE5linux调度算法实现的高层数据结构主要有运行实体、调度类、运行队列，下面我们主要看看这几个数据结构的字段和意义。运行实体，rq结构体每个cpu有一个，主要存储一些基本的用于调度的信息，包括实时调度的和CFS调度的1. /*每个处理器都会配置一个rq*/2. structrq3. /*runqueuelock:*/4. spinlock_tlock;5. 6. /*7. *nr_runningandcpu_loadshouldbeinthesamecachelinebecause8. *remoteCPUsuseboththesefieldswhendoingloadcalculation.9. */10. /*用以记录目前处理器rq中执行task的数量*/11. unsignedlongnr_running;12. #defineCPU_LOAD_IDX_MAX5 13. /*用以表示处理器的负载，在每个处理器的rq中14. 都会有对应到该处理器的cpu_load参数配置，在每次15. 处理器触发schedulertick时，都会呼叫函数16. update_cpu_load_active,进行cpu_load的更新。在系统初始化的时候17. 会呼叫函数sched_init把rq的cpu_loadarray初始化为0.18. 了解他的更新方式最好的方式是通过函数update_cpu_load,公式如下澹?19. cpu_load0会直接等待rq中load.weight的值。20. cpu_load1=(cpu_load1*(2-1)+cpu_load0)/221. cpu_load2=(cpu_load2*(4-1)+cpu_load0)/422. cpu_load3=(cpu_load3*(8-1)+cpu_load0)/823. cpu_load4=(cpu_load4*(16-1)+cpu_load0/1624. 呼叫函数this_cpu_load时，所返回的cpuload值是cpu_load025. 而在进行cpublance或migration时，就会呼叫函数26. source_loadtarget_load取得对该处理器cpu_loadindex值，27. 来进行计算*/28. unsignedlongcpu_loadCPU_LOAD_IDX_MAX;29. #ifdefCONFIG_NO_HZ 30. unsignedlonglast_tick_seen;31. unsignedcharin_nohz_recently;32. #endif 33. /*captureloadfrom*all*tasksonthiscpu:*/34. /*load-weight值，会是目前所执行的scheduleentity的35. load-weight的总和，也就是说rq的load-weight越高，36. 也表示所负责的排程单元load-weight总和越高37. 表示处理器所负荷的执行单元也越重*/38. structload_weightload;39. /*在每次schedulertick中呼叫update_cpu_load时，40. 这个值就增加一，可以用来反馈目前cpu41. load更新的次数*/42. unsignedlongnr_load_updates;43. /*用来累加处理器进行contextswitch的次数，会在44. 函数schedule呼叫时进行累加，并可以通过函数45. nr_context_switches统计目前所有处理器总共的contextswitch46. 次数，或是可以透过查看档案/proc/stat中的ctxt位得知目前47. 整个系统触发contextswitch的次数*/48. u64nr_switches;49. 50. u64nr_migrations_in;51. /*为cfsfairschedulingclass的rq*/52. structcfs_rqcfs;53. /*为real-timeschedulingclass的rq*/54. structrt_rqrt;55. 56. /*用以支援可以groupcfstasks的机制*/57. #ifdefCONFIG_FAIR_GROUP_SCHED 58. /*listofleafcfs_rqonthiscpu:*/59. /*在有设置fairgroupscheduling的环境下，60. 会基于原本cfsrq中包含有若干task的group61. 所成的排程集合，也就是说当有一个groupa62. 就会有自己的cfsrq用来排程自己所属的tasks,63. 而属于这groupa的tasks所使用到的处理器时间64. 就会以这groupa总共所分的的时间为上限。65. 基于cgroup的fairgroupscheduling架构，可以创造出66. 有阶层性的task组织，根据不同task的功能群组化67. 在配置给该群主对应的处理器资源，让属于68. 该群主下的task可以透过rq机制排程。使用属于69. 该群主下的资源。70. 这个变数主要是管理CFSRQlist，操作上可以透过函数71. list_add_leaf_cfs_rq把一个groupcfsrq加入到list中，或透过72. 函数list_del_leaf_cfs_rq把一个groupcfsrq移除，并可以73. 透过for_each_leaf_cfs_rq把一个rq上得所有leafcfs_rq走一遍74. */75. structlist_headleaf_cfs_rq_list;76. #endif 77. /*用以支援可以groupreal-timetasks的机制*/78. #ifdefCONFIG_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. structlist_headleaf_rt_rq_list;84. #endif 85. 86. /*87. *Thisispartofaglobalcounterwhereonlythetotalsum88. *overallCPUsmatters.Ataskcanincreasethiscounteron89. *oneCPUandifitgotmigratedafterwardsitmaydecrease90. *itonanotherCPU.Alwaysupdatedundertherunqueuelock:91. */92. /*一般来说，linuxkernel的task状态可以为TASK_RUNNING93. TASK_INTERRUPTIBLE(sleep),94. TASK_UNINTERRUPTIBLE(DeactivateTask,此时Task会从rq中95. 移除)或TASK_STOPPED.96. 透过这个变数会统计目前rq中有多少task属于97. TASK_UNINTERRUPTIBLE的状态。当呼叫函数98. active_task时，会把nr_uninterruptible值减一，并透过该函数99. enqueue_task把对应的task依据所在的schedulingclass100. 放在对应的rq中，并把目前rq中nr_running值加一*/101. unsignedlongnr_uninterruptible;102. /*curr:指向目前处理器正在执行的task;103. idle:指向属于idle-taskschedulingclass的idletask;104. stop:指向目前最高等级属于stop-taskschedulingclass105. 的task;*/106. structtask_struct*curr,*idle;107. /*基于处理器的jiffies值，用以记录下次进行处理器108. balancing的时间点*/109. unsignedlongnext_balance;110. /*用以存储context-switch发生时，前一个task的memorymanagement111. 结构并可用在函数finish_task_switch中，透过函数mmdrop释放前一个112. task的记忆体资源*/113. structmm_struct*prev_mm;114. /*用以记录目前rq的clock值，基本上该值会等于透过sched_clock_cpu115. (cpu_of(rq)的回传值，并会在每次呼叫scheduler_tick时透过116. 函数update_rq_clock更新目前rqclock值。117. 在实作部分，函数sched_clock_cpu会透过sched_clock_local或118. ched_clock_remote取得对应的sched_clock_data,而处理的sched_clock_data119. 值，会透过函数sched_clock_tick在每次呼叫scheduler_tick时进行更新；120. */121. u64clock;122. /*用以记录目前rq中有多少task处于等待i/o的sleep状态123. 在实际的使用上，例如当driver接受来自task的调用，但处于等待i/o124. 回复的阶段时，为了充分利用处理器的执行资源，这时125. 就可以在driver中呼叫函数io_schedule，此时126. 就会把目前rq中的nr_iowait加一，并设定目前task的io_wait为1127. 然后触发scheduling让其他task有机会可以得到处理器执行时间*/128. atomic_tnr_iowait;129. 130. #ifdefCONFIG_SMP 131. /*rootdomain是基于多核心架构下的机制，132. 会由rq结构记住目前采用的rootdomain，其中包括了133. 目前的cpumask(包括span,onlinertoverload),referencecount跟cpupri134. 当rootdomain有被rq参考到时，refcount就加一，反之就减一。而cpu135. maskspan表示rq可挂上的cpumask,noline为rq目前已经排程的136. cpumaskcpu上执行real-timetask.可以参考函数pull_rt_task，当一个rq中属于137. real-time的task已经执行完毕，就会透过函数pull_rt_task从该138. rq中属于rto_maskcpumask可以执行的处理器上，找出是否有一个处理器139. 有大于一个以上的real-timetask，若有就会转到目前这个执行完成140. real-timetask的处理器上141. 而cpupri不同于Task本身有区分140個(0-139)142. TaskPriority(0-99為RTPriority而100-139為Nice值-20-19).143. CPUPriority本身有102個Priority(包括,-1為Invalid,144. 0為Idle,1為Normal,2-101對應到Real-TimePriority0-99).145. 參考函式convert_prio,TaskPriority如果是140就會對應到146. CPUIdle,如果是大於等於100就會對應到CPUNormal,147. 若是TaskPriority介於0-99之間,就會對應到CPUReal-TimePriority101-2之間.)148. 在實際的操作上,例如可以透過函式cpupri_find149. 帶入一個要插入的Real-TimeTask,此時就會依據cpupri中150. pri_to_cpu選擇一個目前執行Real-TimeTask且該Task151. 的優先級比目前要插入的Task更低的處理器,152. 並透過CPUMask(lowest_mask)返回目前可以選擇的處理器Mask.153. 實作的部份可以參考檔案kernel/sched_cpupri.c.154. 在初始化的過程中,會透過函式sched_init呼叫函式init_defrootdomain,155. 對RootDomain與CPUPriority機制進行初始化.156. */157. structroot_domain*rd;158. /*ScheduleDomain是基於多核心架構下的機制.159. 每個處理器都會有一個基礎的SchedulingDomain,160. SchedulingDomain可以有階層性的架構,透過parent161. 可以找到上一層的Domain,或是透過child找到162. 下一層的Domain(NULL表示結尾.).並可透過span163. 栏位,表示這個Domain所能涵蓋的處理器範圍.164. 通常BaseDomain會涵蓋系統中所有處理器的個數,165. 而ChildDomain所能涵蓋的處理器個數不超過它的166. ParentDomain.而當在進行SchedulingDomain中的TaskBalance167. 時,就會以該Domain所能涵蓋的處理器為最大範圍.168. 同時,每個ScheduleDomain都會包括一個或一個以上的169. CPUGroups(結構為structsched_group),並透過next變數把170. CPUGroups串連在一起(成為一個單向的Circularlinkedlist),171. 每個CPUGroup都會有變數cpumask來定义這個CPUGroup172. 所涵蓋的處理器範圍.並且CPUGroup所包括的處理器173. 範圍,必需涵蓋在所屬的ScheduleDomain處理器範圍中.174. 當進行SchedulingDomain的Balancing時,會以其下的CPUGroups175. 為單位,根據cpu_power（會是該Group所涵蓋的處理器176. TasksLoading的總和）來比較不同的CPUGroups的負荷,177. 以進行Tasks的移動,達到Balancing的目的.178. 在有支援SMP的架構下,會在函式sched_init中,呼叫open_softirq,179. 註冊SCHED_SOFTIRQSoftwareIRQ与其对应的Callback函式180. run_rebalance_domains.並會在每次呼叫函式scheduler_tick時,181. 透過函式trigger_load_balance确认是否目前的jiffies值已經182. 大於RunQueue下一次要觸發LoadBalance的next_balance時間值,183. 並透過函式raise_softirq觸發SCHED_SOFTIRQSoftwareIRQ.184. 在SoftwareIRQ觸發後,就會呼叫函式run_rebalance_domains,185. 並在函式rebalance_domains中,進行后续處理器上的186. SchedulingDomainLoadBalance動作.187. 有關SchedulingDomain進一步的內容,也可以參考188. LinuxKernel文件Documentation/scheduler/sched-domains.txt.189. */190. structsched_domain*sd;191. /*這值會等於函式idle_cpu的返回值,如果為1表示192. 目前CPURunQueue中執行的為IdleTask.反之為0,193. 則表示處理器執行的不是IdleTask(也就是說194. 處理器正在忙碌中.).*/195. unsignedcharidle_at_tick;196. /*Foractivebalancing*/197. /*若這值不為0,表示會有在Schedule排程動作198. 結束前,要呼叫的收尾函式.(实作為inline函式199. post_scheduleinkernel/sched.c),目前只有Real-TimeScheduling200. Class有支援這個機制(會呼叫函式has_pushable_tasks201. inkernel/sched_rt.c).*/202. intpost_schedule;203. /*當RunQueue中此值為1,表示這個RunQueue正在進行204. FairScheduling的LoadBalance,此時會呼叫stop_one_cpu_nowait205. 暫停該RunQueue所屬處理器的排程,並透過函式206. active_load_balance_cpu_stop,把Tasks從最忙碌的處理器,207. 移到Idle的處理器上執行.*/208. intactive_balance;209. /*用以儲存目前進入Idle且負責進行LoadBalance210. 流程的處理器ID.呼叫的流程為,在呼叫函式schedule時,211. 若該處理器RunQueue的nr_running為0(也就是目前沒有212. 正在執行的Task),就會呼叫idle_balance,並觸發後續Load213. Balance流程.*/214. intpush_cpu;215. /*cpuofthisrunqueue:*/216. /*用以儲存目前运作這個RunQueue的處理器ID*/217. intcpu;218. /*為1表示目前此RunQueue有在對應的處理器掛上219. 並執行.*/220. intonline;221. /*如果RunQueue中目前有Task正在執行,這個值會222. 等於目前該RunQueue的LoadWeight除以目前RunQueue223. 中Task數目的均值.224. (rq-avg_load_per_task=rq-load.weight/nr_running;).*/225. unsignedlongavg_load_per_task;226. 227. structtask_struct*migration_thread;228. structlist_headmigration_queue;229. /*這個值會由Real-TimeSchedulingClass呼叫函式230. update_curr_rt,用以統計目前Real-TimeTask執行時間的231. 均值,在這函式中會以目前RunQueue的clock_task232. 減去目前Task執行的起始時間,取得執行時間的233. Delta值.(delta_exec=rq-clock_taskcurr-se.exec_start;).234. 在透過函式sched_rt_avg_update把這Delta值跟原本235. RunQueue中的rt_avg值取平均值.以運作的週期來看,236. 這個值可反應目前系統中Real-TimeTask平均被237. 分配到的執行時間值.*/238. u64rt_avg;239. /*這個值主要在函式sched_avg_update更新,以笔者手中240. 的LinuxKernel2.6.38.6的實作來說,當RunQueueClock241. 減去age_stamp大於0.5秒(=sched_avg_period),就會把這值242. 累加0.5秒(單位都是nanoseconds).從函式scale_rt_power243. 的實作來說,age_stamp值離RunQueueClock越遠,表示total244. 值越大,available值也越大,而函式scale_rt_power返回的245. div_u64計算結果也越大,最終RunQueue的cpu_power246. 與SchedulingDomain中的SchedulingGroup的cpu_power247. 值也就越大.(可參考函式update_cpu_power的實作).*/248. u64age_stamp;249. /*這值會在觸發Scheduling時,若判斷目前處理器250. RunQueue沒有正在運作的Task,就會透過函式251. idle_balance更新這值為為目前RunQueue的clock值.252. 可用以表示這個處理器是何時進入到Idle的253. 狀態*/254. u64idle_stamp;255. /*會在有Task運作且idle_stamp不為0(表示前一個256. 狀態是在Idle)時以目前RunQueue的clock減去257. idle_stmp所計算出的Delta值為依據,更新這個值258. .可反應目前處理器進入Idle狀態的時間長短*/259. u64avg_idle;260. #endif 261. 262. /*calc_loadrelatedfields*/263. /*用以記錄下一次計算CPULoad的時間,初始值264. 為目前的jiffies加上五秒與1次的SchedulingTick的265. 間隔(=jiffies+LOAD_FREQ,且LOAD_FREQ=(5*HZ+1)*/266. unsignedlongcalc_load_update;267. /*會等於RunQueue中nr_running與nr_uninterruptible的268. 總和.（可參考函式calc_load_fold_active）.*/269. longcalc_load_active;270. 271. #ifdefCONFIG_SCHED_HRTICK 272. #ifdefCONFIG_SMP 273. /*在函式init_rq_hrtick初始化RunQueueHigh-Resolution274. Tick時,此值預設為0.275. 在函式hrtick_start中,會判斷目前觸發的RunQueue276. 跟目前處理器所使用的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. inthrtick_csd_pending;291. /*用以儲存hrtick機制中,要跨處理器執行的292. 函式結構.*/293. structcall_single_datahrtick_csd;294. #endif 295. /*為High-ResolutionTick的结构,會透過函式296. hrtimer_init初始化.*/297. structhrtimerhrtick_timer;298. #endif 299. 300. #ifdefCONFIG_SCHEDSTATS 301. /*latencystats*/302. /*為SchedulingInfo.的統計結構,可以參考303. include/linux/sched.h中的宣告.例如在每次觸發304. Schedule時,呼叫函式schedule_debug對上一個Task305. 的lock_depth進行確認(Fork一個新的Process時,306. 會把此值預設為-1就是No-Lock,當呼叫307. KernelLock時,就會把CurrentTask的lock_depth加一.),308. 若lock_depth=0,就會累加SchedulingInfo.的bkl_count值,309. 用以代表TaskBlocking的次數.*/310. structsched_inforq_sched_info;311. /*可用以表示RunQueue中的Task所得到CPU執行312. 時間的累加值.313. 在發生TaskSwitch時,會透過sched_info_switch呼叫314. sched_info_arrive並以目前RunQueueClock值更新315. Task的sched_info.last_arrival時間,而在Task所分配時間316. 結束後,會在函式sched_info_depart中以現在的317. RunQueueClock值減去Task的sched_info.last_arrival318. 時間值,得到的Delta作為變數rq_cpu_time的累319. 加值.*/320. unsignedlonglongrq_cpu_time;321. /*couldaboveberq-cfs_rq.exec_clock+rq-rt_rq.rt_runtime?*/322. 323. /*sys_sched_yield()stats*/324. /*用以統計呼叫SystemCallsys_sched_yield的次數.*/325. unsignedintyld_count;326. 327. /*schedule()stats*/328. unsignedintsched_switch;329. /*可用以統計觸發Scheduling的次數.在每次觸發330. Scheduling時,會透過函式schedule呼叫schedule_debug,331. 呼叫schedstat_inc對這變數進行累加.*/332. unsignedintsched_count;333. /*可用以統計進入到IdleTask的次數.會在函式334. pick_next_task_idle中,呼叫schedstat_inc對這變數進行335. 累加.*/336. unsignedintsched_goidle;337. 338. /*try_to_wake_up()stats*/339. /*用以統計WakeUpTask的次數.*/340. unsignedintttwu_count;341. /*用以統計WakeUp同一個處理器Task的次數.*/342. unsignedintttwu_local;343. 344. /*BKLstats*/345. unsignedintbkl_count;346. #endif 347. ;调度类，sched_class为对模块编程的上层支持，对于每个linux新添加进来的调度算法都需要有自己的调度类实例。1. /*CFS排程機制在設計時,考慮到排程機制的2. 彈性,定義了SchedulerClass的機制,讓排程機制3. 可以根據設計的需求,延伸不同的排程模4. 組進來,每個新加入的排程機制都必須要5. 提供SchedulerClass的實作,結構為structsched_class*/6. structsched_class7. /*會指向下一個SchedulingClass,以筆者所採用8. 的LinuxKernel2.6.38.6而言,SchedulingClass的順序為9. stop_sched_class-rt_sched_class-fair_sched_class-idle_sched_class*/10. conststructsched_class*next;11. /*當Task屬於Runnable狀態時,就會呼叫這個函式12. 把Task配置到RunQueueRBTree中,進行排程動作,13. 並呼叫inc_nr_running將RunQueue中nr_running的值14. 加一.(nr_running用以代表目前RunQueue有多少15. RunnableTask進行排程)*/16. void(*enqueue_task)(structrq*rq,structtask_struct*p,intwakeup);17. /*當Task不需要執行時,就會呼叫這個函式18. 把Task從RunQueueRBTree中移除,並呼叫19. dec_nr_running將RunQueue中nr_running的值減一.*/20. void(*dequeue_task)(structrq*rq,structtask_struct*p,intsleep);21. /*用以暫停目前正在執行中的Task,如果22. sysctl_sched_compat_yield有設定,就會找出目前23. RBTree中最右邊的Task(也就是vrruntime最多24. 的Task),讓目前Task的vrruntime值等於最右邊25. Task值的vrruntime加一(可參考:26. se-vruntime=rightmost-vruntime+1),如此在下次27. 排程觸發時就會透過函式put_prev_task把目前28. 的Task放到RBTree的最右邊,也就等同於暫停29. Task,讓該Task下次被執行到的機會最低.*/30. void(*yield_task)(structrq*rq);31. /*用以決定一個Task是否可以中斷目前正在32. 運作的Task,取得執行權.以CFS本身的實作來說33. (insched_fair.c).如果想要取代目前Task的Task本身34. 的SchedulingPolicy為Batch或是Idle時,會直接返回,35. 不會用來取代目前正在執行中的Task.反之,36. 如果目前正在執行中的Task的SchedulingPolicy37. 為Idle,就會直接由所傳入的Task取代目前正38. 在執行的Task.*/39. void(*check_preempt_curr)(structrq*rq,structtask_struct*p,intflags);40. /*用以在排程觸發時,從RunQueueRBTree中,41. 取出符合目前Scheduling邏輯的下一個要42. 被執行的Task.*/43. structtask_struct*(*pick_next_task)(structrq*rq);44. /*用以在排程觸發時,把上一個執行完畢的45. Task放到目前RunQueueRBTree中對應的位置.*/46. void(*put_prev_task)(structrq*rq,structtask_struct*p);47. 48. #ifdefCONFIG_SMP 49. /*通常用在執行一個新的程序,或是WakeUp50. 一個Task時,會根據目前SMP下每個處理器的51. 負荷,決定Task是否要切換到另一個處理器52. 的RunQueue去執行,執行時會返回最後目標53. 處理器的值.*/54. int(*select_task_rq)(structtask_struct*p,intsd_flag,intflags);55. 56. unsignedlong(*load_balance)(struc