【畢業(yè)學(xué)位論文】（Word原稿）計(jì)算環(huán)境下的分布式作業(yè)任務(wù)調(diào)度算法研究與應(yīng)用-軟件工程

碩士學(xué)位論文 （專業(yè)學(xué)位） 姓 名： 學(xué) 號(hào)： 所在院系：軟件學(xué)院 職業(yè)類別：工程碩士 專業(yè)領(lǐng)域：軟件工程 指導(dǎo)教師： 副指導(dǎo)教師： 二一三年十二月 云計(jì)算環(huán)境下的分布式作業(yè)任務(wù)調(diào)度算法研究與應(yīng)用 A in 2010 基于 人力資源管理系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn) 陳世軍 同濟(jì)大學(xué) 2013 云計(jì)算環(huán)境下的分布式作業(yè)任務(wù)調(diào)度算法研究與應(yīng)用 同濟(jì)大學(xué) 學(xué)位論文版權(quán)使用授權(quán)書 本人完全了解同濟(jì)大學(xué)關(guān)于收集、保存、使用學(xué)位論文的規(guī)定，同意如下各項(xiàng)內(nèi)容：按照學(xué)校要求提交學(xué)位論文的印刷本和電子版本；學(xué)校有權(quán)保存學(xué)位論文的印刷本和電子版，并采用影印、縮印、掃描、數(shù)字化或其它手段保存論文；學(xué)校有權(quán)提供目錄檢索以及提供本學(xué)位論文全文或者部分的閱覽服務(wù)；學(xué)校有權(quán)按有關(guān)規(guī)定向國(guó)家有關(guān)部門或者機(jī)構(gòu)送交論文的復(fù)印件和電子版；在不以贏利為目的的前提下，學(xué)?？梢赃m當(dāng)復(fù)制論文的部分或全部?jī)?nèi)容用于學(xué)術(shù)活動(dòng)。 學(xué)位論文作者簽名： 年 月 日 同濟(jì)大學(xué)學(xué)位論文原創(chuàng)性聲明 本人鄭重聲明：所呈交的學(xué)位論文，是本人在導(dǎo)師指導(dǎo)下，進(jìn)行研究工作所取得的成果。除文中已經(jīng)注明引用的內(nèi)容外，本學(xué)位論文的研究成果不包含任何他人創(chuàng)作的、已公開發(fā)表或者沒(méi)有公開發(fā)表的作品的內(nèi)容。對(duì)本論文所涉及的研究工作做出貢獻(xiàn)的其他個(gè)人和集體，均已在文中以明確方式標(biāo)明。本學(xué)位論文原創(chuàng)性聲明的法律責(zé)任由本人承擔(dān)。 學(xué)位論文作者簽名： 年 月 日 同濟(jì)大學(xué) 碩士學(xué)位論文 摘要 I 摘要 云計(jì)算是目前國(guó)內(nèi)外商業(yè)和科研機(jī)構(gòu)研究的熱點(diǎn)之一，是網(wǎng)格計(jì)算、并行計(jì)算、分布式計(jì)算的發(fā)展，是一種新興的商業(yè)計(jì)算模式。它采用了成熟的虛擬化技術(shù)將數(shù)據(jù)中心的資源打包為互聯(lián)網(wǎng)上的用戶提供按需服務(wù)。作業(yè)調(diào)度與資源分配是云計(jì)算的兩個(gè)關(guān)鍵技術(shù)，云計(jì)算的商業(yè)性使其關(guān)注對(duì)用戶的服務(wù)質(zhì)量，其虛擬化技術(shù)使得資源分配和作業(yè)調(diào)度不同于以往的并行分布式計(jì)算。 本 文系統(tǒng)的、全面的研究了云計(jì)算技術(shù)，以社會(huì)學(xué)分配理論 關(guān)于分配性正義的伯格模型為理論基礎(chǔ)，提出了云環(huán)境下基于伯格模型的作業(yè)調(diào)度算法。該算法適應(yīng)云計(jì)算商業(yè)化和虛擬化的特性，區(qū)別于傳統(tǒng)的作業(yè)調(diào)度算法注重效率的特點(diǎn)，在云環(huán)境下的作業(yè)調(diào)度過(guò)程中建立起雙重公平性約束。第一重約束是在云環(huán)境下將用戶任務(wù)按照 好分類，依據(jù)人元模型理論給出了任務(wù)描述，按照任務(wù)的分類在其主元部分加入任務(wù)的一般期待來(lái)約束資源選擇過(guò)程的公平性，給出了加入一般期待的任務(wù)與資源的映射方法。第二重約束是在云環(huán)境中定義了資源分配的公平性評(píng)判函數(shù)，對(duì)資 源分配結(jié)果的公平性進(jìn)行評(píng)判，依據(jù)評(píng)判結(jié)果修正模型的參數(shù)，約束系統(tǒng)的公平性。對(duì)于具有多重 性的任務(wù)，本文應(yīng)用人元分析理論給出了處理任務(wù)的多重一般期待的方法。最后，擴(kuò)展了 現(xiàn)了本文提出的任務(wù)描述和基于伯格模型的作業(yè)調(diào)度算法，對(duì) 臺(tái)進(jìn)行了重編譯生成，并在擴(kuò)展后的 臺(tái)上實(shí)現(xiàn)了作業(yè)調(diào)度的仿真程序，對(duì)算法進(jìn)行了模擬驗(yàn)證和對(duì)比分析，實(shí)驗(yàn)顯示該算法能夠有效的執(zhí)行用戶任務(wù)并體現(xiàn)出較好的公平性。 此外，本文結(jié)合伯格模型的均衡論研究了云環(huán)境下負(fù)載均衡的控制模式 ，為云環(huán)境下資源的負(fù)載均衡策略研究提供了借鑒方案。 關(guān)鍵詞 ： 云計(jì)算 ， 作業(yè) 調(diào)度 ， 資源管理 ， 類 I is of at of is an of It a to to on of it of to In a of to of on to on in in is to oS to to in to of a to of of to is in a to of of to of on of oS a of of to in of II of 濟(jì)大學(xué) 碩士學(xué)位論文 目錄 錄 第 1 章 引言 . 1 題背景與意義 . 1 內(nèi)外發(fā)展現(xiàn)狀 . 1 課題的主要研究?jī)?nèi)容 . 3 課題的研究方法 . 4 文的組織結(jié)構(gòu) . 4 第 2 章 云計(jì)算相關(guān)技術(shù)簡(jiǎn)介 . 5 計(jì)算技術(shù)介紹 . 5 格計(jì)算及其調(diào)度 . 5 計(jì)算簡(jiǎn)介 . 7 計(jì)算體系結(jié)構(gòu) . 11 計(jì)算服務(wù)及應(yīng)用 . 12 布式技術(shù)概要 . 14 布式相關(guān)技術(shù)簡(jiǎn)介 . 14 程模型 . 16 平臺(tái) . 18 計(jì)算環(huán)境下調(diào)度算法技術(shù)介紹 . 19 章小結(jié) . 20 第 3 章 云計(jì)算環(huán)境下分布式任務(wù)調(diào)度算法 . 21 計(jì)算環(huán)境下分布式資源管理與作業(yè)調(diào)度 . 21 計(jì)算環(huán)境下虛擬機(jī)監(jiān)控代理 . 21 計(jì)算環(huán)境下 度策略 . 23 計(jì)算環(huán)境下分布式系統(tǒng)的 類 . 25 計(jì)算環(huán)境下伯格模型的作業(yè)調(diào)度 . 26 計(jì)算環(huán)境下 資源分配公平性判定約束 . 27 計(jì)算環(huán)境下資源選擇過(guò)程的一般期待約束 . 29 計(jì)算環(huán)境下分布式算法資源描述 . 29 計(jì)算環(huán)境下分布式作業(yè)任務(wù)描述 . 30 計(jì)算環(huán)境下分布式作業(yè)任務(wù)調(diào)度算法邏輯 . 33 章小結(jié) . 34 第 4 章 云環(huán)境下分布式任務(wù)調(diào)度伯格模型的負(fù)載均衡 . 35 計(jì)算環(huán)境下分布式任務(wù)調(diào)度模型的建立 . 35 計(jì)算環(huán)境下分布式任務(wù)調(diào)度均衡失效的應(yīng)激反應(yīng)分析 . 36 計(jì)算環(huán)境下分布式任務(wù)調(diào)度的均衡恢復(fù)策略 . 37 同濟(jì)大學(xué) 碩士學(xué)位論文 目錄 V 章小結(jié) . 38 第 5 章 云計(jì)算環(huán)境下分布式調(diào)度算法的實(shí)現(xiàn)及驗(yàn)證與 應(yīng)用 . 39 法的實(shí)現(xiàn) . 39 度算法實(shí)現(xiàn)的輔助仿真軟件 . 39 度算法實(shí)現(xiàn) . 40 法的驗(yàn)證 . 42 境配置 . 42 真流程 . 43 驗(yàn)結(jié)果及分析 . 44 法的應(yīng)用 . 46 第 6 章 總結(jié)與展望 . 47 結(jié) . 47 望 . 48 致謝 . 49 參考文獻(xiàn) . 50 個(gè)人簡(jiǎn)歷、在讀期間發(fā)表的學(xué)術(shù)論文與研究成 果 . 51 第 1章 引言 1 第 1 章 引言 題 背景與 意義 云計(jì)算 是近幾年發(fā)展起來(lái)的一種 新興的商業(yè) 計(jì)算模型， 它 采用將計(jì)算任務(wù)分布在由大量計(jì)算機(jī)搭建的云系統(tǒng)平臺(tái)上，使得任務(wù)能夠根據(jù)自身需求獲取相應(yīng)的資源，如 存等各種服務(wù)。同時(shí)，這些云平臺(tái)上的云資源可以 很方便的通過(guò)網(wǎng)絡(luò) 提供 給需要使用云計(jì)算的用戶。然而在云計(jì)算環(huán)境下，大量的任務(wù) 需要大量的系統(tǒng)資源，如何在有限的資源環(huán)境中，對(duì)用 戶提交的海量任務(wù)進(jìn)行分配資源以及有效的對(duì)資源進(jìn)行調(diào)度成為當(dāng)前云計(jì)算中所要解決的重要問(wèn)題之一。 1 另 一方面， 在云計(jì)算環(huán)境中，對(duì)用戶群體提交的海量任務(wù)進(jìn)行調(diào)度是云計(jì)算的關(guān)鍵所在，通常要將 N 個(gè)任務(wù)分配到 M 個(gè)工作單元中，如何將這 N 個(gè)任務(wù)合理的分配在 M 個(gè)工作單元，使得系統(tǒng)負(fù)載平衡成為一個(gè) 題，因此有效的解決云計(jì)算環(huán)境下分布式作業(yè)任務(wù)調(diào)度能夠影響云計(jì)算系統(tǒng)的性能。 2 目前，解決云計(jì)算環(huán)境中的任務(wù)調(diào)度問(wèn)題的主要方法有 務(wù)調(diào)度算法及其簡(jiǎn)單擴(kuò)展、計(jì)算能力調(diào)度算法以及公平調(diào)度算法等，針對(duì)調(diào)度算法的研究已經(jīng) 成為科研熱點(diǎn)。同時(shí)分布式任務(wù)調(diào)度也影響著云計(jì)算平臺(tái)的性能，也是云計(jì)算服務(wù)質(zhì)量 (關(guān)鍵問(wèn)題，值得研究。 通過(guò)對(duì)本課題的研究，能夠?qū)υ朴?jì)算中分布式作業(yè)任務(wù)調(diào)度有一個(gè)更好的理解，并在此基礎(chǔ)上，能夠?qū)υ朴?jì)算分布式作業(yè)任務(wù)調(diào)度算法進(jìn)行有效的改進(jìn)，提高云計(jì)算中資源利用率，從而達(dá)到工作單元負(fù)載平衡，最終使得云計(jì)算服務(wù)質(zhì)量(到有效提高。 本課題的研究能夠改善云計(jì)算環(huán)境中作業(yè)任務(wù)調(diào)度的負(fù)載平衡，提高云計(jì)算服務(wù)質(zhì)量，最終提高用戶使用的滿意度，進(jìn)而達(dá)到良好社會(huì)效應(yīng)。另外 一方面，本課題的研究通過(guò)優(yōu)化分布式任務(wù)調(diào)度，提高云計(jì)算集群的使用效率，最終為提供云計(jì)算服務(wù)的公司節(jié)省了服務(wù)成本，能取得良好的經(jīng)濟(jì)效益。 內(nèi)外發(fā)展現(xiàn)狀 目前，國(guó)內(nèi)外在云計(jì)算環(huán)境中針對(duì)分布式作業(yè)任務(wù)調(diào)度算法主要有以下幾個(gè)方面的研究。 (1) 傳統(tǒng)的作業(yè)調(diào)度算法。 在云計(jì)算環(huán)境中， 傳統(tǒng)的調(diào)度算法通常有 最小連接調(diào)度、 輪循調(diào)度、加權(quán)輪循調(diào)度、 源地址散列調(diào)度、目標(biāo)地址散列調(diào)度 等。 這同濟(jì)大學(xué) 碩士學(xué)位論文 云計(jì)算環(huán)境下的分布式作業(yè)任務(wù)調(diào)度算法研究與應(yīng)用 2 些算實(shí)現(xiàn)簡(jiǎn)單， 但是在實(shí)際的 云計(jì)算 調(diào)度應(yīng)用中性能表現(xiàn)不佳， 因此沒(méi)能得到廣泛的應(yīng)用 。 3 (2) 啟發(fā)式調(diào)度算法。 啟發(fā)式調(diào)度算法 是目前 應(yīng)用比較廣泛的尋找最優(yōu)解的算法， 將其引入云計(jì)算 環(huán)境下 分布式作業(yè)任務(wù)調(diào)度中，正好能夠 解決分布式 作業(yè)任務(wù) 的問(wèn)題，能夠有效的提高云計(jì)算環(huán)境下作業(yè)任務(wù)調(diào)度的性能。目前，針對(duì)云計(jì)算 環(huán)境 啟發(fā)式調(diào)度算法的主要 研究算法 有 蟻群算法、遺傳算法等。 啟發(fā)式算法在實(shí)際使用的過(guò)程中，能夠很好的自適應(yīng)系統(tǒng)，并能找到最優(yōu)解，但是它在尋求最優(yōu)解的過(guò)程中，求解過(guò)程非常繁雜，對(duì)系統(tǒng)性能要求較高，同時(shí)尋求最優(yōu)解的時(shí)間 可能較長(zhǎng)，從而影響系統(tǒng)的整體性能。 4 (4) 基于 作業(yè)調(diào)度算法。 采用 術(shù)進(jìn)行云計(jì)算環(huán)境下的作業(yè)任務(wù) 調(diào)度來(lái)源于人工智能，雖然人工智能早在 20 世紀(jì) 60 年代就被提出，但是 其真正發(fā)展卻在 20 世紀(jì) 90 年代 。 面向 技術(shù)能夠有效的描述并分析分布式系統(tǒng) ， 并且它能 在 云計(jì)算環(huán)境下作業(yè)任務(wù)調(diào)度 過(guò)程中智能學(xué)習(xí) ，因此也得到了廣泛的研究。 在基于 任務(wù)調(diào)度中，可以將云計(jì)算系統(tǒng)看成多層 統(tǒng)的幾乎，并將云計(jì)算環(huán)境中每一個(gè)資源節(jié)點(diǎn)封裝成一個(gè) 此，針對(duì)云計(jì)算 環(huán)境下作業(yè)任務(wù)調(diào)度算法的研究 可以 簡(jiǎn)化為在不同 間進(jìn)行計(jì)算任務(wù)分配，并根據(jù)實(shí)際情況隨時(shí)調(diào)整 算難度 。同時(shí)，在每個(gè) ， 也需要對(duì)子任務(wù)繼續(xù)進(jìn)行分配 ，爭(zhēng)取達(dá)到最優(yōu) 。 5 (5) 基于經(jīng)濟(jì)學(xué)模型的調(diào)度算法。 云計(jì)算環(huán)境中的作業(yè)任務(wù)調(diào)度算法 可以看成是計(jì)算任務(wù)與系統(tǒng)資源 之間的分配，這與經(jīng)濟(jì)學(xué)模型十分相似 ：云計(jì)算系統(tǒng)資源相當(dāng)于經(jīng)濟(jì)學(xué) 中 商品供應(yīng)商， 為云計(jì)算用戶提供計(jì)算資源； 云計(jì)算中 的 用戶相當(dāng)于經(jīng)濟(jì)學(xué)中 的商品消費(fèi)者， 需要為自己的 使用的資源支付 相應(yīng)的費(fèi)用。因此，可以在云計(jì)算 調(diào)度算法中引入經(jīng)濟(jì)學(xué)模型，在云計(jì)算資源與與計(jì)算用戶之間建立市場(chǎng)機(jī)制，利用價(jià)格杠桿來(lái)調(diào)節(jié)用戶需求和資源分配，從而對(duì)云計(jì)算系統(tǒng)進(jìn)行優(yōu)化并提高云計(jì)算效率 。 另外，與經(jīng)濟(jì)學(xué)模型調(diào) 度算法類似，利用資源與拍賣間類似的聯(lián)系，目前還有基于拍賣機(jī)制的作業(yè)調(diào)度算法模型。 6 (6) 其它 改進(jìn)的 調(diào)度算法。 除了以上介紹的調(diào)度 算法以外， 還有一些針對(duì)原算法基礎(chǔ)上進(jìn)行綜合和改進(jìn)的作業(yè)任務(wù)調(diào)度算法 ，如加入新人機(jī)制、 束、優(yōu)先級(jí)等不同的余數(shù)條件對(duì)算法進(jìn)行改進(jìn)。同時(shí)，也有針對(duì)原算法進(jìn)行 的 改進(jìn) ，最終提高云計(jì)算環(huán)境下作業(yè)任務(wù)調(diào)度的負(fù)載均衡。 另一方面，云計(jì)算作為目前最重要的新興技術(shù)，已經(jīng)引起了學(xué)術(shù)界和工業(yè)界的廣泛關(guān)注。在國(guó)外， 供了 程框架、 供了 、 經(jīng)開始出售自己的云計(jì)算服務(wù) 、 “藍(lán)云”提供端對(duì)端的云計(jì)算解決方案以及 出的云平臺(tái) 得到了廣泛的應(yīng) 第 1章 引言 3 用。 相對(duì)于 國(guó)外的技術(shù)，國(guó)內(nèi)也開始緊隨其后開發(fā)了自己的云計(jì)算平臺(tái)，國(guó)內(nèi) 百度云，阿里巴巴推出了阿里云技術(shù)， 360 也推出了自己的云盤技術(shù)以及國(guó)內(nèi)其它的 商都對(duì)云計(jì)算展開了相應(yīng)的研究。 針對(duì)目前各種云環(huán)境下作業(yè)任務(wù)調(diào)度算法來(lái)說(shuō)，目前調(diào)度算法趨向于使用多種算法組合使用以及針對(duì)啟發(fā)式算法進(jìn)行的各種改進(jìn)，從而達(dá)到更 好的調(diào)度效果，最終使得云計(jì)算環(huán)境中的各項(xiàng)單元負(fù)載平衡。 課題的主要研究?jī)?nèi)容 1. 云計(jì)算的發(fā)展及其面臨的問(wèn)題 介紹云計(jì)算的發(fā)展歷程、云存儲(chǔ)發(fā)展，云計(jì)算技術(shù)，云計(jì)算的實(shí)現(xiàn)，云計(jì)算帶來(lái)的好處以及目前云計(jì)算所面臨的各種問(wèn)題。 2. 研究 通過(guò)對(duì)當(dāng)前的云計(jì)算核心框架平臺(tái) 行研究，并將為主要實(shí)驗(yàn)技術(shù)，構(gòu)建云平臺(tái)。 為當(dāng)前最主要的當(dāng)前云計(jì)算的核心技術(shù)，對(duì)其調(diào)度算法進(jìn)行研究，能夠更加深入底層算法，從而對(duì)其進(jìn)行改進(jìn) 達(dá)到更好的調(diào)度目的。 為云存儲(chǔ)的核心平臺(tái)，它同時(shí)也利用 行底層調(diào)度，利用 為底層文件系統(tǒng)，對(duì)其進(jìn)行研究，能夠有效掌握當(dāng)前云計(jì)算的主流技術(shù)。 3. 分布式作業(yè)任務(wù)規(guī)劃調(diào)度算法研究 目前針對(duì)云計(jì)算分布式任務(wù)任務(wù)調(diào)度算法的研究有很多，只有對(duì)這些作業(yè)調(diào)度算法進(jìn)行深入的研究和了解，才能更好的對(duì)其進(jìn)行改進(jìn)，從而提高云計(jì)算環(huán)境下的作業(yè)調(diào)度效果。 同時(shí)，這些主流算法中或多或少存在著一些問(wèn)題，只有對(duì)這些問(wèn)題進(jìn)行進(jìn)行深入研究，才能對(duì)其不足之處進(jìn)行改進(jìn)，并提出更好作業(yè)調(diào)度規(guī)劃，最終提高云計(jì) 算服務(wù)的效率。 4. 性能測(cè)試及分析 在當(dāng)前環(huán)境下，搭建相應(yīng)的實(shí)驗(yàn)集群，對(duì)當(dāng)前提出的算法進(jìn)行測(cè)試，并進(jìn)行算法比較和分析。 5. 關(guān)鍵技術(shù) 在云計(jì)算中，關(guān)鍵技術(shù)主要包括作業(yè)調(diào)度算法、 理技術(shù)以及術(shù)等。 同濟(jì)大學(xué) 碩士學(xué)位論文 云計(jì)算環(huán)境下的分布式作業(yè)任務(wù)調(diào)度算法研究與應(yīng)用 4 課題的研究方法 本課題采取的研究方法是，對(duì)當(dāng)前的主流調(diào)度算法進(jìn)行研究，采取啟發(fā)式調(diào)度算法實(shí)現(xiàn)云計(jì)算環(huán)境下的分布式作業(yè)任務(wù)調(diào)度，從而提高云計(jì)算服務(wù)質(zhì)量，達(dá)到云計(jì)算中資源的調(diào)度平衡，最終達(dá)到更好的效果。 本課題的技術(shù)路線是，應(yīng)用當(dāng)前已較為成熟的 程框架，結(jié) 合存儲(chǔ)模式，在啟發(fā)式調(diào)度算法的基礎(chǔ)上，對(duì)算法進(jìn)行改進(jìn)，從而實(shí)現(xiàn)分布式作業(yè)任務(wù)調(diào)度。 本課題的實(shí)施方案是，在已搭建平臺(tái)的基礎(chǔ)上，對(duì)分布式任務(wù)作業(yè)調(diào)度算法進(jìn)行運(yùn)行測(cè)試，并對(duì)結(jié)果進(jìn)行比較和分析，以得到更好的實(shí)驗(yàn)驗(yàn)證目的。 對(duì)本課題來(lái)說(shuō)，雖然在云計(jì)算環(huán)境下分布式作業(yè)任務(wù)調(diào)度是一個(gè)難題，但是是目前針對(duì)云計(jì)算中的各種調(diào)度算法研究也非常的多，而且云計(jì)算的各種技術(shù)手段也日益成熟，因此只要能夠合理對(duì)問(wèn)題進(jìn)行分析，對(duì)調(diào)度算法進(jìn)行合理的改進(jìn)，最后一定可以達(dá)到預(yù)期的目標(biāo)。 文的組織結(jié)構(gòu) 本文共分為六個(gè)章節(jié)： 第一章，引言。 介紹了課題的背景與意義，國(guó)內(nèi)外現(xiàn)狀以及本課題的研究?jī)?nèi)容和研究方法。 第二章， 云計(jì)算 相關(guān)技術(shù)介紹。 介紹了云計(jì)算相關(guān)技術(shù)、分布式技術(shù)以及云計(jì)算環(huán)境下的調(diào)度算法。 第三章， 云計(jì)算環(huán)境下任務(wù)調(diào)度 算法研究 。 介紹了云計(jì)算環(huán)境下的作業(yè)任務(wù)調(diào)度算法以及算法的邏輯結(jié)構(gòu) 第四章， 云計(jì)算環(huán)境下 分布式任務(wù)調(diào)度 負(fù)載均衡研究 。 介紹了云計(jì)算環(huán)境下的分布式任務(wù)調(diào)度模型經(jīng)歷以及負(fù)載均衡策略。 第五章， 作業(yè)任務(wù)調(diào)度與結(jié)果分析 。 介紹了算法實(shí)現(xiàn)、算法驗(yàn)證以及算法的應(yīng)用。 第六章，總結(jié)與展望。 對(duì)本文進(jìn)行總結(jié)，并對(duì)今后的工作進(jìn)行展望。 第 2 章 云計(jì)算相關(guān)技術(shù) 簡(jiǎn)介 5 第 2 章 云計(jì)算相關(guān)技術(shù) 簡(jiǎn)介 云計(jì)算作為當(dāng)前 科研研究的熱點(diǎn)， 引起了很多科研單位的關(guān)注 ，并取得了很大的進(jìn)展 。 同時(shí)， 它作為一項(xiàng)新興的技術(shù)，也吸引了 各大 商 的注意，他們針對(duì)云計(jì)算 研究投入了大量的投資，并開始推廣自己的云計(jì)算 產(chǎn)品 。 云計(jì)算研究的關(guān)鍵是 針對(duì)云計(jì)算環(huán)境下 作業(yè)任務(wù) 調(diào)度算法 的 研究， 只有 了解云計(jì)算 的相關(guān)技術(shù)， 才能理解云計(jì)算的工作流程， 并對(duì)其調(diào)度算法進(jìn)行規(guī)劃研究 。 本章 將 介紹云計(jì)算 的 相關(guān)技術(shù)，并做一個(gè)系統(tǒng)的闡述 。 計(jì)算技術(shù)介紹 格計(jì)算 及其調(diào)度 云計(jì)算是在網(wǎng)格計(jì)算的基礎(chǔ)上發(fā)展起來(lái) 的，所以在介紹云計(jì)算的同時(shí)，有必要先了解一下網(wǎng)格計(jì)算的相關(guān)技術(shù) 。 網(wǎng)格計(jì)算 是 分布式計(jì)算 的一種發(fā)展 ， 它 依據(jù)并行計(jì)算原理， 將 非常復(fù)雜的計(jì)算 任務(wù)進(jìn)行分解， 并將分解的 子任務(wù)分配 給許多計(jì)算機(jī)進(jìn)行處理， 最終將處理后的結(jié)構(gòu)進(jìn)行綜合，從而得到最終結(jié)果 ， 其原理圖如下圖 示。 計(jì) 算 任 務(wù)節(jié) 點(diǎn) 一總 節(jié) 點(diǎn) 節(jié) 點(diǎn) 二任 務(wù) 一任 務(wù) 二任 務(wù) 三節(jié) 點(diǎn) 三任 務(wù)計(jì) 算 結(jié) 果圖 格計(jì)算原理圖 從上圖中，可以看出， 網(wǎng)格計(jì)算 具有 注重計(jì)算任務(wù)、任務(wù)間的交互相對(duì)較少以及計(jì)算流程比較簡(jiǎn)單 的特點(diǎn)。 另一方面 ， 它對(duì)網(wǎng)絡(luò)、內(nèi)存空間和 硬盤 需求不大，同濟(jì)大學(xué) 碩士學(xué)位論文 云計(jì)算環(huán)境下的分布式作業(yè)任務(wù)調(diào)度算法研究與應(yīng)用 6 它只消耗 源。 因此 ，近年來(lái)，網(wǎng)格計(jì)算通常 借助于世界各地閑置的計(jì)算機(jī)，通過(guò) 取強(qiáng)大的計(jì)算能力 ，完成計(jì)算量龐大的項(xiàng)目。如分析太空的 電訊號(hào)、探索外星生命、尋找黑洞、 發(fā)現(xiàn)有效抵抗艾滋病毒的藥物以及 尋找 超過(guò) 1000 萬(wàn)位的 梅森質(zhì)素 等 。 7 網(wǎng)格計(jì)算的 發(fā)展是伴隨著個(gè)人電腦的普及， 使得越來(lái)越多人擁有了自己電腦，同時(shí)也 使得 越來(lái)越多的電腦處于閑置狀態(tài)。 另一方面，現(xiàn)在硬件的發(fā)展速度遠(yuǎn)遠(yuǎn)大于軟件的發(fā)展速度，因此個(gè)人電腦在開機(jī)狀態(tài)， 資源也沒(méi)能完全利用。如果將這些網(wǎng)絡(luò)上閑置的 源 進(jìn)行 整合 ，那么 肯定會(huì)成為相當(dāng) 強(qiáng)大的計(jì)算 能力 。網(wǎng)格計(jì)算 正好可以利用這些閑置的個(gè)人計(jì)算資源，將計(jì)算量很大的任務(wù)合理的分配給網(wǎng)絡(luò)上的計(jì)算機(jī)進(jìn)行處理， 同時(shí)， 將這些處理 完后的結(jié)果進(jìn)行綜合歸納即可得到最終結(jié)果。 雖然 這種計(jì)算方式看起來(lái)難度有點(diǎn)大 ，但是 隨著參與的計(jì)算機(jī)越來(lái)越多， 網(wǎng)格 計(jì)算 的計(jì)算 速度 也會(huì)變得非常 迅速。如上圖的 示，任務(wù)通過(guò)總結(jié)點(diǎn)進(jìn)行分配，最終分配到每個(gè)節(jié)點(diǎn)的任務(wù)量就很少， 因此計(jì)算量也就很容易實(shí)現(xiàn)了。 另外一方面， 為了讓更多的計(jì)算機(jī)參與到計(jì)算中來(lái)，可以采取 相應(yīng) 的 激勵(lì) 制度 ，如最近非常流行的虛擬貨幣 質(zhì)數(shù)幣 (就是利用 閑置的 源進(jìn)行“挖礦”，并對(duì)每個(gè)計(jì)算機(jī)節(jié)點(diǎn)提交的任務(wù)量進(jìn)行 統(tǒng)計(jì)，當(dāng)質(zhì)數(shù)計(jì)算出來(lái)時(shí)會(huì)分配相應(yīng)的質(zhì)數(shù)幣作為獎(jiǎng)勵(lì) ，提交任務(wù)量越高的計(jì)算機(jī)獲得的質(zhì)數(shù)幣也就越多 。同時(shí)， 獲得的質(zhì)數(shù)幣還能在網(wǎng)上用于買賣， 利用這種激勵(lì)方式 相當(dāng)于 “購(gòu)買” 了用戶的 源 ，進(jìn)而參與的人越來(lái)越多 。 與云計(jì)算類似，網(wǎng)格計(jì)算也存在著其作業(yè)任務(wù)調(diào)度， 網(wǎng)格計(jì)算任務(wù)調(diào)度是如何在總計(jì)算時(shí)間最小的 情況下，將任務(wù)分解成 n 個(gè)相互獨(dú)立的計(jì)算任務(wù)， 并 把 這n 個(gè)任務(wù)分配給 m 個(gè)獨(dú)立的計(jì)算單元，使得資源得到充分利用。 網(wǎng)格計(jì)算任務(wù)調(diào)度的目的是使 整個(gè)系統(tǒng)任務(wù)達(dá)到最優(yōu)調(diào)度，同時(shí) 提高整個(gè)系統(tǒng)的吞吐量，最終實(shí)現(xiàn)的主要目標(biāo)是服務(wù)質(zhì)量 (負(fù)載均衡、最優(yōu)跨度、經(jīng)濟(jì)援助。 (1) 服務(wù)質(zhì)量 網(wǎng)格計(jì)算通過(guò) 映用戶對(duì)系統(tǒng)資源的需求，并依此來(lái)提供計(jì)算和存儲(chǔ)服務(wù)。 在網(wǎng)格系統(tǒng)進(jìn)行任務(wù)管理調(diào)度時(shí)，一定要保證網(wǎng)站計(jì)算系統(tǒng)的服務(wù)質(zhì)量 ( 8 (2) 負(fù)載均衡。 在網(wǎng)格計(jì)算中 ，網(wǎng)格系統(tǒng)的負(fù)載均衡直接影響整個(gè)系統(tǒng) 中 資源的使用率，因此在對(duì)網(wǎng)格計(jì)算作業(yè)任務(wù)進(jìn)行調(diào)度時(shí)，需要 考慮系統(tǒng)負(fù)載均衡。同時(shí)，負(fù)載均衡也是 影響著 分布式計(jì)算和并行計(jì)算 性能 的一個(gè)關(guān)鍵因素。 9 (3) 最優(yōu)跨度 。 跨度通常指 的是調(diào)度的長(zhǎng)度，通俗的說(shuō)，它是指的從任務(wù)從開始到最后所有任務(wù)結(jié)束所用的時(shí)間 。 因此對(duì)網(wǎng)格計(jì)算來(lái)說(shuō)，達(dá)到 最優(yōu)跨度 是網(wǎng)格系統(tǒng)最常見也是最主要的目標(biāo)。 10 第 2 章 云計(jì)算相關(guān)技術(shù) 簡(jiǎn)介 7 (4) 經(jīng)濟(jì)原則。 由于網(wǎng)格系統(tǒng)地理分布廣泛，而資源 分布也不均衡，針對(duì)這些資源的使用的費(fèi)用也不盡相同，因此在對(duì)網(wǎng)格計(jì)算進(jìn)行作業(yè)任務(wù)調(diào)度時(shí)，也需在考慮前面服務(wù)質(zhì)量、負(fù)載均衡和最優(yōu)跨度的基礎(chǔ)上考慮 到計(jì)算任務(wù)的花費(fèi)，這樣才能使得網(wǎng)格計(jì)算能夠可持續(xù)的發(fā)展下去 。 11 在網(wǎng)格計(jì)算的作業(yè)任務(wù)調(diào)度中，通?？紤]比較多的是負(fù)載均衡 ，它是網(wǎng)格計(jì)算中一個(gè)比較關(guān)鍵的問(wèn)題。 負(fù)載均衡的 目的是使得計(jì)算任務(wù)合理的分配到網(wǎng)格系統(tǒng)中的各個(gè)節(jié)點(diǎn)，從而提高 整體資源的利用率和吞吐量。 通常描述負(fù)載均衡 的方法有： 搶先與非搶先、 實(shí)時(shí)與非實(shí)時(shí)和靜態(tài)與動(dòng)態(tài)三個(gè)角度 (1) 搶先與非搶先 。 在網(wǎng)格計(jì)算中，通常對(duì)一個(gè)已經(jīng)分配的任務(wù)進(jìn)行再度分配，從而達(dá)到負(fù)載均衡的目的，叫搶先；而 對(duì) 已經(jīng)分配好的任務(wù)不再進(jìn)行調(diào)度分配，叫非搶先。搶先的方式能夠?qū)θ蝿?wù)再調(diào)度分配，可以更加合理的對(duì)資源進(jìn)行利用，然而 它也增加了系統(tǒng)的復(fù)雜性和調(diào)度的難度。 12 (2) 實(shí)時(shí)與非實(shí)時(shí)。 在網(wǎng)格計(jì)算中，作業(yè)任務(wù)調(diào)度的目的是使得任務(wù)在規(guī)定的時(shí)間內(nèi)完成，負(fù) 載均衡的目的是為了完成規(guī)定時(shí)間內(nèi)的任務(wù)，這種方式為實(shí)時(shí)調(diào)度。 常見的實(shí)時(shí)系統(tǒng)中負(fù)載均衡算法有： 時(shí)間間隔受限調(diào)度、動(dòng)態(tài)基于優(yōu)先級(jí)的調(diào)度、靜態(tài)基于優(yōu)先級(jí)的調(diào)度以及基于時(shí)間的調(diào)度等。 而非實(shí)時(shí)系統(tǒng)主要目的是 利用負(fù)載均衡 提高系統(tǒng)的性能 ，以負(fù)載均衡作為衡量系統(tǒng) 性能 的主要指標(biāo)。 13 (3) 靜態(tài)與動(dòng)態(tài)。 在網(wǎng)格計(jì)算中，負(fù)載均衡的靜態(tài)與動(dòng)態(tài)的區(qū)分是根據(jù)調(diào)度算法是試用的靜態(tài)算法還是動(dòng)態(tài)算來(lái)來(lái)劃分的，這是根據(jù)作業(yè)任務(wù)調(diào)度決策的時(shí)機(jī)來(lái)劃分的。 所謂靜態(tài)算法，是依據(jù)網(wǎng)格系統(tǒng)的基本信息情況，提前分配任務(wù)然后開始運(yùn)行系統(tǒng)，它 可以 分為求最 優(yōu)解和次優(yōu)解的問(wèn)題。 而動(dòng)態(tài)算法則是在系統(tǒng)運(yùn)行后，實(shí)時(shí)根據(jù)系統(tǒng)現(xiàn)狀，對(duì)系統(tǒng)進(jìn)行調(diào)度，合理的分配負(fù)載信息。 動(dòng)態(tài)算法雖然能夠根據(jù)當(dāng)前情況進(jìn)行決策，但是增加了系統(tǒng)的開銷，它可以分為 分布式調(diào)度和集中式調(diào)度兩種。 14 綜上所述，對(duì)網(wǎng)格計(jì)算下的負(fù)載均衡需要從 以下三方面考慮：一是負(fù)載評(píng)價(jià)，即對(duì)系統(tǒng)中負(fù)載的評(píng)價(jià)和系統(tǒng)中所有節(jié)點(diǎn)的評(píng)價(jià)；二是調(diào)度算法，即網(wǎng)格計(jì)算必須根據(jù)當(dāng)前需求選擇合適的算法；三是二次調(diào)度，即當(dāng)系統(tǒng)中負(fù)載均衡 不穩(wěn)定或失效時(shí) ，需要對(duì)任務(wù)進(jìn)行重新分配達(dá)到新的負(fù)載平衡。 計(jì)算簡(jiǎn)介 從上文中，我們對(duì)網(wǎng)格 計(jì)算 有了一定的了解，云計(jì)算是在網(wǎng)格計(jì)算的基礎(chǔ)上發(fā)展起來(lái)的， 它與網(wǎng)格計(jì)算有著密不可分的關(guān)系 ，特別是在云計(jì)算的調(diào)度問(wèn)題上，也同樣面臨著和網(wǎng)格計(jì)算類似的問(wèn)題。因此對(duì)網(wǎng)格計(jì)算的了解有利于我們加深對(duì)同濟(jì)大學(xué) 碩士學(xué)位論文 云計(jì)算環(huán)境下的分布式作業(yè)任務(wù)調(diào)度算法研究與應(yīng)用 8 云計(jì)算的了解。 云計(jì)算的發(fā)展，離不開大數(shù)據(jù)的發(fā)展。據(jù)不完全統(tǒng)計(jì)，在 一天產(chǎn)生的數(shù)據(jù)需要 張 儲(chǔ)，全球一天發(fā)出近 3000 億封 時(shí)數(shù)據(jù)等級(jí)已經(jīng)從現(xiàn)在的 024G)升級(jí)到 024 024024 際數(shù) 據(jù)公司 )統(tǒng)計(jì)表明： 2010 年全球產(chǎn)生 據(jù)、2011 年全球產(chǎn)生 據(jù)。而全球所有書籍、印刷品的全部數(shù)據(jù)量也才 200以要對(duì)這么龐大的數(shù)據(jù)量進(jìn)行分析，普通的計(jì)算機(jī)是無(wú)法勝任的，因此云計(jì)算的技術(shù)才伴隨著云時(shí)代的來(lái)臨而發(fā)展。 通常來(lái)說(shuō)，我們把網(wǎng)絡(luò)稱作為“云 ” ，因此云計(jì)算 就是利用 因特網(wǎng)中的各種可被利用的 計(jì)算 系統(tǒng)資源 ，以第三方擁有的資源提供用戶所需求的計(jì)算服務(wù)，這就是云計(jì)算的基本定義。 從技術(shù)上來(lái)說(shuō)，云計(jì)算是并行計(jì)算、分布式計(jì)算和網(wǎng)格計(jì)算的一種發(fā)展， 它 是一種新的計(jì)算模式，它通過(guò) 利用 云計(jì)算數(shù)據(jù) 中心的 資源 (數(shù)據(jù)、應(yīng)用、 源 )作為服務(wù) 提供給用戶使用。 同時(shí)，云計(jì)算也是 一種管理 框架，它通過(guò)把互聯(lián)網(wǎng)上高度 自治的虛擬化資源統(tǒng)一起來(lái)，組成一個(gè)計(jì)算能力 強(qiáng)大的資源池，并以此來(lái)對(duì)用戶提供服務(wù)。 那么云計(jì)算的核心技術(shù)是什么？ 云計(jì)算是由網(wǎng)格計(jì)算 (并行計(jì)算 (分布式計(jì)算 (基礎(chǔ)上發(fā)展而來(lái)的，也可以說(shuō)它是這些計(jì)算的 商業(yè)實(shí)現(xiàn)模式 。 云計(jì)算是通過(guò) 將計(jì)算 任務(wù)分配給不同地區(qū)部署的 分布式計(jì)算 機(jī)，使得 用戶使用這些計(jì)算機(jī)就像在本地使用一樣。 因此 云計(jì)算的核心技術(shù)也由這幾種關(guān)鍵性技術(shù)組成，示。 云 計(jì) 算C l o u d C o m p u t i n 算 服 務(wù)I a a S 、 P a a S 、 S a a 計(jì) 算G r i d C o m p u t i n g / S O 化V i r t u a l i z a t i o 計(jì) 算C l u s t e r C o m p u t i n 計(jì) 算P a r t i t i o n C o m p u t i n 計(jì)算核心服務(wù) 由上圖 ，我們可以看出 云計(jì)算 提供不同層面的技術(shù) 和服務(wù)，具體來(lái)說(shuō)，第 2 章 云計(jì)算相關(guān)技術(shù) 簡(jiǎn)介 9 有以下三種表現(xiàn)形式： 基礎(chǔ)即服務(wù) (as a 平臺(tái)即服務(wù)(as a 及 軟件即服務(wù) (as a (1) 基礎(chǔ)即服務(wù) ( 這種 云計(jì)算 服務(wù) 模式 即為用戶通過(guò)使用云計(jì)算服務(wù)商提供的各種 計(jì)算機(jī)基礎(chǔ)設(shè)施從而獲取相應(yīng)的服務(wù)。 典型的應(yīng)用如 存儲(chǔ)等。 15 (2) 平臺(tái)即服務(wù) ( 這種云計(jì)算服務(wù)模式 指的 是 云 計(jì)算 服務(wù)商 通過(guò) 把相應(yīng)的軟件開發(fā)平臺(tái)或者服務(wù)器平臺(tái)作為 服務(wù)提供給用戶。 典型的應(yīng)用如萬(wàn)網(wǎng)的云服務(wù)器。 16 (3) 軟件即服務(wù) (這種云計(jì)算服務(wù)模式 指的是 用戶無(wú)需購(gòu)買昂貴的軟件，僅需要支付相對(duì)低廉的費(fèi)用，即可獲得云計(jì)算服務(wù)商提供的軟件服務(wù) 。 這種服務(wù)的優(yōu)勢(shì)在于： 用戶利用 可使用軟件， 而將軟件的管理 、 維護(hù) 以及安全 交給云計(jì)算服務(wù)商，從而 提高了工作效率。典型的應(yīng)用如 在線 用程序 。 17 雖然云計(jì)算分成了 三種服務(wù)形式，但是在具體應(yīng)用上，這三種服務(wù)是相輔相成，云服務(wù)商通過(guò)提供基礎(chǔ)服務(wù)的同時(shí)，才能為用戶提供開發(fā)平臺(tái)和相應(yīng)的軟件 服務(wù) ； 平臺(tái)服務(wù) 建立在計(jì)算機(jī)基礎(chǔ)服務(wù)上，同時(shí)它也為軟件服務(wù)提供相應(yīng)的平臺(tái) ； 軟件服務(wù)也建立在平臺(tái)服務(wù)和基礎(chǔ)服務(wù)的基礎(chǔ)上，沒(méi)有平臺(tái)和計(jì)算機(jī)基礎(chǔ) 設(shè)施 ，軟件服務(wù)也沒(méi)辦法實(shí)現(xiàn)。 它們的關(guān)系如下圖 示。 軟 件 即 服 務(wù)( S a a S )平 臺(tái) 即 服 務(wù)( P a a S )基 礎(chǔ) 即 服 務(wù)( I a a S )計(jì)算服務(wù)類型 同時(shí)，在云計(jì)算 系統(tǒng) 內(nèi)部，虛擬化技術(shù)是云計(jì)算的關(guān)鍵 ，本文研究的云計(jì)算環(huán)境下分布式作業(yè)任務(wù)調(diào)度算法研究與應(yīng)用 也是在虛擬化基礎(chǔ)上實(shí)現(xiàn)的 ，而虛擬化部?jī)H僅反應(yīng)在云計(jì)算服務(wù)器虛擬化上，它還體現(xiàn)在存儲(chǔ)和網(wǎng)絡(luò)虛擬化中。 其虛擬化關(guān)系圖如下圖 示。 在圖中 ， 云計(jì)算系統(tǒng)虛擬化針對(duì)服務(wù)器虛擬化