ISSN 1009- 3044E-mail: infocccc.net.cnComputer Knowiedge and Technology電腦知識'技術(shù)htp://www.dnzs.net.cnVol.7, No.1, January 211.pp.70-717Tel:+86- -51- -5690963 5690964Linux進(jìn)程調(diào)度分析鐘誠,盧衛(wèi)恒,李德勇.(江南計算技術(shù)研究所,江蘇無錫214083)摘要:Linux系統(tǒng)作為能夠應(yīng)用于多平臺的多任務(wù)操作系統(tǒng)，它被廣泛應(yīng)用于嵌入式電子產(chǎn)品中,linux系統(tǒng)的效率就成為電子產(chǎn)品性能的重要因素之一。文章從linux進(jìn)程調(diào)度的角度來分析linux系統(tǒng)的性能,對linux進(jìn)程調(diào)度的原理、算法以及過程進(jìn)行了分析。關(guān)鍵詞:進(jìn)程調(diào)度;內(nèi)核;多任務(wù)中圖分類號:TP311文獻(xiàn)標(biāo)識碼:A文章 編號:1009 -042011)01-0070- -02Linux Process Scheduling AnalysisZHONG Cheng, LU Wei-heng, LI De -yong(iangnan Computing Technology Institute, Wuxi 214083, China)Abstract: The linux system is many task operate systems that can be applied to many platforms, it is extensively been applied to a built- inelectronics product, the efficiency of linux system becomes one of the important factors of electronics product function.The article is fomthe angle that the linux progress adjusted a degree to analyze the function of linux system, adjusted principle, calculate way and process ofdegree to carry on analysis to the linux progress.Key words: process scheduling; kemel; muliusk1概述Linux 操作系統(tǒng)是-一種開源、免費.能夠運用于多平臺的多任務(wù)操作系統(tǒng)。多任務(wù)操作系統(tǒng)就是能夠同時并發(fā)的交互的處理多進(jìn)程任務(wù)的系統(tǒng),然而多個進(jìn)程的運行,就不可避免的競爭系統(tǒng)的資源,尤其是在單處理器系統(tǒng)上,進(jìn)程就不可能同時占用處理器資源,這樣進(jìn)程調(diào)度就是Linux內(nèi)核不可或缺的成員,它是負(fù)貴選擇下一個可以運行的進(jìn)程。進(jìn)程調(diào)度程序可以看成在可運行態(tài)進(jìn)程之間分配有限資源的內(nèi)核子系統(tǒng),它是多任務(wù)操作系統(tǒng)的基礎(chǔ).只有通過調(diào)度程序得合理調(diào)度,系統(tǒng)資源才會最大化的發(fā)揮它的作用,多進(jìn)程才會有并發(fā)執(zhí)行的效果。2基本原理2.1原則進(jìn)程的運行需要系統(tǒng)上的各種資源,如內(nèi)存.cpu、各種專用模塊等,因此linux進(jìn)程的調(diào)度實際上就是合理的把這些資源分配給各個進(jìn)程,而如何分配則是取決于具體的調(diào)度算法,不同的應(yīng)用場合需要的資源存在著很多差異,選用什么樣的調(diào)度算法要依據(jù)具體的資源分配策略。一個好的調(diào)度算法應(yīng)該注意以下方面:1)高效率:使CPU盡可能的保持忙碌,最大限度地利用處理器的原則是.只要有可以執(zhí)行的進(jìn)程,那么就總會有進(jìn)程正在執(zhí)行。2)公平:保證每個進(jìn)程得到合理的資源分配時間.避免一個進(jìn)程長期占用同一個資源,不存在一一個進(jìn)程長時間獲得不到資源。3)響應(yīng)時間:使進(jìn)程切換或獲取資源時的相應(yīng)時間盡可能的短,以最快的速度進(jìn)人到工作狀態(tài)。4)周轉(zhuǎn)時間:使得用戶等待結(jié)果輸出的時間盡可能矩。5)吞吐量:使得在單位時間內(nèi)盡可能多的處理進(jìn)程。2.2調(diào)度的依據(jù)調(diào)度程序在運行時,它主要依據(jù)每個進(jìn)程的tsk struck結(jié)構(gòu)中need. reeched .nice .counter .policy和nt prority各項根據(jù)不同的分配策略依靠調(diào)度算法決定下-個要執(zhí)行的進(jìn)程。1)need. _resched:當(dāng)進(jìn)程需要進(jìn)行調(diào)度的時候,會去判斷這個變量的值.如果為1,則會調(diào)用schedule0。2)counter:時間片,它表明一個進(jìn)程處于運行狀態(tài)所能夠持續(xù)的時間,每當(dāng)-一個時鐘中斷到來時,就會減1,當(dāng)它的值減少為0時,會把need_resched變量置1,此時進(jìn)程將會進(jìn)入到調(diào)度隊列從而不再運行。調(diào)度策略都要給每個進(jìn)程規(guī)定一個默認(rèn)的時間片,這個時間片的長度要合理的設(shè)置，時間片過長,會導(dǎo)致- -個進(jìn)程長時間占用資源,這樣進(jìn)程的交互性就差,其它進(jìn)程也難以公平的獲得資源;時間片過短，會使進(jìn)程頻繁的切換,進(jìn)程切換的時間所占比例增大.從而致使CPU的效率降低。3)nice: 進(jìn)程的靜態(tài)優(yōu)先級,根據(jù)優(yōu)先級的高低來確定不同進(jìn)程的counter的初值。調(diào)度算法中最基本的一類就是基于優(yōu)先級的調(diào)度,它根:據(jù)進(jìn)程在系統(tǒng)中的重要程度以及所省的CPU處理時間而分級.優(yōu)先級高的先執(zhí)行,低的后執(zhí)行,同優(yōu)先級的按照輪轉(zhuǎn)的方式執(zhí)行。調(diào)度程序總是選擇優(yōu)先級最高并且時間片還沒有使用完的進(jìn)程首先執(zhí)行,因此可以通過修改進(jìn)程的優(yōu)先級控制進(jìn)程的調(diào)度。4)t_prority:進(jìn)程的動態(tài)優(yōu)先級,一-般每個進(jìn)程都會有一個基本優(yōu)先級.調(diào)度程序可以在實際運行過程中,根據(jù)需要動態(tài)提高或降低該值,可以控制進(jìn)程的調(diào)度。中國煤化工YHCNMHG收稿日期:2010-11-02作者簡介:鐘誠(1986-),男,助理工程師,江南計算技術(shù)研究所碩士研究生,主要研究方向為信息安全。70_ .網(wǎng)絡(luò)通訊及安全 .......本欄目責(zé)任編輯:馮蕾第7卷第1期(2011年1月)Computer Knowtedge and Technology電訾知識與技術(shù)5)policy:進(jìn)程的調(diào)度策略.進(jìn)程分為實時進(jìn)程和普通進(jìn)程,它們所采用的調(diào)度算法不同,實時進(jìn)程對執(zhí)行的效率要求更高,一般情況下優(yōu)先級都會高于普通進(jìn)程。對于普通進(jìn)程,選擇進(jìn)程主要依據(jù)counter和nice。3調(diào)度算法3.1時間片輪轉(zhuǎn)調(diào)度算法在通常的時間片輪轉(zhuǎn)算法中.系統(tǒng)將可以運行的程序按照先后順序加人到一個等待隊列中.每次分配時將CPU使用權(quán)交給隊列頭部的進(jìn)程.同時賦予一個時間片,隨著時鐘中斷的不斷到來,減少時間片.當(dāng)時間片用完時.系統(tǒng)發(fā)出信號,通知調(diào)度程序,調(diào)度程序終止該進(jìn)程的執(zhí)行,并把該進(jìn)程送到隊尾.等待下一次輪詢。這時將CPU資源交給隊列苘部的進(jìn)程.同樣根據(jù)策略分給它-一個時間片,依次循環(huán)。這樣就可以保證每個進(jìn)程都在較為合理的時間內(nèi)獲得資源,不會出現(xiàn)一個進(jìn)程獨占的現(xiàn)象。3.2優(yōu)先權(quán)調(diào)度算法由于各個進(jìn)程的應(yīng)用環(huán)境差異,執(zhí)行的功能有所區(qū)別,因此不同的進(jìn)程對于系統(tǒng)的緊迫程度就有所不同.有些進(jìn)程需要進(jìn)入系統(tǒng)后優(yōu)先處理.而有些進(jìn)程則不需要實時處理,這便引入了優(yōu)先權(quán)調(diào)度算法。根據(jù)系統(tǒng)對實時性要求的情況又可進(jìn)- 步分為非搶占式和搶占式調(diào)度算法。非搶占式調(diào)度算法,在這種方式下,系統(tǒng)一旦把CPU資源分給優(yōu)先級最高的進(jìn)程之后.在該進(jìn)程結(jié)束之前,不會再次調(diào)用調(diào)度函數(shù),只有因為該進(jìn)程正常結(jié)束或者由于某些事件導(dǎo)致該進(jìn)程放棄CPU時，調(diào)度函數(shù)才會把CPU資源重新交給另一個優(yōu)先級最高的進(jìn)程。這種方式適用于批處理系統(tǒng)等對于實時性要求不嚴(yán)格的系統(tǒng)中。搶占式調(diào)度算法,在這種方式下.系統(tǒng)把CPU資源分給當(dāng)前隊列中優(yōu)先級最高的進(jìn)程之后,- -旦出現(xiàn)了另一個優(yōu)先級更高的進(jìn)程,則立刻調(diào)用調(diào)度雨數(shù)把CPU資源交給這個進(jìn)程。這種調(diào)度算法在新進(jìn)程到來時都會與正在執(zhí)行的進(jìn)程進(jìn)行優(yōu)先級比較,如果高于肖前進(jìn)程就調(diào)用調(diào)度函數(shù),否則就進(jìn)入等待隊列。搶占時調(diào)度算法更好的滿足緊迫的進(jìn)程,故常用與實時性要求較高的系統(tǒng)中。3.3多級反饋隊列調(diào)度算法這種調(diào)度算法綜合了時間片輪轉(zhuǎn)調(diào)度算法和優(yōu)先權(quán)調(diào)度算法的優(yōu)點.首先根據(jù)等待隊列中進(jìn)程的優(yōu)先級,把時間片分給優(yōu)先級最高的-批進(jìn)程.在這些進(jìn)程中運行時間片輪轉(zhuǎn)調(diào)度,當(dāng)有更高的優(yōu)先級進(jìn)程到來時,會優(yōu)先分給時間片。4Linux進(jìn)程調(diào)度過程分析4.1轉(zhuǎn)入調(diào)度程序的時機(jī)1)進(jìn)程在執(zhí)行的過程中遇到狀態(tài)切換的時候:當(dāng)進(jìn)程需要進(jìn)人休眠或者終止?fàn)顟B(tài)時而調(diào)用了相應(yīng)的進(jìn)程處理函數(shù)時,這些函數(shù)會觸發(fā)進(jìn)程調(diào)度函數(shù)。2)有新的并且符合運行條件的進(jìn)程加入到等待隊列中;3)進(jìn)程從其他系統(tǒng)調(diào)用中返回用戶態(tài)時:進(jìn)程當(dāng)從系統(tǒng)調(diào)用中返回時,都會對調(diào)度標(biāo)識的檢測.如果調(diào)度標(biāo)識指示需要調(diào)度,則調(diào)用調(diào)度函數(shù)進(jìn)行調(diào)度。4)當(dāng)前運行的進(jìn)程不再擁有counter值時;5)設(shè)備驅(qū)動程序:當(dāng)設(shè)備API經(jīng)常調(diào)用驅(qū)動程序時,驅(qū)動程序會反復(fù)檢測need.,esched值,需要時調(diào)用schedule兩數(shù)獲取或放棄CPU資源。4.2調(diào)度函數(shù)schedule當(dāng)系統(tǒng)的進(jìn)程符合4.1中所敘述的時機(jī)后,便轉(zhuǎn)入調(diào)度函數(shù)。此過程一般分為三部分內(nèi)容:調(diào)度前的檢查過程,對當(dāng)前進(jìn)程的處理.選擇下一個可以執(zhí)行的進(jìn)程。1)調(diào)度前的檢查過程:調(diào)度函數(shù)主要對當(dāng)前進(jìn)程的地址空間進(jìn)行檢查,如果該進(jìn)程沒有地址空間可以使用，則必然出錯,檢查是否是中斷服務(wù)程序調(diào)用了調(diào)度函數(shù).如果是則出錯。2)對當(dāng)前進(jìn)程進(jìn)行處理:首先檢查當(dāng)前進(jìn)程的狀態(tài),如果當(dāng)前進(jìn)程的狀態(tài)為TASKZOMBE或是TASK.INTERRUPTIBLE,則直接將該進(jìn)程從運行隊列中刪除;其次,檢查當(dāng)前進(jìn)程的時間片,如果是來用時間片輪轉(zhuǎn)調(diào)度算法,該值為0則對進(jìn)程重新分配時間片,再將該進(jìn)程置隊列尾部。3)將資源交給符合條件的新的進(jìn)程:搜索運行隊列中所有進(jìn)程的權(quán)值,并與當(dāng)前進(jìn)程的權(quán)值進(jìn)行比較.選撣權(quán)值最大的進(jìn)程,如果運行隊列中所有進(jìn)程的權(quán)值都降為零時.則表示當(dāng)前隊列中的進(jìn)程的時間片都使用光了,需要根據(jù)策略重新獲取時間片。最終選取下一個可執(zhí)行的進(jìn)程,將內(nèi)核地址空間切換至用戶地址空間。5總結(jié)進(jìn)程調(diào)度程序時內(nèi)核的重要組成部分，這是因為linux系統(tǒng)的運行離不開進(jìn)程.而進(jìn)程又都必須占用計算機(jī)的唯一資源CPU。然而,進(jìn)程執(zhí)行的功能,所備的性能差異很大.調(diào)度算法很難做到既適合眾多的可運行的進(jìn)程,又具有可伸縮性，還可以在吞吐量與調(diào)度周期之間求得平衡,同時還要滿足各種負(fù)載,因此如何最大化的權(quán)衡各種告中縣linww講程調(diào)度的￥鍵所在。中國煤化工參考文獻(xiàn):[1]張同光.Linux 2.6內(nèi)核分析一對 進(jìn)程調(diào)度機(jī)制的分小長春工業(yè)大學(xué)學(xué)YHCNMHG[2]楊嘉,王移芝.Linux內(nèi)核調(diào)度器算法研究與性能分析[I].計算機(jī)技術(shù)與發(fā)展2006(3).[3]謝偉毅.Linux調(diào)度算法在桌面應(yīng)用環(huán)境中的改進(jìn)[]計算機(jī)工程與應(yīng)用2006(23).本欄目責(zé)任編輯:馮靜.......網(wǎng)絡(luò)遇訊及安全" 71.