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

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

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

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

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