引言
雲計算具有海量計算資源、可彈性擴充、運維成本低等優勢，這些巨大優勢使得雲計算被廣泛應用于越來越多的大資料應用當中。
大資料應用需要快速地處理海量資料，而MapReduce可以并行地處理TB級别以上的大規模海量資料，是雲計算大規模資料處理技術發展曆史上的奠基石。
而選擇合适的資源排程算法進行合理有效的資源配置設定是MapReduce實作并行計算的關鍵，是以，以MapReduce為核心研究雲計算資源排程的相關工作顯得尤為重要。
然而，與傳統的叢集和網格計算不同，雲計算不僅在硬體上呈現多樣性，而且使用者執行不同任務對CPU (Central Processing Unit)、記憶體(Memory)及輸入/輸出等計算資源的需求方面也呈現高度的異構性和動态性。
在這樣多資源的異構雲計算環境下，全球資料量暴增，伴随着能耗也随之暴增，如何公平有效地配置設定資源并降低能源的浪費已成為雲計算資源排程研究的關鍵問題。
本文主要圍繞如何準确地描述資源的特性，捕捉使用者的資源偏好、同時兼顧提高資源使用率、設計合理的資源排程政策展開研究。
本章首先介紹了本論文的研究背景及意義，重點叙述了雲計算核心技術的經典排程算法的特點；然後對資源排程的國内外研究現狀進行了分析，總結歸納了雲計算環境下主流的幾種不同的資源排程方法，最後給出了本文的貢獻和結構安排。
1.2課題研究背景及意義
2003年MapReduce由一篇名為《MapReduce: Simplified Data Processing on Large Clusters》的論文首次提出，它是大資料時代的一次标志性革命。MapReduce作為Google核心技術之一，它采用分散處理-集中彙總的思想，是可以快速地處理海量資料的一種通用并行程式設計模型。
MapReduce将待處理的海量資料分成很多個map任務和reduce任務。其中，map任務被分布在整個叢集網絡的各個節點上來運作，負責處理一部分資料；reduce任務則負責彙總所有節點送出的中間結果，并經過歸納處理，輸出最終結果。
MapReduce采用主/從結構，以Hadoop系統為例作業跟蹤器Job Tracker與任務排程器Job Tracker的通信是雙向的：Job Tracker接收到使用者的作業請求後會指令Task Scheduler對送出的作業先進行初始化，然後再将待執行作業加入到資源配置設定的等待隊列。
負責接收用戶端使用者（Client）送出的作業請求。TaskTracker定期地以Heartbeat方式向JobTracker彙報作業資訊，并同時輸出本節點空閑資源的使用情況和作業的執行狀态。
當Task Tracker有空閑資源時，Job Tracker則在作業隊列中選擇合适的排程政策配置設定資源給Task Tracker。
基本思想是作業按照送出的先後順序，遵循先進先出的原則，然後根據優先級（如系統可以根據作業送出的資源需求情況确定靜态優先級或根據就緒作業等待高低按時間先後來選擇被執行的作業。
如若先送出的作業需要占用大量的資源，處理占用的時間較多，那麼占用資源少、處理時間較短的其他作業就可能需要等待很長時間。
正是因為實際應用中使用者作業對資源需求差異性的存在，使用者的體驗和任務的執行效率會是以受到影響。
FIFO排程算法的弊端是忽略了不同作業存在需求差異，易造成雲計算系統資源使用率不高，導緻系統性能下降。
Capacity Scheduling：是一種多隊列資源排程算法(由雅虎公司提出)，Capacity Scheduling排程算法為每個隊列單獨配置設定一定比例的資源，每個隊列内部采用FIFO進行資源排程。
Capacity Scheduling 算法具有靈活性，一旦系統中有剩餘資源出現，系統會暫時回收剩餘資源，并把它實時地配置設定給有需要的隊列使用。
而當原剩餘資源所在隊列有新的任務請求時，“借用”的資源會在它任務全部執行完後馬上把“借用”的資源但随着分布式系統叢集規模的不斷擴大和使用者任務對資源需求的差異性。
譬如，有的任務是CPU-密集型需要大量的CPU，而有的任務是Memory-密集型的，則需要大量的記憶體資源。
這些問題導緻傳統的MapRecuce并行程式設計模式無法提供良好的解決方案，這是因為傳統的MapReduce提供的資源排程方案中，CPU、記憶體、網絡帶寬等資源是被切分成等量的若幹份。
對應的每一份資源是采用固定的slot，即槽位來表示的。其主要存在的問題有：1）當MapReduce任務非常多時，所有資源管理和任務排程工作集中在Job Tracker作業跟蹤器完成，存在單點故障。
- 資源被劃分成若幹份固定等量的slot槽位，無法真實準确地反映CPU或記憶體的占用情況，任務得不到有效的平衡，容易導緻叢集資源使用率不高、造成資源的浪費。
新管理架構改進了資源排程管理架構，将JobTracker的資源管理和作業排程這兩個主要子產品。隔離成了兩個互相獨立的子產品。
通過将JobTracker拆分，與傳統MapReduce相比，Hadoop Yarn降低了任務增加時對主節點的壓力，能夠運作更多的作業。
由于資料量、能耗暴增，公平有效配置設定資源成為資源排程的關鍵問題，本論文圍繞MapReduce的Fair Scheduling算法中的DRF政策展開研究基于公平與效率的多資源排程優化問題。
1.3.1 傳統資源排程優化分類
近年來，物聯網、雲計算、大資料、深度學習及量子通信等新技術已成為科研學者們研究的熱點MapReduce是雲計算實作并行計算的核心技術支撐，MapReduce資源排程優化的研究具有非常重要的價值和意義。
資源排程優化的主要目标是采用合适的資源排程政策實作資源的最優配置設定，并盡量使得配置設定結果滿足使用者的服務品質同時提高雲計算系統資源使用效率及降低能耗等要求。
1.3.2基于能耗優化的資源排程
由于雲計算大量的計算資源都集中在“雲端”，導緻雲計算的資源使用率不高且造成巨大的能耗浪費，是以，資料中心的能耗管理面臨着非常嚴峻的挑戰。
雲計算的巨大能耗已經成為阻礙其快速發展的制約因素之一。在這種情形下，學術界通常研究以下兩類方法：
基于DVFS的方法：目前，降低雲計算資料中心能耗的方法主要有基于DVFS技術的能耗優化，是大多數低功耗優化資源排程研究普遍采用的一種方法。
DVFS技術全稱是動态電壓頻率調整技術（Dynamic Voltage and Frequency Scaling，DVFS），其核心思想是當CPU沒有被完全利用時，通過降低CPU的供電電壓和時鐘頻率，減小系統動态功耗的目的。
基于DVFS技術的能耗優化排程算法是雲計算節能技術研究的重要基礎。任務臨界區的運作速度由靜态算法來控制，以求出任務處于離線狀态的執行速度。
即非臨界區的靜态速度，進而使得任務獲得更多的空閑時間；而臨界區的運作速度則由動态算法進行調節，保證了排程的實時性，并降低了能耗。
基于DVFS技術在計算節點閑置或低速運作（CPU的速率低）的情形下可以有效降低系統的空閑能耗。但是，這一類方法的弊端是同時減少了資源的供給，導緻CPU的性能會随之降低。
以虛拟化為中心的方法：除DVFS技術外，近年來越來越多的研究者關注于基于虛拟機的資源排程算法以降低雲計算資料中心的能耗。
虛拟化技術應用于節點硬體的同質化、隔離使用者及高效地處理不同的工作負載
研究了低代價虛拟機遷移方法，提出了一種再排程的能耗優化算法。
解決了網絡感覺的周期性資源重置問題，算法有效提升了虛拟機的整體運作效率。
針對應用層的資源排程和資源使用效率問題，提出了一種基于門檻值的動态資源配置設定算法。
算法以單個虛拟資源為動态配置設定資源的基本機關，通過負載的變化情況來動态地排程虛拟資源，實驗證明了提出的方法能夠提高資源使用率并降低使用者使用成本。
将CPU和GPU耦合到一個單一的晶片上，針對這種CPU-GPU體系結構，文獻[25]提出了一種彈性多資源公平配置設定政策來捕捉公平與效率之間的權衡。
而遷移的次數、遷移的規模及遷移的影響等因素不得不考慮。如上所述，基于能耗優化的資源排程算法思想固然有許多優勢的決策基礎。
但同時也應該注意到，這類算法思想仍存在諸多需要深入解決和研究的問題。
1.3.3基于智能優化的資源排程
雲計算資源排程不可能在多項式時間複雜度内獲得全局最優解是以，針對資源排程的NP-Hard 問題求近似解已成為國内外科學研究者們非常關注的熱點問題。這些算法的特點是通過模拟自然過程或自然現象，具有自學習、自組織、自适應及高并行性等特點。
這一類智能優化算法主要分為單目标優化和多目标優化兩種：單目标優化方法：提出了一個改進的粒子群優化算法，提高了粒子群算法收斂速度，避免了算法易陷入局部極小值的問題。
與傳統算法不同，改進的算法在合作架構的基礎上通過語義角色和概念來更新關鍵參數。
屬于一典型的NP-hard 問題，提出了一個JSP的蟻群優化算法，通過使虛拟機閑置時間最小化來實作負載的平衡。
以上大多基于智能優化資源排程算法都是基于經典的啟發式算法，經過适當地改進可應用于解決資源排程與配置設定問題，進而在較短的時間内把海量任務映射到合适的計算資源
多目标優化方法：現實應用中的很多問題都存在着多個目标，但往往有些目标是互相競争互相排斥的。
多目标智能優化排程主要關注經濟成本、能耗問題、服務品質及系統性能等目标。由于多目标優化排程問題有多個帕累托最優解，并且帕累托最優解集在解空間往往會形成一個邊界線或者邊界面。
是以，對于這一類問題很難找到使幾個優化目标或各個目标函數同時實作最優解的結果，隻能對其進行折中處理。
以多目标為限制條件的多目标優化的相關研究工作有很多。針對雲計算任務排程問題，通過詳細地定義任務對資源的需求特性提出了一個資源成本模型。
并根據提出的模型提出了一個多目标優化排程算法，算法以完工時間和使用者預算成本為優化的。
是以，DRBF配置設定政策保障資源公平性不受使用者欺騙行為影響，不僅滿足真實性在資源使用率、使用者所得總任務數及資源配置設定量等方面，表現優于其他三種算法；不僅保證了資源配置設定的公平性，而且提高了系統資源使用率。