苑立娟

摘 要：MapReduce調(diào)度算法包括默認(rèn)的FIFO調(diào)度策略、公平調(diào)度策略、計(jì)算能力調(diào)度策略，在試題庫(kù)組卷過(guò)程中采用的是分階段的任務(wù)方式來(lái)實(shí)現(xiàn)的，根據(jù)任務(wù)優(yōu)化MapReduce算法是本文要解決的問(wèn)題。提出分級(jí)調(diào)度算法，把現(xiàn)有的調(diào)度策略在分級(jí)任務(wù)基礎(chǔ)之上分為多級(jí)模式，不斷趨近最終結(jié)果，根據(jù)任務(wù)的不同階段進(jìn)行分級(jí)分階調(diào)度符合不同階段不同需求。實(shí)驗(yàn)表明，多階段調(diào)度算法能夠滿(mǎn)足試題庫(kù)組卷任務(wù)的檢索需求。

關(guān)鍵詞：云計(jì)算；MapReduce；分級(jí)調(diào)度；組卷

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

首先，任務(wù)分級(jí)劃界。MapReduce會(huì)將一個(gè)任務(wù)分解為多個(gè)子任務(wù)，而試題庫(kù)組卷過(guò)程也是一個(gè)分級(jí)不斷靠近需求的過(guò)程，本文第一層級(jí)任務(wù)確定題型和分?jǐn)?shù)，第二層級(jí)任務(wù)根據(jù)題型和分?jǐn)?shù)確定試題個(gè)數(shù)，第三層級(jí)任務(wù)對(duì)難度系數(shù)進(jìn)行優(yōu)化，第四層級(jí)任務(wù)迭代微調(diào)。其次，層級(jí)上下文銜接。一層級(jí)任務(wù)完成后，應(yīng)該把結(jié)果及其參數(shù)傳遞給二層級(jí)，依次類(lèi)推。

結(jié)合MapReduce的調(diào)度過(guò)程，本文提出了分級(jí)調(diào)度的概念，每級(jí)層調(diào)度選擇該層級(jí)的較為優(yōu)秀的調(diào)度方法。整個(gè)任務(wù)被分為多層有先后的子任務(wù)，每個(gè)任務(wù)為下層任務(wù)提供參數(shù)進(jìn)行參考，該層任務(wù)提交給適合執(zhí)行的對(duì)象來(lái)處理。

1 MapReduce任務(wù)調(diào)度過(guò)程

MapReduce是Hadoop框架的一種編程模式，是進(jìn)行分布式數(shù)據(jù)處理的。它的關(guān)鍵在于Map（地圖）和Reduce（化簡(jiǎn)）。第一階段數(shù)據(jù)檢索過(guò)程，Map獲取系統(tǒng)或數(shù)據(jù)庫(kù)中的子數(shù)據(jù)，根據(jù)用戶(hù)設(shè)定好的Map函數(shù)將數(shù)據(jù)分為多個(gè)Key/Value對(duì)的子數(shù)據(jù)，排序后存儲(chǔ)與在客戶(hù)端。在化簡(jiǎn)階段，Reduce任務(wù)讀取相應(yīng)的子數(shù)據(jù)，這樣任務(wù)被分為多個(gè)子任務(wù)并行處理，提高數(shù)據(jù)處理的效率。整個(gè)過(guò)程處于主節(jié)點(diǎn)的控制之下，JobTracker負(fù)責(zé)對(duì)眾多節(jié)點(diǎn)進(jìn)行掌控。

2 多級(jí)分層調(diào)度思想

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

3 算法實(shí)現(xiàn)的流程

