【摘要】： 微處理器自誕生以來,性能的提升主要是通過提高主頻來實(shí)現(xiàn)的,而主頻的提升要求大幅度增加晶體管的數(shù)量。巨大的晶體管數(shù)量則意味著巨大的能耗,隨之帶來的散熱問題也日益凸顯。當(dāng)處理器性能受到半導(dǎo)體工藝限制的時(shí)候,研究人員將目光投到了處理器的體系結(jié)構(gòu),提出了多核處理器的概念。多核處理器已經(jīng)成為微處理器發(fā)展的趨勢,使用多核技術(shù)可以使微處理器的性能得到極大的提高,但同時(shí)也對調(diào)度策略提出了更高的要求。 本文首先分析了課題研究的背景和意義,簡要介紹了進(jìn)程、線程和多線程以及在單處理器調(diào)度的基本理論知識。介紹了多核處理器硬件相關(guān)的主要實(shí)現(xiàn)技術(shù),包括同時(shí)多線程(Simultaneous Multithreading,SMT ),片上多處理器(Chip MultiProcessor,CMP),片上多線程(Chip Multiple Threading, CMT);并分析了目前多核線程調(diào)度的研究現(xiàn)狀。 其次,本文詳細(xì)研究了Linux2.6內(nèi)核的O(1)調(diào)度算法及其具體實(shí)現(xiàn)。O(1)調(diào)度器中增加了數(shù)據(jù)結(jié)構(gòu)runqueue,就緒隊(duì)列被分成活動隊(duì)列和過期隊(duì)列,結(jié)合bitmap[]不必遍歷整個(gè)就緒隊(duì)列,查找next進(jìn)程的時(shí)間復(fù)雜度降為O(1),進(jìn)程運(yùn)行時(shí)間片的重新分配更及時(shí);動態(tài)優(yōu)先級的計(jì)算過程更簡單。詳細(xì)分析了在Linux中的SMP的具體實(shí)現(xiàn),著重討論了Linux負(fù)載均衡系統(tǒng)。然后指出了Linux2.6調(diào)度算法的不足:1.因?yàn)樵谔幚砥鏖g遷移不同進(jìn)程的代價(jià)是不盡相同的,所以在遷移進(jìn)程的時(shí)候,應(yīng)該適當(dāng)考慮進(jìn)程的特點(diǎn)。2.調(diào)度器給處理器分配進(jìn)程的時(shí)候應(yīng)該考慮進(jìn)程的相關(guān)性。3.當(dāng)系統(tǒng)的負(fù)載不平衡且很輕微的時(shí)候,不一定需要平衡負(fù)載。 最后,提出一種負(fù)載均衡的通用模型,使用四元組E,T,L,S來表示。然后根據(jù)該模型的各個(gè)因子對Linux的負(fù)載均衡系統(tǒng)進(jìn)行剖析,著重分析了Linux的負(fù)載評價(jià)因子L和調(diào)度策略因子S。針對Linux調(diào)度器不考慮進(jìn)程遷移代價(jià)的不足提出了基于資源利用率的負(fù)載均衡算法,通過計(jì)算進(jìn)程的CPU利用率和內(nèi)存利用率來選擇遷移進(jìn)程,然后通過統(tǒng)計(jì)系統(tǒng)中的過載CPU和輕載CPU,根據(jù)Donor或者Reciever算法來匹配源CPU和目的CPU。
【圖文】：

3. 最短進(jìn)程減少 FCFS 固有的對長進(jìn)程的偏愛的另一種方法是最短進(jìn)程（S，SPN）策略。這是一個(gè)非剝奪的策略，其原則是下一次選擇所進(jìn)程。因此，短進(jìn)程將會越過長作業(yè)，跳到隊(duì)列頭。SPN 的風(fēng)險(xiǎn)在于只要持續(xù)不斷地提供更短的進(jìn)程，長進(jìn)程就有方面，盡管 SPN 減少了對長作業(yè)的偏愛，但是由于缺少剝奪機(jī)或事務(wù)處理環(huán)境仍然不理想。4. 最短剩余時(shí)間最短剩余時(shí)間（Shortest Remaining Time，SRT）是對 SPN 增加。在這種調(diào)度機(jī)制下，調(diào)度程序總是選擇預(yù)期剩余時(shí)間最短的進(jìn)個(gè)進(jìn)程加入就緒隊(duì)列時(shí)，它可能比當(dāng)前運(yùn)行的進(jìn)程具有更短的只要新進(jìn)程就緒，調(diào)度程序就剝奪當(dāng)前進(jìn)程并使新進(jìn)程運(yùn)行。和程序在執(zhí)行選擇函數(shù)時(shí)必須包含對處理時(shí)間的估計(jì)，并且存在險(xiǎn)。5. 最高響應(yīng)比根據(jù)排隊(duì)模型，周轉(zhuǎn)時(shí)間（turnaround time，TAT）就是駐留時(shí)

