（計(jì)算機(jī)應(yīng)用技術(shù)專業(yè)論文）基于pvm的任務(wù)調(diào)度策略的研究與實(shí)現(xiàn).pdf

中南大學(xué)碩士學(xué)位論文 摘要 并行分布計(jì)算已經(jīng)成為一種解決許多大型科學(xué)和工程問題的十分有效的方式。 影響并行分布計(jì)算性能的因素有很多，諸如任務(wù)粒度、處理機(jī)的分配和網(wǎng)絡(luò)拓?fù)涞龋?其中任務(wù)調(diào)度策略是影響其性能的關(guān)鍵，已發(fā)展成為并行處理領(lǐng)域中的研究熱點(diǎn)。 本文首先分析了調(diào)度問題的一般模型，總結(jié)了影響調(diào)度性能的各種因素。針對(duì) 這些不同的因素，本文提出了一些新的策略，改進(jìn)了某些現(xiàn)有的方法：如為了解決 集中式的任務(wù)調(diào)度策略中調(diào)度結(jié)點(diǎn)容易成為瓶頸的問題，本文提出的主動(dòng)匯報(bào)和兩 層調(diào)度的思想，使系統(tǒng)具有良好的負(fù)載平衡性能：通過引用閥值的概念，采用自適 應(yīng)的虻報(bào)方案，系統(tǒng)能夠及時(shí)準(zhǔn)確的獲取各工作站的負(fù)載信息；通過采納有效聚合和 充分釋放的思想，使系統(tǒng)具有良好的可擴(kuò)展性；為了提高系統(tǒng)的整體性能，本文采取 了多線程和消息無解包轉(zhuǎn)發(fā)技術(shù)，給出了多種任務(wù)分配策略。 借助于上述工作，結(jié)合復(fù)雜機(jī)電耦臺(tái)與解耦問題，基于可移植異構(gòu)的并行開發(fā) 環(huán)境p v m 本文設(shè)計(jì)和開發(fā)了一個(gè)可視化的并行調(diào)度程序。該系統(tǒng)具有程序模塊化 高、簡(jiǎn)單易用等優(yōu)點(diǎn)。 最后，文中以四輥軋機(jī)為例，驗(yàn)證了理論的正確性和程序的實(shí)用性。 關(guān)鍵字：兩層調(diào)度主動(dòng)報(bào)告負(fù)載平衡有效聚合充分釋放 中南大學(xué)碩士學(xué)位論文 a b s t ! a e t p a r a u e id i s 仃i b u t e dc o m p u t i i l g ( p d c ) h a sb c c o m e 叩e x n 甘e l yc f f e c t i v ew a yt o s 0 1 v em a n yp r o b l e m sl nt h el a r g e s c a l es c i e n t l f i cc o m p u t m ga i l de n g i n e e r i n g 矗e l d h o w e v e r t h e r ea r em a r 舛f 如t o r st oa f f b c t 山ec f f i c i e n c y o fp a r a l l e ld i s 砸b u t e d c o m p u t i l l g ，s l l c h 弘t a s k 掣a t i i i t y p r o c e s s o r sa 1 1 0 c a t i i l ga n dn e 御o r kt o p 0 1 0 9 y ，i nw h i c h t a s k s c h e d u l i 士】gs 仃a t e g yi s8c n l c i a lo n e 卸d 山u sh a sb e c o m e ah o tr e s e a r c hs p o ti n 出e n e l do fp a r a l l e lp r o c e s s i n g i n t h i sp a p e r f i r s t l y ，t h cg e n e r a lm o d e lo fs c h c d l l l i n gp f o b l e mi s 柏a l y z e d 卸d s t l m u l a t m 9 1 yt h ef a c t o r sa f f e c n n gt h es c h e d u l l ge f f i c i e n c ya r es u m m a r i z e d f o r 也e s e d l f r b r e n tk i n d s o ff a c t o r s ，s o m en e ws 廿a t e g l e sa r ep r o m o t e da 1 1 ds o m ei m p r o v e d m e 山o d sa r ep r o d e d ：i no r d e rt or e s o h e 血eb a n l en e c k l a c ep r o b l e m s1 nc e d t r a l i z e d t a s ks c h e d u l i n gs 嘰t e g ya n ds l m u l t a n e o l l s l yd b t a i l i 山eb e t t e rl o a db a l a n c i n gc a p a b i l i l 釩 t h e s el d e a so ft w o - t l e rs c h e d u l l n ga n da c t l v ef 印o r n n ga r ep r e s e n t e 止b yl n 仃o d u c m gt h e c 叩c e p t i o no fv a l v e 神da d o m i n gt h ea u t o a d a p t a t i 衄蚰dr e p o r t i n gm e c b a n j s m ，t h e s y s t e mc a nt l m e l ya n da c c l | r a t e l yg e t 也el o a d i f o 兀丑a t i o no fe a c hw o f k s t a t l o n ；b y l n 汀o d u c i i l gt l l e s ei d e a so fe f f i c i e n c ya g 伊e 9 8 t i d g 衄dc x h a u s t l v er e i e a s i n g ，t l l es y s t 鋤 g e tt h e b e t t e rs c a l a b l l l t y ，l o r d e rt o 皿p r o v et h e w h 0 1 es y s t e m se m c l e n c y 也e s e t e c h n o l o g i e so fm u l t i t h r e a da n dm e s s a g er e l 咖n gw i 血o u t1 l r l f o l d i i l ga r ea d o p t e da n da f e wd i f f e r e n tk i n d so ft a s ka l l o c a t i n gs 訂a t e g ya r ep f o v i d e d r e s o r t i n 衛(wèi)t ot h ea b o v ea c h l e v e m e n t sa n dc o m b i n e dw l t l lt h ep r o b l e m so fc o m p l e x e k c 缸o(hù) m e c h a n i c a lc o i 單l i n gs y s t 鋤，av i s i b l ep a r a l l e ls c h e d l d i n gp r 0 野a m ，w h i c h p o s s e s s e sm a l l yv l n u e ss u c ha se a s y t o u s ea 1 1 d h l g h l ym o d u l 撕z a t i o n ，i sd e s l g n e d 蛆d r e a l i z e d ，w h i c h1 5 b a s e do nt h ee a s y t o 一廿a n s p l 姐tp a r a l l e l ，d c v e l o p e de n v i r o n m e n tp v m f m a l l y ，a na p p l i c a t i o ni n s t a n c eo fr o l l i n gm i l l 】st a l ( e = 1f o ra ne x 帥p l ea n dm e v a l i d i t yo f 仕圮t h e o r y 如dt h ep t a c t i c a b i l i ho f 也cp r o 盯a ma r ep r o v e d k e y w o r d 3 ：t w o - t i 盯s c h e d u 抽g ； e f f i c i e n c ya g 鬻e g a t i g ； a 吐1 v cr 印饑恤g l o a db a l a c m g j e x h a u s t i v er e l e a s i n g ： 中南大學(xué)碩士學(xué)盥論文 第一章緒論 隨著科學(xué)在各個(gè)方向的不斷發(fā)展，科學(xué)計(jì)算的復(fù)雜度正不斷加大，計(jì)算的精度 也要求越來越高。同時(shí)，低廉的徽處理機(jī)以及通信技術(shù)的提高極大的推動(dòng)了分布式 并行系統(tǒng)的發(fā)展，這些系統(tǒng)具有高性能比、高可用性和可擴(kuò)展性等主要優(yōu)點(diǎn)- 因而 成為解決科學(xué)計(jì)算的一個(gè)良好方案。然而，目前分布式并行系統(tǒng)中還存在許多問題 亟待解決。 1 1 分布式系統(tǒng)與并行計(jì)算 隨著網(wǎng)絡(luò)和分布式系統(tǒng)的出現(xiàn)，單機(jī)孤立使用的時(shí)代已經(jīng)過去。新一代計(jì)算機(jī) 軟件的開發(fā)都開始考慮用“分布”、“并行”的思想來實(shí)現(xiàn)5 ”。分布和并行意味著資 源利用率和計(jì)算效率的提高。并行處理技術(shù)已經(jīng)發(fā)展成為當(dāng)前計(jì)算機(jī)技術(shù)的主要研 究方向之一”而且已經(jīng)應(yīng)用于許多大型的科學(xué)計(jì)算和工程應(yīng)用之中。 1 1 1 現(xiàn)代科學(xué)技術(shù)對(duì)計(jì)算能力的需求 當(dāng)今，計(jì)算科學(xué)已經(jīng)和傳統(tǒng)的兩種科學(xué)，即理論科學(xué)和試驗(yàn)科學(xué)，并列成為第 三門科學(xué)，他們彼此相輔相成地推動(dòng)著科學(xué)的發(fā)展和社會(huì)的進(jìn)步。隨著計(jì)算機(jī)和計(jì) 算方法的飛速發(fā)展，幾乎所有的學(xué)科都走向定量化和精確化，從而產(chǎn)生了一系列諸 如計(jì)算物理，計(jì)算化學(xué)，計(jì)算地質(zhì)學(xué)、計(jì)算氣象學(xué)和計(jì)算材料科學(xué)等等計(jì)算科學(xué)。 在許多情況下比如，理論模型復(fù)雜甚至理論尚未建立，或者試驗(yàn)費(fèi)用昂貴甚至試 驗(yàn)無法進(jìn)行此時(shí)計(jì)算就成為求解問題的唯一或主要手段。在諸如預(yù)測(cè)模型的模型 和模擬、工程設(shè)計(jì)和自動(dòng)化、能源勘探、醫(yī)學(xué)、軍事咀及基礎(chǔ)理論研究等領(lǐng)域中反 而對(duì)計(jì)算提出了極高的具有挑戰(zhàn)性的要求。 例如，中期數(shù)值天氣預(yù)報(bào)的時(shí)效每增加一天計(jì)算機(jī)的速度就要大約提高一個(gè) 數(shù)量級(jí)。傲三天的數(shù)值天氣預(yù)報(bào)需要每秒百萬次運(yùn)算操作的計(jì)算機(jī)。又如，在進(jìn)行 油田整體“油藏模擬”時(shí)假定一個(gè)油田有上萬口井，每口井模擬至少要取8 x 8 x 5 0 個(gè)點(diǎn)，則總的變量數(shù)可高達(dá)千萬量級(jí)，使得現(xiàn)今的計(jì)算機(jī)難以實(shí)現(xiàn)。其他的應(yīng)用 領(lǐng)域包括核武器數(shù)值模擬。航空航天高速飛行器的設(shè)計(jì)。原子物理過程微觀世界的 模擬材料科學(xué)中的計(jì)算環(huán)境資源以及生物計(jì)算等。這些重大的計(jì)算問題，涉及 到非規(guī)則的復(fù)雜結(jié)構(gòu)、非均勻的復(fù)合材料、非線性的動(dòng)力學(xué)系統(tǒng)以及奇性區(qū)域、話 動(dòng)邊界、帶約束條件等各種復(fù)雜的數(shù)學(xué)物理問題。要對(duì)這些復(fù)雜的非線性數(shù)學(xué)物理 方程進(jìn)行大規(guī)模和高精度的計(jì)算，在一般的計(jì)算機(jī)上采用傳統(tǒng)的計(jì)算方法往往是無 能為力的。正是這些高性能計(jì)算的需求，不斷地推動(dòng)并行處理技術(shù)的發(fā)展。 中南大學(xué)碩士學(xué)位論文 1 1 2 并行計(jì)算技術(shù)的發(fā)展現(xiàn)狀 并行和分布計(jì)算技術(shù)自6 0 年代中期和7 0 年代后期分別出現(xiàn)以來，其處理方式 經(jīng)歷了從陣列機(jī)、向量機(jī)及向量并行機(jī)、共享存儲(chǔ)的對(duì)稱多處理器系統(tǒng)( s m p ) 、分 布存儲(chǔ)的大規(guī)模并行處理系統(tǒng)( m p p ) 到非一致訪問的分布共享存儲(chǔ)( n u m a ， n d n u n j f o n l lm e m o r ya d d r e s s ) 并行機(jī)系統(tǒng)和計(jì)算機(jī)機(jī)群系統(tǒng)( c l u s t e r s ) 的演變過 程。 當(dāng)前。并行和分布計(jì)算發(fā)展的基本狀況是：并行軟件的發(fā)展遠(yuǎn)遠(yuǎn)落后于并行和 分布計(jì)算體系結(jié)構(gòu)的發(fā)展；并行和分布計(jì)算應(yīng)用遠(yuǎn)遠(yuǎn)落后于并行和分布計(jì)算技術(shù)的 發(fā)展：向盡量采用商品化的軟、硬件甚至系統(tǒng)來構(gòu)成并行和分布計(jì)算系統(tǒng)平臺(tái)的方 向發(fā)展：計(jì)算系統(tǒng)的規(guī)?？缮炜s性和可編程性已經(jīng)成為并行和分布計(jì)算系統(tǒng)進(jìn)一步 發(fā)展的一個(gè)主要矛盾。 規(guī)?？缮炜s并行計(jì)算機(jī)群系統(tǒng)能以最低可能成本向用戶提供最高可能性能，因 此成為并行和分布計(jì)算技術(shù)發(fā)展的主流，加上可移植異構(gòu)編程環(huán)境p v m ( p a r a l l e l v i n u a lm a c h i n e ) 【2 0 2 1 ，3 4 3 5 1 日益流行和標(biāo)準(zhǔn)的消息傳送平臺(tái)m p i ( m e s s a g e p a s s i n g i n t e r f a c e ) 并行編程環(huán)境的日益普及將進(jìn)一步推動(dòng)并行和分布計(jì)算應(yīng)用的發(fā)展。 1 2 并行計(jì)算中任務(wù)調(diào)度策略的研究現(xiàn)狀 在分布式并行計(jì)算中，要能夠發(fā)揮其高性能比、高可用性和可擴(kuò)展性的優(yōu)點(diǎn)， 系統(tǒng)設(shè)計(jì)人員必須解決好分布式系統(tǒng)中任務(wù)分配的問題，即任務(wù)調(diào)度策略。任務(wù)調(diào) 度策略是指合理地分配子任務(wù)到各個(gè)工作站，保證總?cè)蝿?wù)在最短時(shí)間內(nèi)完成。目前， 對(duì)任務(wù)調(diào)度繁略的研究主要集申在以下幾個(gè)方面： ( 1 ) 集中式的調(diào)度策略和分布式的調(diào)度策略 集中式的調(diào)度策略由一個(gè)處理機(jī)維護(hù)一個(gè)任務(wù)分布表，并由這個(gè)處理機(jī)負(fù)責(zé)任 務(wù)的分配。分布式任務(wù)的調(diào)度策略不再有一個(gè)集中的處理機(jī)管理任務(wù)分配表，每個(gè) 處理機(jī)只與一部分處理機(jī)通信。每個(gè)處理器都參與負(fù)載平衡【1 0 1 6 1 9 4 ”控制它只需 了解周邊處理視的局部負(fù)載信息，通過滲透方式或交換方式將負(fù)載均勻她分?jǐn)车较?統(tǒng)的各個(gè)處理機(jī)上。二者各有優(yōu)點(diǎn)：集中式的實(shí)現(xiàn)方便，但容易出現(xiàn)瓶頸問題；分 布式的實(shí)現(xiàn)復(fù)雜。 ( 2 ) 任務(wù)劃分問題 任務(wù)粒度1 對(duì)于分布式系統(tǒng)中任務(wù)分配策略的確定具有重要的意義。對(duì)于所有 任務(wù)調(diào)度算法，任務(wù)粒度都是一個(gè)影響其性能的重要因素。在分布式系統(tǒng)中。由于 不同結(jié)點(diǎn)之間進(jìn)程通訊開銷較大，過細(xì)的任務(wù)粒度會(huì)使通訊的開銷增長(zhǎng)，抵消并行 計(jì)算帶來的好處。因此在分布式系統(tǒng)中，人們一直都追求大粒度的任務(wù)。然而。 對(duì)于什么才算“大粒度”的任務(wù)，目前尚在研究。另外，如何將任務(wù)按照通信開銷 2 中南大學(xué)碩士學(xué)位論文 劃分成適當(dāng)數(shù)目的邏輯組。也是目前的研究熱點(diǎn)。 ( 3 ) 任務(wù)遷移1 4 0 】 為了實(shí)現(xiàn)負(fù)載平衡，有時(shí)需要將正在運(yùn)行的任務(wù)從一個(gè)處理機(jī)遷移到另外一個(gè) 處理機(jī)，這就是任務(wù)遷移。任務(wù)遷移要能夠達(dá)到透明性、可伸縮性、并行性、異構(gòu) 性等要求。進(jìn)程遷移時(shí)要收集己執(zhí)行任務(wù)的虛存映像、進(jìn)程控制快、沒讀的消息和 i ，o 緩沖區(qū)、文件指針和已設(shè)置的定時(shí)器等由于收集這些狀態(tài)信息是比較困難的。 所以任務(wù)遷移實(shí)現(xiàn)起來難度很大，一直是學(xué)術(shù)界的研究焦點(diǎn)。 ( 4 ) 負(fù)載信息3 “j 收集策略 要獲得良好的負(fù)載平衡在任務(wù)分配和再分配時(shí)就要收集系統(tǒng)的負(fù)載信息。何時(shí) 收集何種負(fù)載信息也一直是學(xué)術(shù)界研究的熱點(diǎn)。目前的負(fù)載信息指標(biāo)主要有：行隊(duì)列 中的任務(wù)數(shù)、系統(tǒng)調(diào)用的頻率、c p u 上f 文的切換率、空閑c p u 時(shí)間百分比、空閑存 儲(chǔ)器的大小( k 字節(jié)) 以及每分鐘的平均負(fù)載等。對(duì)于負(fù)載信息收集策略主要有三種： 周期性收集策略、命令驅(qū)動(dòng)策略、狀態(tài)變化驅(qū)動(dòng)策略。 ( 5 ) 網(wǎng)絡(luò)并行計(jì)算的可伸縮性p 1 在網(wǎng)絡(luò)并行計(jì)算中，一個(gè)關(guān)鍵問題是用戶如何有效地利用整個(gè)網(wǎng)絡(luò)的系統(tǒng)資源， 其中最重要的就是處理機(jī)資源?？缮炜s性是指并行系統(tǒng)如何根據(jù)問題的規(guī)模自動(dòng)的 伸展( g r o w i n g ) 、收縮( s h r i n k j n g ) 和調(diào)節(jié)負(fù)載平衡( l o a db a l a n c i n g ) 。 1 3 課題背景 本文的研究工作是在“復(fù)雜機(jī)電系統(tǒng)耦合與解耦設(shè)計(jì)理論與方法”( 國(guó)家自然科 學(xué)基金重點(diǎn)項(xiàng)目) 項(xiàng)目上開展的。該基金項(xiàng)目針對(duì)于現(xiàn)代大型復(fù)雜機(jī)電系統(tǒng)性能與 運(yùn)行狀態(tài)是多種物理過程和多類參數(shù)耦臺(tái)結(jié)果的這一事實(shí)，以冶金機(jī)械為研究結(jié)合 點(diǎn)，運(yùn)用數(shù)學(xué)物理理論與方法，分析系統(tǒng)中各個(gè)因素動(dòng)態(tài)交互作用的機(jī)理，建立多 種網(wǎng)絡(luò)式全局耦合數(shù)學(xué)模型，通過解耦分析和模型求解，研究復(fù)雜機(jī)電系統(tǒng)功能、 奇異工況、故障狀態(tài)的生成機(jī)制，研究耦合并行設(shè)計(jì)方法以實(shí)現(xiàn)復(fù)雜機(jī)電系統(tǒng)全 局最優(yōu)設(shè)計(jì)2 ”。 復(fù)雜機(jī)電系統(tǒng)中普遍存在由多種物理過程( 力學(xué)過程、熱流過程、運(yùn)動(dòng)過程、 物質(zhì)性變過程、工藝過程等) 同時(shí)交互影響某一物理過程的耦合現(xiàn)象【2 ”由于這種 多過程、多因素的耦合具有內(nèi)在的分布性( 時(shí)間、空間及功能上的分布) ，在并行工 程及其相關(guān)學(xué)科的發(fā)展推動(dòng)下，從分布式并行協(xié)同求解角度進(jìn)行解耦研究，成為復(fù) 雜機(jī)電系統(tǒng)設(shè)計(jì)的重要方向膽“。采用分布式并行協(xié)同求解機(jī)制在局域阿上用多臺(tái) 計(jì)算機(jī)模擬多個(gè)專家的協(xié)同工作方式，更接近專家求解問題的模式【2 6 】。 1 4 研究目標(biāo)和研究意義 主塑查蘭堡主蘭垡堡蘭 本文在已有并行工程理論和方法研究的基礎(chǔ)上，開展了以下幾個(gè)方面的研究工 作： ( 1 ) 研究并行分布計(jì)算的處理機(jī)調(diào)度中的相關(guān)問題包括負(fù)載平街策略、負(fù)載 信息收集策略。 ( 2 ) 研究消息傳遞軟件系統(tǒng)p v m 的使用及其通信技術(shù)的實(shí)現(xiàn)： ( 3 ) 研究計(jì)算資源的可擴(kuò)展性?？蓴U(kuò)展并行計(jì)算是當(dāng)今研究的一大視點(diǎn)，研究 計(jì)算資源的可擴(kuò)展性是指如何在運(yùn)算中，根據(jù)實(shí)際情況實(shí)現(xiàn)系統(tǒng)資源的動(dòng)態(tài)增長(zhǎng)、 減小，并在此過程中保持系統(tǒng)穩(wěn)定。 ( 4 ) 歸納總結(jié)影響調(diào)度性能的因素。 ( 5 ) 以四輥軋機(jī)全局動(dòng)力學(xué)耦合模型求解為例，驗(yàn)證本文理論方法的正確性和 實(shí)用性。 1 5 研究方法和技術(shù)路線 i 求解方法分布式并行協(xié)同求解方法 針對(duì)復(fù)雜機(jī)電耦臺(tái)中存在著大量的計(jì)算問題，包括大規(guī)模矩陣的相乘和形如 x = a x + bu ( 其中a ，b ，u 均代表系數(shù)矩陣，x = 【1 】，x 2 ，x n 】) 的微分方程組的求解這類問 題中矩陣的維數(shù)常常達(dá)到幾百維甚至幾千維，而且對(duì)微分方程組的求解常采用迭代 法，迭代次數(shù)事先不能確定，系數(shù)矩陣在計(jì)算的過程中需要不斷調(diào)整，從而導(dǎo)致了計(jì)算 的復(fù)雜性。鑒于以上的特點(diǎn)。我們采用分布式并行協(xié)同方法進(jìn)行復(fù)雜機(jī)電系統(tǒng)中耦合 和解耦模型的求解i ”1 2 硬件環(huán)境網(wǎng)絡(luò)并行計(jì)算環(huán)境 網(wǎng)絡(luò)并行環(huán)境是近年來國(guó)際上并行環(huán)境的重要方向。網(wǎng)絡(luò)并行計(jì)算【2 “，就是通 過高速信息網(wǎng)絡(luò)，充分利用網(wǎng)上的計(jì)算資源，實(shí)現(xiàn)大型問題的并行計(jì)算。 網(wǎng)絡(luò)并行具有投資少、見效快、靈活性強(qiáng)等優(yōu)點(diǎn)。國(guó)內(nèi)外經(jīng)驗(yàn)表明，除了少數(shù) 固定的計(jì)算機(jī)大戶( 如天氣預(yù)報(bào)、地震勘探和主要國(guó)防部門等) 外，很多用戶并不 經(jīng)常需要超級(jí)計(jì)算，也就不必每個(gè)單位購置昂貴的高性能并行機(jī)一旦需要，可通 過網(wǎng)絡(luò)實(shí)現(xiàn)超級(jí)計(jì)算的目的。由于高速信息網(wǎng)絡(luò)的低通信延遲與高帶寬性能，國(guó)際 上越來越多的大學(xué)和研究所都在用網(wǎng)絡(luò)并行解決大型計(jì)算問題。利用實(shí)驗(yàn)室已有的 計(jì)算資源我們構(gòu)造一個(gè)由多臺(tái)p c 機(jī)通過局域網(wǎng)連接而成的網(wǎng)絡(luò)并行計(jì)算環(huán)境。 3 軟件系統(tǒng)一一p v m 軟件系統(tǒng) 網(wǎng)絡(luò)并行需要一個(gè)可移植的網(wǎng)絡(luò)計(jì)算環(huán)境使用戶能在通用平臺(tái)上運(yùn)行程序。 對(duì)已有的程序不必作大的改動(dòng)就能夠使在該環(huán)境下編寫的程序可以在其它可移植的 編程環(huán)境下運(yùn)行。 d 中南大學(xué)碩士學(xué)位論文 目前工作站并行機(jī)群系統(tǒng)都采用消息傳遞型編程模型。這種顯式消息傳遞模型 由于克服了傳統(tǒng)并行機(jī)兼容性差的缺點(diǎn)，能夠適應(yīng)于異構(gòu)型并行機(jī)并且具有方便用 戶編程、易于移植和易于實(shí)現(xiàn)的特點(diǎn)。當(dāng)前主要的消息傳遞軟件系統(tǒng)中，p v m ( p a r a l l e iv i r t u em a c h i n e ) 軟件因?yàn)橄到y(tǒng)規(guī)模小，而且可在核心上擴(kuò)充附屬功能層， 同時(shí)也是可自由獲取的公開軟件，因此p v m 軟件在分子動(dòng)力學(xué)模擬、超導(dǎo)研究和 氣象科學(xué)等領(lǐng)域得到了廣泛的應(yīng)用。在我國(guó)研制成功的并行機(jī)曙光1 0 0 0 以及北航 正在研制的可擴(kuò)展并行機(jī)群之上都移植了p v m 系統(tǒng)【3 0 j 。 鑒于目前一般用戶使用的p c 機(jī)都是w i n 3 2 操作系統(tǒng)，因而使用w i n 3 2 版本的 p v m 軟件包。 本文結(jié)合復(fù)雜機(jī)電系統(tǒng)耦合模型求解問題，實(shí)現(xiàn)了一個(gè)調(diào)度系統(tǒng)，并使用該系 統(tǒng)解決了四輥軋機(jī)全局動(dòng)力學(xué)耦臺(tái)模型的求解問題。實(shí)踐證明使用本系統(tǒng)進(jìn)行并 行計(jì)算具有高透明性、靈活性和高效性的特點(diǎn)。 1 6 論文結(jié)構(gòu) 本文結(jié)構(gòu)如下： 第一章論述本文的課題背景，研究的目標(biāo)、意義和研究所采用的路線和方法。 第二章詳述了并行虛擬機(jī)( p v m ) 的體系和其通信機(jī)制。 第三章詳述了調(diào)度策略的一般問題，包括調(diào)度模型、影響調(diào)度的一般性因素和 一般的調(diào)度策略。 第四章詳述了本文調(diào)度策略的思想，包括任務(wù)的描述，目標(biāo)機(jī)器的描述以及具 有兩層調(diào)度策略和主動(dòng)匯報(bào)等優(yōu)點(diǎn)的基于p v m 的調(diào)度策略。 第五章詳述了本文調(diào)度策略的具體實(shí)現(xiàn)描述了相關(guān)的數(shù)據(jù)結(jié)構(gòu)和主要算法。 第六章詳述了本文的調(diào)度系統(tǒng)的一個(gè)具體應(yīng)用。 第七章總結(jié)了本文的研究成果，展望了未來的研究工作。 5 中南大學(xué)碩士學(xué)位論文 第二章并行虛擬機(jī)p v m 近年來，基于消息傳遞的并行處理方式越來越受到人們的重視。p v m ( p a r a l l e l v i r t u a im a c h i n e ) 正是這樣一個(gè)軟件系統(tǒng)。它允許用戶將通過網(wǎng)絡(luò)相互連接的眾多 異種機(jī)看成是單一的虛擬并行計(jì)算機(jī)系統(tǒng)，這些異種機(jī)可以是多處理機(jī)系統(tǒng)，也可 以是工作站或p c 機(jī)，而異種機(jī)之間的消息傳遞、數(shù)據(jù)轉(zhuǎn)換和任務(wù)分配等均由p v m 以透明的方式自動(dòng)完成。所以對(duì)應(yīng)用程序來講p v m 是一個(gè)基于消息傳遞的分布式 并行計(jì)算環(huán)境。 p v m 軟件是由o a kr i d g en a t i o n a il a b o r a t o r y ( o r n l ) 的a 1g e i s t 和e m o r y u n i v e r s i t y 的v a i d ys u n d e r a m u 等人研制的，主要參與的機(jī)構(gòu)有美國(guó)的o a kr i d g e 國(guó) 家實(shí)驗(yàn)室，田納西大學(xué)、e m o 唱大學(xué)、卡內(nèi)基梅隆大學(xué)等，同時(shí)。本項(xiàng)目還得到了 美國(guó)能源部、國(guó)家自然科學(xué)基金會(huì)和田納西州政府的資助。 2 1p v m 系統(tǒng)的組成與結(jié)構(gòu) 從軟件結(jié)構(gòu)上講p v m 由兩部分組成l 】：第一部分是后臺(tái)常駐進(jìn)程p v md a e m o n ( p v m d ) ，駐留在構(gòu)成虛擬機(jī)的每臺(tái)用戶計(jì)算機(jī)上，用戶配置虛擬機(jī)時(shí)，首先在一臺(tái) 機(jī)器上啟動(dòng)p v m ，然后該p v m d ( 主p v m d ) 自動(dòng)啟動(dòng)其它機(jī)器上的p v m d ( 從p v m d ) 各p v m d 協(xié)同工作完成整個(gè)虛擬機(jī)的維護(hù)、任務(wù)的控制、消息的傳遞等工作；第 二部分是p v m 用戶接口庫l i b p v m i b 。主要提供了與用戶的接口函數(shù)使用戶程序 更方便地利用p v m 提供的機(jī)制和資源該函數(shù)庫主要包含了用于消息傳遞、啟動(dòng) 進(jìn)程、調(diào)度任務(wù)及修改虛擬機(jī)的配置等函數(shù)。p v m 虛擬機(jī)的結(jié)構(gòu)m 可用圖2 1 表示。 圖2 1 p v m 虛擬機(jī)結(jié)構(gòu) 6 中南大學(xué)碩士學(xué)位論文 從p v m 虛擬機(jī)結(jié)構(gòu)可以看出：多個(gè)位于網(wǎng)絡(luò)中不同機(jī)器上的p v m d 構(gòu)成了p v m 虛擬機(jī)的核心。這些機(jī)器的體系結(jié)構(gòu)可能都不同，但都支持t c p ，i p 網(wǎng)絡(luò)協(xié)議，調(diào)用 p v m 庫函數(shù)的用戶應(yīng)用程序稱為p v m 任務(wù)，它們是完成并行應(yīng)用實(shí)際工作的主體。 被加載到虛擬機(jī)中后，由p v m 管理并被分配到某臺(tái)具體機(jī)器中運(yùn)行。從兩位于不 同機(jī)器上的任務(wù)真正并行地被執(zhí)行。 2 2p v m 清息通信機(jī)制 p v m 系統(tǒng)最主要的功能就是支持消息傳遞型的并行程序設(shè)計(jì)，所以p v m 系統(tǒng) 最核心的部分就是實(shí)現(xiàn)p v m 任務(wù)間的通信。 p v m 系統(tǒng)基于t c p i p 和u d p 協(xié)議集，實(shí)現(xiàn)了p v m d 之間、p v m 任務(wù)和口v m d 之間以及p v m 任務(wù)之間三種通信，3 3 ，3 4 ，3 ”圖2 2 是p v m 消息通信機(jī)制示意圖。 p v m d 之間的通信采用u d p 協(xié)議。u d p 協(xié)議提供一種不可靠的數(shù)據(jù)包服務(wù)，它 可能導(dǎo)致數(shù)據(jù)包的丟失、重復(fù)或無序。因此p v m 系統(tǒng)采用了應(yīng)答重發(fā)機(jī)制以實(shí) 圖22 p v m 消息通信機(jī)制示意斟 現(xiàn)可靠有序的數(shù)據(jù)包傳輸機(jī)制。p v m 任務(wù)與p v m d 之間是通過t c p 協(xié)議通信的，這 是一種面向連接的可靠的傳輸控制協(xié)議，不需要應(yīng)答和重發(fā)機(jī)制。然而。t c p 提供 字節(jié)流服務(wù)。沒有設(shè)置報(bào)文邊界，p v m 系統(tǒng)通過在數(shù)據(jù)包的報(bào)頭加入數(shù)據(jù)包長(zhǎng)度來 設(shè)置報(bào)文邊界p v m 任務(wù)之間也是通過t c p 協(xié)議進(jìn)行通信的，p v m d 作為p v m 任 務(wù)問通信的路由器 在一個(gè)節(jié)點(diǎn)機(jī)內(nèi)p v m 任務(wù)是如何與p v m d 建立連接的呢? 由于p v m 任務(wù)創(chuàng)建 的動(dòng)態(tài)性- p v m d 無法確知應(yīng)該和哪些任務(wù)連接因此口v m d 啟動(dòng)時(shí)設(shè)立一s o c k e t 賦予某一特定地址，并將此地址寫入一個(gè)地址文件，p v m d 由此s o c k e t 監(jiān)聽來自p v m 任務(wù)的連接請(qǐng)求。當(dāng)p v m 任務(wù)創(chuàng)建時(shí)調(diào)用p v m m ”i d ( ) 函數(shù)，該函數(shù)首先創(chuàng)建對(duì) 7 中南大學(xué)碩士學(xué)位論文 應(yīng)p v m d 的t t p c b 結(jié)構(gòu)和其中的s o c k e t ，然后從地址文件中查到p v m d 的監(jiān)聽s o c k e t 地址，并從t t d c b 結(jié)構(gòu)中的s o c k e t 向此監(jiān)聽s o c k e t 發(fā)出聯(lián)接請(qǐng)求p v m d 收到連接 請(qǐng)求后，創(chuàng)建新t a s k 結(jié)構(gòu)和結(jié)構(gòu)中與該任務(wù)連接的s o c k e t ，而監(jiān)聽s o c k e t 保留繼續(xù) 監(jiān)聽，然后p v m 任務(wù)再和p v m d 通過系統(tǒng)內(nèi)的兩次控制消息請(qǐng)求確定有關(guān)任務(wù)和 鋤k 結(jié)構(gòu)的些參數(shù)，連接即告完成，然后就可以進(jìn)行消息通信了。 發(fā)送一個(gè)消息一般采用三步進(jìn)行。一個(gè)消息傳遞的具體過程是：先調(diào)用 p v r l i n i t s e n d ( ) 生成一個(gè)空發(fā)送緩沖區(qū)，然后用一組p v r n - p p ( ) 函數(shù)將傳送消息中的 各種類型的數(shù)據(jù)壓入緩沖區(qū)，最后用p v ms e n d ( ) 函數(shù)將發(fā)送緩沖區(qū)內(nèi)的數(shù)據(jù)發(fā)送出 去。 任務(wù)調(diào)用p v m 函數(shù)發(fā)送時(shí)，通過與p v m d 連接的s o c k e t 發(fā)送數(shù)據(jù)塊，由于流方 式傳輸不限傳輸量大小，為了保證接收方能夠明確讀入量的大小，傳輸時(shí)要在數(shù)據(jù) 塊的前面附加頭結(jié)構(gòu)信息，指明本次傳送數(shù)據(jù)塊的源、目的和長(zhǎng)度。p v m d 讀數(shù)據(jù) 時(shí)采用兩次讀方式首先讀入一個(gè)頭結(jié)構(gòu)信息，明確待收數(shù)據(jù)塊的大小，再按該值 讀入數(shù)據(jù)，從而完成一個(gè)數(shù)據(jù)塊的接收過程，p v m d 將數(shù)據(jù)塊內(nèi)數(shù)據(jù)轉(zhuǎn)存入一個(gè)報(bào) 文結(jié)構(gòu)，再如入到對(duì)應(yīng)目的節(jié)點(diǎn)機(jī)的h o s t d 結(jié)構(gòu)的發(fā)送隊(duì)列中，p v m d 之間采用u d p 方式通訊并使用一個(gè)出錯(cuò)重發(fā)控制協(xié)議，從而保證報(bào)文能正確地到達(dá)目的端，并且 保證發(fā)送接收順序的一致性。目的p v m d 按順序接收到報(bào)文后將根據(jù)報(bào)文目的域 值將報(bào)文轉(zhuǎn)放到對(duì)應(yīng)該目的任務(wù)的描述結(jié)構(gòu)t a s k 的發(fā)送隊(duì)列中然后p v m d 將通過 和任務(wù)連接的流s o c k e t 將報(bào)文內(nèi)的數(shù)據(jù)發(fā)往對(duì)應(yīng)的目的任務(wù)。 目的任務(wù)是以兩次讀方式從與p v m d 聯(lián)接的流s o c k e t 中讀入數(shù)據(jù)塊。消息中各 數(shù)據(jù)塊以原發(fā)送順序到達(dá)目的任務(wù)。目的任務(wù)只需將從同一源而來的數(shù)據(jù)塊按順序 鏈入同一u m b u f 中即可。當(dāng)屬于同一消息的最后一個(gè)數(shù)據(jù)塊加入了對(duì)應(yīng)u m b u f 內(nèi)， 該u m b u f 將被加入一個(gè)接收緩沖區(qū)鏈表內(nèi)等待任務(wù)處理。目的任務(wù)調(diào)用p v mr e c v ( ) ( 阻塞接收) 或p v m n r e c v ( ) ( 非阻塞接收) 找到所需消息接收緩沖區(qū)，然后一組對(duì) 應(yīng)的p v m u p ( ) 函數(shù)將各種類型的數(shù)據(jù)從消息中取出。這樣就完成了一個(gè)消息傳遞 過程。 2 3p h 通信模型 p v m 通信模型假定任意的任務(wù)都可以將消息發(fā)送給其它的任務(wù)而且消息的大 小和數(shù)量在原則上是沒有限制的。p v m 保證消息發(fā)送的順序，接收方從而可以以相 同的順序接收消息m l 。 p v m 通信模型支持異步阻塞發(fā)送。消息發(fā)送方不必等待接收方的反饋信息。發(fā) 送方一旦把消息發(fā)送出去就可以繼續(xù)執(zhí)行下面的計(jì)算消息緩沖區(qū)即可刪除或重 中南大學(xué)碩士學(xué)位論文 新使用，具體的發(fā)送由p v m d 負(fù)責(zé)。消息到達(dá)接收端后保存在緩沖區(qū)中，直到有接 收者為止。只要接收端存在，p v m 便能可靠地將消息發(fā)出。異步阻塞發(fā)送使得p v m 用戶無需擔(dān)心會(huì)因?yàn)閟 e n d r e c e i v e 不匹配而引起死鎖，也不必?fù)?dān)心消息會(huì)在發(fā)送之 后再重寫入緩沖區(qū)中。 p v m 提供阻塞接收、非阻塞接收和限時(shí)接收三種方式。采用阻塞接收時(shí)，在消 息到達(dá)之前，任務(wù)處于等待狀態(tài)，在等待過程中不消耗c p u 時(shí)間。而采用非阻塞接 收時(shí)，任務(wù)在消息到達(dá)之前可繼續(xù)執(zhí)行，但需要不斷查詢消息是否已經(jīng)到達(dá)。限時(shí) 接收時(shí)由用戶設(shè)定等待時(shí)間當(dāng)超過了給定的時(shí)間而沒有消息時(shí)就返回。消息在發(fā) 送和接收之間不用提供反饋信息，系統(tǒng)會(huì)很安全地發(fā)送和緩沖消息。 2 4 消息傳遞用戶接口 p v m 應(yīng)用程序由分布在虛擬機(jī)上的多個(gè)進(jìn)程構(gòu)成，每個(gè)進(jìn)程負(fù)責(zé)一定的計(jì)算和 處理任務(wù)，通過調(diào)用p v m 的庫函數(shù)并借助于p v m d 與其它進(jìn)程進(jìn)行通信和協(xié)調(diào)。p v m 中的進(jìn)程稱為任務(wù)，由任務(wù)標(biāo)識(shí)符t i d 標(biāo)識(shí)。 p v m 庫函數(shù)提供給用戶創(chuàng)建p v m 任務(wù)、構(gòu)造虛擬機(jī)、任務(wù)間通信等功能。下 面介紹如何利用p v m 函數(shù)進(jìn)行任務(wù)創(chuàng)建、任務(wù)間消息傳遞等【2 1 - 3 4 - 3 5 】( 只寫出c 版 本的p v m 庫函數(shù)) 。 ( 1 ) p v m 進(jìn)程通過調(diào)用函數(shù)p v m m ”i d ( ) 進(jìn)入p v m 同時(shí)獲得自己的t i d ： jn t t i d = p v m m y t i d ( ) ( 2 ) 函數(shù)p v l s p a w n ( ) 用于生成p v m 的子任務(wù)。其調(diào)用格式為： i n t n u m t = p v m s p a w n ( c h a t a s k ， c h a 一a r g v ， i n tf l a g ， c h a w h e r e ， i n tn t a s k ， i n t + t i d s ) 其中： t a s k 為可執(zhí)行文件名： a r g v 指向一個(gè)傳遞給t a s k 的參數(shù)數(shù)組，缺省值為n u l l ： f l a g 給出一些選項(xiàng)，如p v m 協(xié)k d e f a u l t 表示由p v m 決定在哪臺(tái)結(jié)點(diǎn)機(jī)上創(chuàng)建 任務(wù)；p v m t a s k h o s t 表示在由w h e r e 指定的結(jié)點(diǎn)機(jī)上創(chuàng)建任務(wù)：p v m t a s j 晴r c h 表示 在符合w h e r e 指定的p v m a r c h 的結(jié)點(diǎn)機(jī)上創(chuàng)建任務(wù)： w h e r e 當(dāng)f l a g 為p v m 億k h o s t 或p v m l k k a r c h 時(shí)用于指定機(jī)器名或結(jié)點(diǎn)機(jī)的類 型名： n t k 給出要求生成的任務(wù)數(shù)： t i d s 是一個(gè)至少有n t a s k 個(gè)元素的整型數(shù)組，它返回所創(chuàng)建的任務(wù)的t i d 或錯(cuò)誤 碼： 9 中南犬學(xué)碩士學(xué)位論文 ( 3 )p v m 中消息的發(fā)送分為三個(gè)步驟： a 建立并初始化緩沖區(qū) i n t b u f i d = p v m j n i t s e n d ( i n te n c o d i n g ) ，適用于只使用一個(gè)發(fā)送緩沖區(qū) i n t b u f i d = p v m m k b u f ( i n te n c o d n g ) 們蓋用于需要同時(shí)使用多個(gè)發(fā)送緩沖區(qū) 其中： b u f i d 返回所創(chuàng)建的緩沖區(qū)的整數(shù)標(biāo)識(shí)符。 e n c 。d i n g 給出數(shù)據(jù)打包時(shí)使用的數(shù)據(jù)編碼類型，有以下幾個(gè)值： p v m d a t a d e f a u l t ：使用x d r 編碼，這是一種為不同結(jié)點(diǎn)機(jī)之間的數(shù)據(jù)傳輸而設(shè) 計(jì)的與結(jié)點(diǎn)機(jī)的類型無關(guān)的數(shù)據(jù)表達(dá)格式，當(dāng)虛擬機(jī)內(nèi)節(jié)點(diǎn)機(jī)之間具有不同內(nèi)部數(shù) 據(jù)格式時(shí)，p v m 通過x d r 編碼來實(shí)現(xiàn)數(shù)據(jù)傳輸； p v m d a t a r a w ：不對(duì)數(shù)據(jù)進(jìn)行任何編碼，只能用于具有相同數(shù)據(jù)格式的節(jié)點(diǎn)機(jī) 之間的數(shù)據(jù)傳輸，這種方法可以節(jié)省數(shù)據(jù)編碼和解碼的時(shí)間： p v m d a t a l n pj a c e ：打包時(shí)不拷貝數(shù)據(jù)至緩沖區(qū)而僅將數(shù)據(jù)長(zhǎng)度及指向數(shù)據(jù)的指 針存放在發(fā)送緩沖區(qū)中。如果用戶在數(shù)據(jù)打包之后及發(fā)送之前修改了己打包的數(shù)據(jù)， 則發(fā)送的是修改后的數(shù)據(jù)。這種方法可以減少數(shù)據(jù)在內(nèi)存間的拷貝次數(shù)從而提高效 率，另外用戶可以對(duì)某些數(shù)組進(jìn)行一次打包，然后多次進(jìn)行修改和發(fā)送。 b 數(shù)據(jù)打包 一個(gè)發(fā)送緩沖區(qū)中可以同時(shí)包含各種不同類型、不同長(zhǎng)度的數(shù)據(jù)。c 語言接口 對(duì)每種數(shù)據(jù)類型提供了一個(gè)打包函數(shù)如： i n t i n f 0 = p v m pk i n t ( i n t + n p ， i n tn i t e m ，i n ts tr i d e ) 用于打包整數(shù) i n t i n f o = p v m p k f l o a t ( n o a t + f p ， i n tn i t e m 。 i n ts t r i d e )，用于打包浮點(diǎn) 數(shù) i n t i n f o = p v m _ p k s t r ( c h a r c p ) ，用于打包字符串 c 消息發(fā)送 p v m 中一個(gè)任務(wù)可以將打好包的數(shù)據(jù)發(fā)送給一個(gè)指定的任務(wù)，也可以同時(shí)發(fā)送 給多個(gè)任務(wù)( 廣播) ，用于發(fā)送的函數(shù)有： i n t i n f o = p v m s e n d ( i n tt j d ， i d tm s g t a g ) ，將當(dāng)前活動(dòng)緩沖區(qū)中的數(shù)據(jù)發(fā)送給一個(gè)指定的任務(wù) i n t i n f o = p v m j n c 罄t ( i n t t d s ， i n tn t 船k ，i n tm s g t a g ) 同時(shí)將當(dāng)前活動(dòng)緩沖區(qū)中的數(shù)據(jù)廣播給多個(gè)任務(wù) 1 0 中南大學(xué)碩士學(xué)位論文 i n ti n f 0 = p v m p s e n d ( i n tt i d ，i n tm s 昏a g ，v o i d + ”p ，i n tc n t ，i n tt y p e ) 綜合打包函數(shù)和p v m s e n d ( ) 的功能，即打包和發(fā)送一次完成 ( 4 )消息接收分兩個(gè)步驟： a 消息接收 p v m 有三種數(shù)據(jù)接收方式：阻塞接收，非阻塞接收和限時(shí)接收，對(duì)應(yīng)的函數(shù) 分別為： i n t b u f i d = p v m r e c ( i n tt d i n tm s 甜a g ) ，阻塞接收 i n t b u f l d = p v m n r e c v ( i n tt i d ， i n tm s g t a g ) ，月 阻塞接收 i n t b u f i d = p v m t r e c v ( i n i d i n tm s g t a g ，s t r u c tt i m e e v a l + t m o u t ) ，限時(shí)接收 p v m f e c v ( ) 等待相應(yīng)的消息到達(dá)，將消息接收至接收緩沖區(qū)后才返回緩沖區(qū) 的標(biāo)識(shí)符：p v m n r e c v ( ) 并不等待，如果消息尚未到達(dá)，則返回0 ，如消息已經(jīng)到達(dá)， 則作用與p v m _ r e c v ( ) 相同：p v m j r e c v ( ) 用于限時(shí)接收，如果消息在給定時(shí)間內(nèi)到達(dá)， 則作用同p v m r e c v ( ) ，否則返回0 ，等待時(shí)間由結(jié)構(gòu)t m o u t 給出。 在上述函數(shù)中，t i d 和m s g t a g 參數(shù)都可用一l 作為通配符，分別代表任意任務(wù)和 任意標(biāo)簽的消息。 b 數(shù)據(jù)解包 數(shù)據(jù)解包和數(shù)據(jù)打包是相對(duì)應(yīng)的過程，解包過程的順序、數(shù)據(jù)類型及數(shù)據(jù)長(zhǎng)度 必須與發(fā)送時(shí)打包過程完全一致才能保證數(shù)據(jù)的正確性。解包函數(shù)與打包函數(shù)一一 對(duì)應(yīng)：如： i n t i n f o = p v m u p k i n t ( ；n t + n 艮 i n tn i t e m ，i n ts t r i d e ) i n t i n f b = p v m u p k f l o a t ( f l o a f p ， i n tn j t e m ，j n ts t r j d e ) i n t i n f o = p v m u p k s t r ( c h a r c p ) 若只檢查消息是否已經(jīng)到達(dá)或已到達(dá)的消息內(nèi)容而不接收它，可以使用以下函 數(shù)： i n t b u 矗d = p v m p r o b e ( i n tt i d ， j n tm s g t a g ) i n t i n f 0 = p v m b u f i n f 0 ( i n t b u f i d ， i n t 鈾”e s ， i n t m s 昏a 昏i n t + t i d ) 如果消息尚未到達(dá)，p v m p r o b e ( ) 返回0 ，否則返回該消息的消息緩沖區(qū)標(biāo)識(shí)符，但 并不接收消息用戶可以隨后調(diào)用p v m _ b u f i n f 0 ( ) 來獲得有關(guān)該消息的進(jìn)一步信息， 包括消息的長(zhǎng)度b y t e s 、消息標(biāo)簽m s g t a g 和消息來源t i d ， ( 5 ) p v m 任務(wù)完成后離開p v m ，這時(shí)需調(diào)用函數(shù)p v m - 一e x i t ( ) ： i n t i n f 0 = p v m e x i t ( v o i d ) 另外，p v m 接口庫中還提供了用戶在運(yùn)行過程中動(dòng)態(tài)加入刪除主機(jī)、查看虛擬 機(jī)的構(gòu)造、終止任務(wù)、查看主機(jī)和任務(wù)的狀態(tài)等函數(shù)。 中南大學(xué)碩士學(xué)位論文 2 5p v m 任務(wù)調(diào)度機(jī)制 如何指派任務(wù)到節(jié)點(diǎn)，p v m 內(nèi)部提供了三個(gè)層次上的控制“。一是完全由系 統(tǒng)自動(dòng)分配任務(wù)到節(jié)點(diǎn)上運(yùn)行，但p v m 實(shí)現(xiàn)并不考慮各節(jié)點(diǎn)的負(fù)載狀況。二是體 系結(jié)構(gòu)相關(guān)級(jí)，用戶可指派一任務(wù)在具有一相同體系結(jié)構(gòu)的機(jī)器上運(yùn)行。三是由用 戶指定任務(wù)在某一節(jié)點(diǎn)運(yùn)行，對(duì)于編譯時(shí)能夠確定任務(wù)間數(shù)據(jù)流圖的應(yīng)用，這種由 用戶指定的方法是非常有效的，并由此可獲得任務(wù)分配的初始狀態(tài)圖，為動(dòng)態(tài)負(fù)載 平衡算法提供初始值。 2 6p v md nw i n 3 2 【3 4 i p v m 需要一個(gè)多任務(wù)的操作系統(tǒng)平臺(tái)以便生成多個(gè)p v m 進(jìn)程，實(shí)現(xiàn)虛擬機(jī) 的功能。以往這個(gè)多任務(wù)的操作系統(tǒng)都是基于u n i x 的，后來由于w i n d o w s 9 5 和 n t 亦以3 2 位多任務(wù)操作系統(tǒng)出現(xiàn)，為p v m 在p c 機(jī)上的應(yīng)用提供了可能。9 4 年， p v m 開發(fā)者們推出一個(gè)p v mo nw i n 3 2 的版本，基于w i n d o w s 的p v m 與原先基于 u n i x 的版本大部分工作原理是一致的，只是在幾個(gè)方面有些區(qū)別。( 1 ) w i n d o w s 下的p v m 中處理機(jī)之間的消息傳遞使用w i n s o c k 進(jìn)行，不同的是w i n s o c k 不能 像標(biāo)準(zhǔn)u n i x 那樣當(dāng)作文件或流來處理。( 2 ) 在啟動(dòng)一個(gè)從d v m d 時(shí)有區(qū)別，w i n 3 2 中的p v m 需要一個(gè)專門的進(jìn)程來啟動(dòng)其它主機(jī)的p v m d 這個(gè)主機(jī)管理進(jìn)程為h o s t e r 進(jìn)程，而u n i x 下的p v m 中加入從p v m d 是由主p v m d 進(jìn)行一次f b r k 系統(tǒng)調(diào)用生成 一個(gè)與自己相同的p v m d ( p v m d 的影子進(jìn)程) ，由p v m d 完成加入節(jié)點(diǎn)機(jī)的工作。( 3 ) 加入另一個(gè)節(jié)點(diǎn)機(jī)的過程要求有r s h 與r s h d 參與。r s h 是一個(gè)遠(yuǎn)程命令，目的是引起 遠(yuǎn)程機(jī)上的程序運(yùn)行它是由調(diào)用系統(tǒng)函數(shù)r c m d ( ) 實(shí)現(xiàn)的。r s h 與r e x e c 的區(qū)別在于 前者的使用者必須為遠(yuǎn)程機(jī)的特許用戶主機(jī)為這個(gè)用戶提供一個(gè)保留連接的端口， 調(diào)用者不要提供登錄名和口令；r e x e c 需要調(diào)用者提供遠(yuǎn)程機(jī)上的登錄名和口令，供 遠(yuǎn)程機(jī)驗(yàn)證。u n i x 和n t 都提供了f 出與r “e c 命令，但w i n 9 5 不具備這個(gè)功能， 因此撕n d o w s 9 5 需要尋找另外的r s h 和r s h d 程序。 p v mo nw i n 3 2 的優(yōu)點(diǎn)在于：基于w i n d o w s 的p c 機(jī)在數(shù)量上遠(yuǎn)遠(yuǎn)超過基于u n i x 的各種機(jī)器。而且它可以與u n i xp v m 在虛擬機(jī)上并存。 1 2 主墮盔蘭塑：! 蘭堡壘苧 一 第三章任務(wù)調(diào)度策略 分布式系統(tǒng)( d j s t r b u t e ds y s t e n l 一d s ) 是由兩臺(tái)或兩臺(tái)以上、通過網(wǎng)絡(luò)( 或通訊電路) 連接起來的相互獨(dú)立而又相互合作的計(jì)算機(jī)( 又稱結(jié)點(diǎn)，h o s t ) 組成的一種計(jì)算機(jī)系統(tǒng)， 也稱為機(jī)群系統(tǒng)( c l u s t e ro f w o r k s t a t i o n s c o w ) ，它是并行分布計(jì)算領(lǐng)域近年來比較活 躍的研究領(lǐng)域。由于網(wǎng)絡(luò)技術(shù)的發(fā)展，特別是局域網(wǎng)中高速數(shù)據(jù)通訊網(wǎng)絡(luò)的出現(xiàn)，相 似的利用工作站越來越具有吸引力同時(shí)也出現(xiàn)了許多支持異種機(jī)網(wǎng)絡(luò)計(jì)算的軟件工 具環(huán)境，如m p i p v m ，e x p r e s s 等。c o w 與巨型機(jī)和m p p 系統(tǒng)相比，具有很高的 性能價(jià)格比，可擴(kuò)展性好，結(jié)構(gòu)靈活。為了提高并行分布計(jì)算的執(zhí)行效率。必須尋找 一個(gè)任務(wù)調(diào)度策略7 邯，”川】，將適當(dāng)?shù)娜蝿?wù)分配給適當(dāng)?shù)奶幚頇C(jī)，使得整個(gè)任務(wù)負(fù) 載的執(zhí)行時(shí)間最短。 3 1 調(diào)度策略的相關(guān)術(shù)語 任務(wù)粒度( t a s k sgr a n u l a r i t y ) 粒度是一個(gè)任務(wù)的： 作量或執(zhí)行時(shí)間。通常稱循環(huán)一級(jí)的并行為小粒度的并行， 子程序一級(jí)的并行為大粒度的并行。 負(fù)載( l o a d ) 和閥值( t h r e s h o l d ) 在負(fù)載平衡算法中的關(guān)鍵問題是如何確定負(fù)載。常用的負(fù)載尺度包括處理機(jī)利 用率、處理機(jī)隊(duì)列長(zhǎng)度豐進(jìn)程響應(yīng)時(shí)間等：閥值是用來表征處理器的任務(wù)處理能力 的。 有向無環(huán)圖( d i r e c t i o n a la c y c i i cg f a p h d