基于MapReduce分級調度的試題庫組卷算法研究

苑立娟

摘 要：MapReduce調度算法包括默認的FIFO調度策略、公平調度策略、計算能力調度策略，在試題庫組卷過程中采用的是分階段的任務方式來實現的，根據任務優化MapReduce算法是本文要解決的問題。提出分級調度算法，把現有的調度策略在分級任務基礎之上分為多級模式，不斷趨近最終結果，根據任務的不同階段進行分級分階調度符合不同階段不同需求。實驗表明，多階段調度算法能夠滿足試題庫組卷任務的檢索需求。

關鍵詞：云計算；MapReduce；分級調度；組卷

隨著云計算不斷的發展，各行各業都紛紛應用這種高效、安全和便捷的大數據、分布式服務。高等院校也都紛紛涉足云計算，分布式存儲、MapReduce算法以及基于云計算的各種服務系統等都在高校研究中有所體現。高等院?？荚囅到y的組卷過程是一個復雜的檢索過程，而這一過程正是云計算的強項，因此組卷算法如何利用云計算中的MapReduce編程模型來實現是本文研究的主要方向。MapReduce是Google公司開發的Hadoop框架中進行分布式數據處理的一種編程模型。在組卷過程中主要關注兩個問題：一個是組卷參數分級問題、一個是組卷分級任務中的各個級別的檢索問題。MapReduce的任務調度過程是將一個任務分為多個子任務進行并行處理，這個過程正好與組卷的任務有相同之處。MapReduce的調度分為：先進先出、公平調度和計算能力評估調度。這幾個調度算法對于特定的組卷任務來說并不是最優化的。試題庫組卷的過程可以分為多級多階段，將復雜的任務分層剝離。這樣化繁為簡，提高組卷的命中率和效率。本體提出了分級調度算法，該算法要解決的重要問題是：

首先，任務分級劃界。MapReduce會將一個任務分解為多個子任務，而試題庫組卷過程也是一個分級不斷靠近需求的過程，本文第一層級任務確定題型和分數，第二層級任務根據題型和分數確定試題個數，第三層級任務對難度系數進行優化，第四層級任務迭代微調。其次，層級上下文銜接。一層級任務完成后，應該把結果及其參數傳遞給二層級，依次類推。

結合MapReduce的調度過程，本文提出了分級調度的概念，每級層調度選擇該層級的較為優秀的調度方法。整個任務被分為多層有先后的子任務，每個任務為下層任務提供參數進行參考，該層任務提交給適合執行的對象來處理。

1 MapReduce任務調度過程

MapReduce是Hadoop框架的一種編程模式，是進行分布式數據處理的。它的關鍵在于Map（地圖）和Reduce（化簡）。第一階段數據檢索過程，Map獲取系統或數據庫中的子數據，根據用戶設定好的Map函數將數據分為多個Key/Value對的子數據，排序后存儲與在客戶端。在化簡階段，Reduce任務讀取相應的子數據，這樣任務被分為多個子任務并行處理，提高數據處理的效率。整個過程處于主節點的控制之下，JobTracker負責對眾多節點進行掌控。

2 多級分層調度思想

試題庫組卷過程在本文中可分為四層到多層，基礎為四層，如果得不到優化的結果，需要在最后一層進行不斷迭代優化來滿足用戶需求。四層任務從上到下依次是：題型確定層，該層需要很短的時間，時間可以忽略不計，只要獲取用戶設定的題型即可；分數確定層，這一層同上，也是直接獲得；而題型確定層和分數確定層之間的銜接問題應該要處理好，思路在于M為一個完整的一次組卷過程，這個過程定義如下所示：M=f1（f2（T，F），…，fn），M表示一個完整組卷任務，f1是任務分解函數，f2表示一層和二層銜接函數，fn表示N-1層和N層的銜接函數。這樣首位呼應的銜接方式，確保了能在一下層級中獲得上一層級的結果參數。緊接著就是難度系數確定層，獲得試題個數和分數之后，根據個數和分數的配比比例來進行難度系統比例分配，這個分配過程要求用戶提供配比比例，例如1：2：3等，如果由上層函數傳遞過來的分數為20分，很容易獲得難度個數比例，比例依次就是3：6：9+2，四舍五入最后多余的2道題則自動分配給難度最高的配比。當然，根據用戶的設定的難度要求，這個2可以分配給難度系數為1的部分，也可以分配給難度系數為2的部分。這樣任務就在第三層有了詳細的處理過程，分配給調度器檢索任務變的更加簡單而有效了。當三層級處理完畢后可以將結果參數傳遞給四層級，進行題庫覆蓋任務的調度處理，那么這個過程同樣也被細化了。

3 算法實現的流程

定義M函數，M=（T，F，N，C）；T定義為題型，F為分數，N為難度系數，C其他用戶要求參數類型。為任務1定義函數f1（T，F），通過MapReduce處理之后將結果x1賦值給函數f2，函數f2的定義為f2（N，x1），再次交給MapReduce處理將結果x2賦值給函數f3，f3定義為f3（x2，C）。將每個任務分別作為每個Mapper的輸入，每個Mapper處理一個任務的數據，按需求執行運算（因為這里對數值和題目的比例不一樣，調用的方法不一樣）并產生結果，Reducer把多個Mapper的結果組合即完成一次組卷。Master主控程序將任務分配給Worker。Map任務負責檢索，Reduce任務負責整合。Map任務根據條件進行數據檢索，獲得符合要求的題目的鍵值數據，將其傳遞給用戶定義的Reduce（）函數。Map產生的中間結果對緩沖到內存。Map函數緩沖的中間結果被定時寫到本地磁盤，這些數據根據需求利用分區函數被分別放置。這些中間結果即試題的位置信息發送給Master，Master負責把該位置信息傳遞給Reduce（）的Worker。通知傳遞后，Worker調用Map讀取本地機器上試題信息，讀取后標記這些數據為被選用數據，即標記該題被選用，選用次數加1。Reduce函數根據中間記過的key值進行遍歷，把符合要求的數據集合后傳遞給Reduce，Reduce將結果存放在Master掌管的一個輸出文件中。

用戶程序綜合所有數據，形成最終結果。

4 測試與分析

通過實驗測試，本文介紹的分層級調度算法對于1500道題庫4種題型分數為10，20，30，40難度系數比例為1：1：2，最終獲得結果耗時2.35秒，對于3000道題庫4種題型分數和難度系數比例同上的要求，最終獲得結果耗時4.88秒，對于9000道題庫4中題型分數和難度系數比例同上的要求，最終獲得結果耗時7.12秒?？梢垣@得效果是比較滿意的。隨著題庫數量的不斷增加時間耗時不斷的增加，但是其結果是趨于越來越少的。

5 結束語

本文提出的分層級的試題庫組卷算法基本滿足了用戶的要求，通過對任務的特定的層級進行分析，針對不同層級的不同要求選取適應的調度方式來滿足要求，同時能夠保證任務的并行性和時間的高效性。

[參考文獻]

[1]劉吉，陳香蘭.一種MapReduce實時調度算法設計及實現.計算機系統應用，2013，22（8）：116-123.

[2]白東玲，郭紹永.改進的遺傳算法在智能組卷系統中的應用研究.計算機與現代化，2013，（3）：25-28.

[3]李鋼.基于出題系統的隨機算法.軟件，2013，34（2）：84-85.

[4]王凱，吳泉源.一種多用戶MapReduce集群的作業調度算法的設計與實現.計算機與現代化，2010，（10）：23-28.