定義M函數(shù)，M=（T，F(xiàn)，N，C）；T定義為題型，F(xiàn)為分?jǐn)?shù)，N為難度系數(shù)，C其他用戶(hù)要求參數(shù)類(lèi)型。為任務(wù)1定義函數(shù)f1（T，F(xiàn)），通過(guò)MapReduce處理之后將結(jié)果x1賦值給函數(shù)f2，函數(shù)f2的定義為f2（N，x1），再次交給MapReduce處理將結(jié)果x2賦值給函數(shù)f3，f3定義為f3（x2，C）。將每個(gè)任務(wù)分別作為每個(gè)Mapper的輸入，每個(gè)Mapper處理一個(gè)任務(wù)的數(shù)據(jù)，按需求執(zhí)行運(yùn)算（因?yàn)檫@里對(duì)數(shù)值和題目的比例不一樣，調(diào)用的方法不一樣）并產(chǎn)生結(jié)果，Reducer把多個(gè)Mapper的結(jié)果組合即完成一次組卷。Master主控程序?qū)⑷蝿?wù)分配給Worker。Map任務(wù)負(fù)責(zé)檢索，Reduce任務(wù)負(fù)責(zé)整合。Map任務(wù)根據(jù)條件進(jìn)行數(shù)據(jù)檢索，獲得符合要求的題目的鍵值數(shù)據(jù)，將其傳遞給用戶(hù)定義的Reduce（）函數(shù)。Map產(chǎn)生的中間結(jié)果對(duì)緩沖到內(nèi)存。Map函數(shù)緩沖的中間結(jié)果被定時(shí)寫(xiě)到本地磁盤(pán)，這些數(shù)據(jù)根據(jù)需求利用分區(qū)函數(shù)被分別放置。這些中間結(jié)果即試題的位置信息發(fā)送給Master，Master負(fù)責(zé)把該位置信息傳遞給Reduce（）的Worker。通知傳遞后，Worker調(diào)用Map讀取本地機(jī)器上試題信息，讀取后標(biāo)記這些數(shù)據(jù)為被選用數(shù)據(jù)，即標(biāo)記該題被選用，選用次數(shù)加1。Reduce函數(shù)根據(jù)中間記過(guò)的key值進(jìn)行遍歷，把符合要求的數(shù)據(jù)集合后傳遞給Reduce，Reduce將結(jié)果存放在Master掌管的一個(gè)輸出文件中。

用戶(hù)程序綜合所有數(shù)據(jù)，形成最終結(jié)果。

4 測(cè)試與分析

通過(guò)實(shí)驗(yàn)測(cè)試，本文介紹的分層級(jí)調(diào)度算法對(duì)于1500道題庫(kù)4種題型分?jǐn)?shù)為10，20，30，40難度系數(shù)比例為1：1：2，最終獲得結(jié)果耗時(shí)2.35秒，對(duì)于3000道題庫(kù)4種題型分?jǐn)?shù)和難度系數(shù)比例同上的要求，最終獲得結(jié)果耗時(shí)4.88秒，對(duì)于9000道題庫(kù)4中題型分?jǐn)?shù)和難度系數(shù)比例同上的要求，最終獲得結(jié)果耗時(shí)7.12秒。可以獲得效果是比較滿(mǎn)意的。隨著題庫(kù)數(shù)量的不斷增加時(shí)間耗時(shí)不斷的增加，但是其結(jié)果是趨于越來(lái)越少的。

5 結(jié)束語(yǔ)

本文提出的分層級(jí)的試題庫(kù)組卷算法基本滿(mǎn)足了用戶(hù)的要求，通過(guò)對(duì)任務(wù)的特定的層級(jí)進(jìn)行分析，針對(duì)不同層級(jí)的不同要求選取適應(yīng)的調(diào)度方式來(lái)滿(mǎn)足要求，同時(shí)能夠保證任務(wù)的并行性和時(shí)間的高效性。

[參考文獻(xiàn)]

[1]劉吉，陳香蘭.一種MapReduce實(shí)時(shí)調(diào)度算法設(shè)計(jì)及實(shí)現(xiàn).計(jì)算機(jī)系統(tǒng)應(yīng)用，2013，22（8）：116-123.

[2]白東玲，郭紹永.改進(jìn)的遺傳算法在智能組卷系統(tǒng)中的應(yīng)用研究.計(jì)算機(jī)與現(xiàn)代化，2013，（3）：25-28.

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

[4]王凱，吳泉源.一種多用戶(hù)MapReduce集群的作業(yè)調(diào)度算法的設(shè)計(jì)與實(shí)現(xiàn).計(jì)算機(jī)與現(xiàn)代化，2010，（10）：23-28.