在眾多的并行作業(yè)調(diào)度算法中,Backfill通常被廣泛認為是有效提高CPU利用率的一種算法,該算法是在FCFS算法的基礎(chǔ)上,將隊列中較小的作業(yè)回填(backfill)到空閑CPU,以提高CPU利用率。但是,當空閑CPU數(shù)量仍然無法滿足Backfill算法中小作業(yè)的回填要求時,系統(tǒng)仍有部分CPU閑置,因而也難以達到更好的提高CPU利用率的目的。 為了改進Backfill算法不能充分利用空閑CPU這一不足之處,本文提出了基于Backfill算法的需求自適應(yīng)改進算法;而對于共享內(nèi)存體系結(jié)構(gòu)的并行計算機系統(tǒng),本文還提出了基于Backfill算法的資源自動回收改進算法。 在Backfill的基礎(chǔ)上,需求自適應(yīng)改進算法利用CPU的空閑空間作為判斷依據(jù),擴展了可參與填充操作作業(yè)的數(shù)量。該算法通過合理修改隊列中作業(yè)的參數(shù)——所需CPU數(shù)量和估計運行時間,以滿足Backfill算法下無法利用的CPU空閑,彌補了Backfill算法的不足,大大提高了并行計算機系統(tǒng)的CPU資源的利用率。 資源自動回收改進算法以正在運行的作業(yè)的CPU利用率為依據(jù),通過動態(tài)調(diào)整正在運行的作業(yè)的CPU數(shù),擴大可供回填(backfill)的CPU空間,使得Backfill算法無法回填(backfill)的作業(yè)得到運行,彌補了Backfill算法的不足,也很好的提高了共享內(nèi)存體系結(jié)構(gòu)并行計算機系統(tǒng)的CPU利用率。兩種改進算法都是在Backfill的基礎(chǔ)上,從不同的技術(shù)層面來改進Backfill算法,通過與FCFS、Backfill相結(jié)合,共同參與并行計算機系統(tǒng)的作業(yè)調(diào)度,實現(xiàn)CPU資源利用率的不斷提高。
【學(xué)位單位】：湖南大學(xué)
【學(xué)位級別】：碩士
【學(xué)位年份】：2007
【中圖分類】：TP338.6
【部分圖文】：

以對它有一個總體上的了解，為并行程序設(shè)計奠定基礎(chǔ)。并行計算機可以按多種方式進行分類，如果按照存儲機構(gòu)劃分，可以分為共享內(nèi)存式并行計算機和分布式內(nèi)存并行計算機[29]，如圖2.1所示。 ...................，，， ，，，，， ，，，， ， ，， ，共共享內(nèi)存 存 ‘‘‘ ‘‘‘ ‘‘‘ 且且 且 且且 且且且 且又又夕夕 夕女參夕夕夕冬_鄉(xiāng) 鄉(xiāng)互互連網(wǎng)絡(luò) 絡(luò) ///_\\\\\灘止卜卜 卜矛粼粼粼 百百 百 百林落 落 落萬 萬 丫 丫 丫丫 丫 丫 丫 官官共享內(nèi)存并行計算機分布式內(nèi)存并行計算機分布式共享內(nèi)存并行計算機不具有局部存儲的處理單元共享存儲的局部處理單元具有局部存儲的處理單元回目回﨎圖2.1按存儲方式對并行計算機進行分類對于共享內(nèi)存的并行計算機，各個處理單元之間是通過共享內(nèi)存來訪問來交換信息、協(xié)調(diào)各處理器對并行任務(wù)進行處理。對這種共享內(nèi)存的編程

EEExternalJobsehedulerrrrr襯。 dennn圖2.2一個典型的資源管理系統(tǒng)可以通過圖2.2[’l所示，對作業(yè)調(diào)度有一個整體的認識。這是一個典型的資源管理系統(tǒng)(Atypiealresourcemanagementsystem)，作業(yè)調(diào)度器從資源管理器獲取有關(guān)作業(yè)的排隊情況、作業(yè)的優(yōu)先權(quán)和系統(tǒng)可用資源等信息，然后決定作業(yè)將在哪一個節(jié)點被執(zhí)行以及被執(zhí)行的時間順序。2.2.3幾種經(jīng)典并行作業(yè)調(diào)度算法的描述由多CPU組成的并行計算機系統(tǒng)或通過以太網(wǎng)或其他網(wǎng)絡(luò)連接的多個超級計算節(jié)點構(gòu)成的并行計算集群己實現(xiàn)了大規(guī)模的并行計算能力，相對公平的作業(yè)調(diào)度成為并行計算系統(tǒng)急需改進和提高的問題。一個“好的”作業(yè)調(diào)度器要同時兼顧“公平、簡單易懂以及提高可用資源的利用率”，而這三者之間卻又相互矛盾。在不同的環(huán)境下，可以選擇不同的作業(yè)調(diào)度算法或者通過多種作業(yè)調(diào)度算法并用來實現(xiàn)三者之間的折中，得到一個較為和諧、滿意的作業(yè)調(diào)度器。如今

Ti釁圖2.4FCFS作業(yè)調(diào)度2.SJF(最短先服務(wù));LJF(最長先服務(wù))如果說FCFS的調(diào)度原則是依據(jù)作業(yè)被提交的時間先后順序來排序作業(yè)的序，而最終被確定為作業(yè)被執(zhí)行的順序，那么最短先服務(wù)SJF(shortest的調(diào)度原理則是:系統(tǒng)周期性地檢索用戶提交的作業(yè)，將占用資源最小排在隊列前面最先執(zhí)行它。這種調(diào)度方式是以作業(yè)所需求資源的大小來排列中資源需求小的作業(yè)總是排在資源需求大的作業(yè)前面而被提前調(diào)度運圖2.4FCFS的作業(yè)調(diào)度中，作業(yè)T7、T:在SJF調(diào)度下就會比作業(yè)T6提在作業(yè)T，和T6之間就不會存在大量空閑CPU的浪費，這樣在一定程度FCFS調(diào)度過程所導(dǎo)致的大量的CPU碎片，從而很好的提高了CPU資。但這種調(diào)度方式使小作業(yè)成為了系統(tǒng)可用資源的主宰，而大作業(yè)的執(zhí)可預(yù)計的延緩，失去一定的公平性，并且還會導(dǎo)致大作業(yè)因長時間分配

【引證文獻】

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

1 江啟洲;異構(gòu)集群的作業(yè)管理及作業(yè)調(diào)度的研究與實現(xiàn)[D];華南理工大學(xué);2010年

本文編號：2827954