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

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

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

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

【引證文獻(xiàn)】

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

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

本文編號(hào)：2827954