資源描述:
《linux內(nèi)核之cfs調(diào)度和組調(diào)度》由會(huì)員上傳分享,免費(fèi)在線閱讀,更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。
1、Linux內(nèi)核之CFS調(diào)度和組調(diào)度作者:harveywang郵箱:harvey.perfect@gmail.com新浪博客地址:http://blog.sina.com.cn/harveyperfect,有關(guān)于減肥和學(xué)習(xí)英語相關(guān)的博文,歡迎交流Linux支持三種進(jìn)程調(diào)度策略,分別是SCHED_FIFO、SCHED_RR和SCHED_NORMAL。Linux支持兩種類型的進(jìn)程,實(shí)時(shí)進(jìn)程和普通進(jìn)程。實(shí)時(shí)進(jìn)程可以采用SCHED_FIFO和SCHED_RR調(diào)度策略;普通進(jìn)程采用SCHED_NORMAL調(diào)度策
2、略。本文主要討論普通進(jìn)程的調(diào)度算法,為了描述方便,后面章節(jié)中的“進(jìn)程”指“普通進(jìn)程”。從Linux2.6.23內(nèi)核到目前最新的Linux3.3.5內(nèi)核的普通進(jìn)程(采用調(diào)度策略SCHED_NORMAL)采用了絕對(duì)公平調(diào)度算法,CFS(completelyfairschedule)。CFS從RSDL/SD中吸取了完全公平的思想,不再跟蹤進(jìn)程的睡眠時(shí)間,也不再區(qū)分交互式進(jìn)程。它將所有的進(jìn)程都統(tǒng)一對(duì)待,這就是公平的含義。CFS調(diào)度中,進(jìn)程數(shù)據(jù)結(jié)構(gòu)中的動(dòng)態(tài)優(yōu)先級(jí)成員prio還繼續(xù)有效,只是內(nèi)核不再動(dòng)態(tài)調(diào)整進(jìn)程
3、的動(dòng)態(tài)優(yōu)先級(jí)了。進(jìn)程的優(yōu)先級(jí)為100—139,對(duì)應(yīng)的nice值為-20—19。和之前版本的優(yōu)先級(jí)規(guī)定相同。Nice和優(yōu)先級(jí)對(duì)應(yīng)關(guān)系如下如何實(shí)現(xiàn)公平調(diào)度的??jī)?nèi)核給每個(gè)進(jìn)程維護(hù)了一個(gè)虛擬運(yùn)行時(shí)間vruntime,每個(gè)進(jìn)程運(yùn)行一段時(shí)間后,虛擬運(yùn)行時(shí)間會(huì)增加,但是運(yùn)行同樣的實(shí)際時(shí)間每個(gè)進(jìn)程增加的數(shù)值是不同的。比如nice值為0的進(jìn)程運(yùn)行了10ms,其虛擬運(yùn)行時(shí)間增加了1vms(vms為1虛擬毫秒,為了描述方便而定義);nice為19的進(jìn)程運(yùn)行10ms,其虛擬運(yùn)行時(shí)間增加了1000vms。進(jìn)程在其生命周期中,
4、其虛擬運(yùn)行時(shí)間一直都是在增加的。內(nèi)核把虛擬運(yùn)行時(shí)間看做實(shí)際運(yùn)行時(shí)間,為了公平起見要選擇運(yùn)行時(shí)間短的進(jìn)程進(jìn)行運(yùn)行。所以內(nèi)核在調(diào)度中總是選擇虛擬運(yùn)行時(shí)間小的進(jìn)程。對(duì)內(nèi)核來說,這樣就很公平了,O(∩_∩)O同樣運(yùn)行10ms,如何確定一個(gè)進(jìn)程該增加多少vms?增加的虛擬運(yùn)行時(shí)間和進(jìn)程的優(yōu)先級(jí)nice數(shù)值有關(guān),每個(gè)nice數(shù)值對(duì)應(yīng)一個(gè)權(quán)重?cái)?shù)值,見下圖。每個(gè)進(jìn)程虛擬運(yùn)行時(shí)間增加的時(shí)間量和(NICE_0_LOAD/nice_n_weight)成正比。其中NICE_0_LOAD為1024,即nice數(shù)值為0的權(quán)重,
5、nice_n_weight即為nice數(shù)值為n的進(jìn)程的權(quán)重,如nice為-20(優(yōu)先級(jí)最高的普通進(jìn)程)的權(quán)重為88761。從這種算法也可以看出,優(yōu)先級(jí)高的進(jìn)程的虛擬運(yùn)行時(shí)間增加的慢,其實(shí)際運(yùn)行時(shí)間累計(jì)數(shù)值也就長(zhǎng)。同樣,這種算法能保證優(yōu)先級(jí)低的進(jìn)程也有運(yùn)行機(jī)會(huì),只是實(shí)際運(yùn)行的時(shí)間比較短。內(nèi)核要把所有running狀態(tài)的進(jìn)程放到一起,在需要調(diào)度時(shí)從中取出一個(gè)虛擬運(yùn)行時(shí)間短的進(jìn)程。因?yàn)榘l(fā)生調(diào)度的頻率非常高,查找合適進(jìn)程的算法就變的很重要了。在CFS調(diào)度中,內(nèi)核采用了以進(jìn)程虛擬運(yùn)行時(shí)間為key值的紅黑樹數(shù)據(jù)
6、結(jié)構(gòu)掛接各個(gè)running的進(jìn)程。有關(guān)紅黑樹請(qǐng)參考《linux內(nèi)核之紅黑樹》。先要引入一個(gè)重要概念,調(diào)度實(shí)體(schedentiy):就是調(diào)度的對(duì)象。每個(gè)進(jìn)程的task_struct包含了調(diào)度實(shí)體成員變量se。為何要引入調(diào)度實(shí)體,而不是直接使用進(jìn)程的task_struct?是因?yàn)樵贑FS中支持CFS組調(diào)度,一個(gè)組中可能包含1個(gè)或多個(gè)進(jìn)程。不能通過組中任何進(jìn)程的task_struct來調(diào)度組,所以引入了調(diào)度實(shí)體的概念。為了統(tǒng)一起見,進(jìn)程組和進(jìn)程都使用調(diào)度實(shí)體保存調(diào)度相關(guān)的信息。后面會(huì)介紹CFS組調(diào)度。
7、在多核系統(tǒng)中,每個(gè)CPU(此處指一個(gè)核心)對(duì)應(yīng)一個(gè)全局變量per_cpu_runqueues,其數(shù)據(jù)結(jié)構(gòu)為structrq,該變量為調(diào)度的最頂層的數(shù)據(jù)結(jié)構(gòu)。在該數(shù)據(jù)結(jié)構(gòu)中包含了cfs,其數(shù)據(jù)結(jié)構(gòu)為structcfs_rq。cfs就是在該cpu上CFS調(diào)度的頂級(jí)結(jié)構(gòu),或者說是CFS調(diào)度的入口點(diǎn)。其實(shí)rq中還包括了rt成員變量,rt是實(shí)時(shí)進(jìn)程調(diào)度的頂級(jí)結(jié)構(gòu)。structcfs_rq{為了說明方便,只保留部分成員變量structrb_roottasks_timeline;structrb_node*rb_
8、leftmost;structsched_entity*curr,*next,*last,*skip;}其中成員變量tasks_timeline指向了紅黑樹的根,所有的進(jìn)程都掛到這棵紅黑樹上(有些是間接掛接的)。如下圖中的單個(gè)進(jìn)程,進(jìn)程數(shù)據(jù)結(jié)構(gòu)task_struct中包含了成員變量se,即調(diào)度實(shí)體。調(diào)度實(shí)體se中包含了run_node節(jié)點(diǎn),se通過該節(jié)點(diǎn)掛接到紅黑樹上。在選擇需要調(diào)度的進(jìn)程時(shí),內(nèi)核將搜索這個(gè)紅黑樹,找到虛擬運(yùn)行時(shí)間小的進(jìn)程,并把該進(jìn)程從樹上摘下。同時(shí)會(huì)