基于Linux的進程調(diào)度算法的改進與實現(xiàn).pdf

1、分類號泫尚疋。罨碩士學(xué)位論文密級題目：墨生i墊豎的遘猩塑廑篡基的墮堂皇塞堡英文并列題目：!些i坐!Q∑!里!墮塑璺皇i望翌!!坐!墮Q!衛(wèi)!!!!!!!!皇!壘旦!!望g!!g旦墮!!堅翌!!!!璺竺里生!型研究生：鄒漁篷專業(yè)：i土箕扭應(yīng)用擅盔研究方向：鹽篁墊丕纏墾筮生蕉查導(dǎo)學(xué)位授予日期答辯委員會主席：江南大學(xué)地址：無錫市二oo六年三月摘要摘要隨著Linux系統(tǒng)的逐漸推廣，它被越來越多的計算機用戶所了解和應(yīng)用，各國政府都在鼓勵和支持Li

2、nux在本國的發(fā)展。0(1)調(diào)度算法推出后，使調(diào)度器的時間復(fù)雜度從O(n)降到了0(1)，又激起了人們對基于Linux的進程調(diào)度算法的研究。本文首先對Linux系統(tǒng)進行了簡要的介紹，介紹了國內(nèi)外在調(diào)度算法方面的研究現(xiàn)狀，分析了課題研究的背景和意義。然后介紹了進程管理的相關(guān)理論知識。其次，詳細(xì)研究了O(1)調(diào)度算法及其在Linux26內(nèi)核中的具體實現(xiàn)。0(1)調(diào)度器中增加了數(shù)據(jù)結(jié)構(gòu)runqueue，就緒隊列被分成active和expire

3、d，結(jié)合bitmap口不必遍歷整個就緒隊列，查找next進程的時間復(fù)雜度降為0(1)。進程運行時間片的重新分配更及時；動態(tài)優(yōu)先級的計算過程更簡單，計算時機更分散；調(diào)度時機更寬松，提高了調(diào)度器的實時性能；調(diào)度流程更簡單。也指出了，在0(1)調(diào)度器下，不同用戶執(zhí)行相同的程序，他們創(chuàng)建的進程將獲得相同的運行時問片和周轉(zhuǎn)時間。這樣對高級別用戶是不公平的。最后，引入了用戶級別的概念，證明了O(1)調(diào)度器的以上不足。提出了一種基于用戶級別的進程調(diào)度

4、策略，通過給不同用戶指派不同的級別，使不同級別用戶創(chuàng)建的進程的時間片不同，以此使他們的周轉(zhuǎn)時間不同，高級別用戶將獲得比低級別用戶更短的周轉(zhuǎn)時間，使各級別的用戶得到與其級別相適應(yīng)的周轉(zhuǎn)時間，更加體現(xiàn)進程調(diào)度的公平性原則；并且，一般情況下，該調(diào)度策略下O級用戶的周轉(zhuǎn)時間比在0(1)調(diào)度策略下短。0(1)調(diào)度器的研究緊跟了調(diào)度算法研究領(lǐng)域的前沿；用戶級別的引入、基于用戶級別的進程調(diào)度策略的提出，開拓了進程調(diào)度研究的新思路，一定程度上促進了我國