Intel 公司所實(shí)現(xiàn)的 SMT 技術(shù)就是超線程(Hyper-Threading, HT)[13]技術(shù)。超線程技術(shù)實(shí)際上只有一個(gè)實(shí)際的物理處理器但是從軟件角度來看，存在多個(gè)邏輯處理器。超線程技術(shù)支持操作系統(tǒng)和應(yīng)用程序?qū)⒍鄠�(gè)線程調(diào)度到多個(gè)邏輯處理器上，，就像多處理器一樣。從微體系結(jié)構(gòu)的角度來看，邏輯處理器的指令都是固定的，并且在共享的執(zhí)行資源上同時(shí)執(zhí)行。2.3.2 CMP 結(jié)構(gòu)在同時(shí)多線程技術(shù)之后就出現(xiàn)了多核處理器。在 1996 年斯坦福大學(xué)的研究人員提出了單片多處理器（Chip Multi-Processor，CMP）結(jié)構(gòu)，并進(jìn)行了研究[14]。單片多核處理器的主要思想是通過簡化超標(biāo)量結(jié)構(gòu)設(shè)計(jì)，將多個(gè)相對簡單的超標(biāo)量處理器核集成到一個(gè)芯片上，從而避免線延的影響，并充分開發(fā) TLP，提高吞吐量。CMP 存在的主要問題是由于單片多處理器系統(tǒng)的資源是采用劃分方式的,當(dāng)沒有足夠的線程時(shí),資源就浪費(fèi)了[15]。按計(jì)算內(nèi)核的對等與否，CMP 可分為同構(gòu)多核和異構(gòu)多核。計(jì)算內(nèi)核相同，
【學(xué)位授予單位】：電子科技大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2009
【分類號】：TP332

【引證文獻(xiàn)】

相關(guān)期刊論文 前1條

1 夏廈;李俊;;基于緩存競爭優(yōu)化的Linux進(jìn)程調(diào)度策略[J];計(jì)算機(jī)工程;2013年04期

相關(guān)博士學(xué)位論文 前1條

1 耿曉中;基于多核分布式環(huán)境下的任務(wù)調(diào)度關(guān)鍵技術(shù)研究[D];吉林大學(xué);2013年

相關(guān)碩士學(xué)位論文 前10條

1 曹皓;多核處理器體系結(jié)構(gòu)下Linux調(diào)度機(jī)制的研究[D];內(nèi)蒙古大學(xué);2011年

2 高金華;基于多核的任務(wù)調(diào)度研究與實(shí)現(xiàn)[D];中南大學(xué);2010年

3 申建晶;嵌入式多核實(shí)時(shí)操作系統(tǒng)研究及實(shí)現(xiàn)[D];電子科技大學(xué);2011年

4 楊新波;多核系統(tǒng)內(nèi)存管理算法的研究[D];哈爾濱工程大學(xué);2011年

5 曹成;嵌入式實(shí)時(shí)操作系統(tǒng)RT-Thread原理分析與應(yīng)用[D];山東科技大學(xué);2011年

6 范光雄;多處理器系統(tǒng)中的線程調(diào)度研究[D];電子科技大學(xué);2010年

7 王良;基于虛擬儀器的舵電位器測試系統(tǒng)設(shè)計(jì)與實(shí)現(xiàn)[D];中北大學(xué);2010年

8 張修琪;基于Linux多核進(jìn)程調(diào)度的研究[D];電子科技大學(xué);2012年

9 王軍鋒;基于多核的進(jìn)程調(diào)度算法研究[D];哈爾濱工程大學(xué);2012年

10 黃煜;KVM虛擬機(jī)CPU虛擬化的研究與調(diào)度策略的優(yōu)化[D];成都理工大學(xué);2012年

本文編號：2602584