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

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

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

【引證文獻】

相關期刊論文 前1條

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

相關博士學位論文 前1條

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

相關碩士學位論文 前10條

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

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

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

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

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

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

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

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

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

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

本文編號：2602584