孫衛(wèi)真，王秀錦，徐遠(yuǎn)超

（首都師范大學(xué)信息工程學(xué)院，北京100048）

0 引 言

隨著交通信息采集技術(shù)的改進(jìn)和發(fā)展，城市交通數(shù)據(jù)量迅速增長(zhǎng)。經(jīng)過2008年奧運(yùn)會(huì)，京交會(huì)及園博會(huì)等大型社團(tuán)活動(dòng)的交通數(shù)據(jù)多年的積累，以及出租車行業(yè)，特種行業(yè)浮動(dòng)車的數(shù)據(jù)匯集，交通數(shù)據(jù)量大且復(fù)雜，地理分布廣泛，數(shù)量已達(dá)到并超過PB級(jí)。因此，對(duì)這些交通數(shù)據(jù)進(jìn)行數(shù)據(jù)挖掘和建模、實(shí)時(shí)提取和處理進(jìn)而反饋誘導(dǎo)和交通控制已經(jīng)成為智慧城市的必需。利用分布式計(jì)算任務(wù)調(diào)度服務(wù)程序?qū)崿F(xiàn)計(jì)算機(jī)集群資源的統(tǒng)一調(diào)度是提高交通信息提取和分析準(zhǔn)確率以及信息實(shí)時(shí)性的有效方法。

Map Reduce（映射和化簡(jiǎn)）［1］是分布式計(jì)算框架中最為通用和重要的一個(gè)，其開源實(shí)現(xiàn)Hadoop（分布式處理軟件框架計(jì)算平臺(tái)）技術(shù)自發(fā)布以來就得到廣泛的推廣和應(yīng)用。該平臺(tái)不僅開源而且適合將各種資源、數(shù)據(jù)等部署在廉價(jià)的計(jì)算機(jī)上進(jìn)行分布式存儲(chǔ)和分布式管理［1］。

城市智能交通系統(tǒng)要將海量的交通信息在數(shù)據(jù)處理平臺(tái)上快速地部署和任務(wù)調(diào)度，以便為出行者提供及時(shí)有效的交通信息，滿足用戶的實(shí)時(shí)性要求。Hadoop是用于對(duì)海量數(shù)據(jù)進(jìn)行分布式處理的并行系統(tǒng)，在大型集群上對(duì)數(shù)以萬計(jì)的作業(yè)和任務(wù)執(zhí)行調(diào)度，要想使得系統(tǒng)能夠高效完成用戶提交的任務(wù)，就需要對(duì)平臺(tái)的調(diào)度算法進(jìn)行優(yōu)化，以期獲得較好的運(yùn)算效率。

為了提高Hadoop平臺(tái)對(duì)海量交通數(shù)據(jù)的處理能力，在開源框架Hadoop性能以及智能交通數(shù)據(jù)處理算法的基礎(chǔ)上，針對(duì)城市交通數(shù)據(jù)特點(diǎn)，提出了適合不同交通數(shù)據(jù)類型的改進(jìn)型計(jì)算能力調(diào)度算法，以期提高海量智能交通數(shù)據(jù)的處理效率。

1 分布式調(diào)度算法

當(dāng)前Hadoop平臺(tái)下最常用的作業(yè)調(diào)度算法有FIFO（先進(jìn)先出調(diào)度）算法、fair scheduler（公平調(diào)度）算法和capacity scheduler（計(jì)算能力調(diào)度）算法3種。在分布式系統(tǒng)中，作業(yè)的調(diào)度以及計(jì)算能力的均衡和計(jì)算節(jié)點(diǎn)的效率是衡量一個(gè)算法優(yōu)劣的主要指標(biāo)，提高分布式計(jì)算的效率也必然從這幾個(gè)方面對(duì)調(diào)度算法進(jìn)行改進(jìn)。Zaharia M等人針對(duì)多用戶并發(fā)作業(yè)提出了一種基于細(xì)粒度資源共享的公平調(diào)度算法——Quincy，在數(shù)據(jù)量減少一小部分的情況下可大幅度提升集群的吞吐率［2］；2010年Isard M等人使用600臺(tái)計(jì)算機(jī)組成的集群，通過處理Facebook數(shù)據(jù)證明公平調(diào)度與數(shù)據(jù)的本地化是一對(duì)矛盾體，并且在公平調(diào)度算法的基礎(chǔ)上加入了延時(shí)調(diào)度的思想，大幅度提升了數(shù)據(jù)的本地化比例［3］；Yahoo公司開發(fā)的“計(jì)算能力調(diào)度算法”模擬出具有指定計(jì)算能力的獨(dú)立的集群資源為不同用戶作業(yè)提供服務(wù)，此算法分為隊(duì)列間的調(diào)度和隊(duì)列內(nèi)調(diào)度［4，5］。多個(gè)隊(duì)列可以保證每個(gè)隊(duì)列的計(jì)算能力，并且計(jì)算能力調(diào)度是一種基于資源的調(diào)度，計(jì)算更具有靈活性。

但是計(jì)算能力調(diào)度算法沒有全面考慮用戶多樣性的特點(diǎn)，在單隊(duì)列中的調(diào)度仍然采用的是先進(jìn)先出的策略；另外交通信息的實(shí)時(shí)性和緊急性決定了在處理此類信息的算法中必須具有很強(qiáng)的交互性，并且算法的實(shí)時(shí)性與本地化計(jì)算比例密切相關(guān)。

所以針對(duì)交通信息數(shù)據(jù)的特殊性，調(diào)度隊(duì)列在分配作業(yè)時(shí)需要有更好的匹配策略［4，6］；交通數(shù)據(jù)短作業(yè)較多，作業(yè)類型不同，所以作業(yè)之間的相互依賴關(guān)系會(huì)變得更加復(fù)雜，這也勢(shì)必會(huì)增加計(jì)算中的延時(shí)［7］。因此在分布式系統(tǒng)中處理交通數(shù)據(jù)，需要根據(jù)城市交通的特點(diǎn)設(shè)計(jì)出適合其應(yīng)用的調(diào)度算法，從而提高資源的利用率，提高平臺(tái)的計(jì)算效率。

2 Hadoop調(diào)度算法及優(yōu)化

基于對(duì)分布式作業(yè)調(diào)度算法的研究以及對(duì)城市交通信息數(shù)據(jù)的分析，針對(duì)大規(guī)模分布式離散的交通信息處理提出了基于計(jì)算能力調(diào)度算法的改進(jìn)算法，即在原算法的基礎(chǔ)上加入了多種作業(yè)調(diào)度的策略，包括先進(jìn)先出結(jié)合短作業(yè)策略、緊急搶斷策略、作業(yè)隊(duì)列匹配策略和延時(shí)調(diào)度策略。改進(jìn)后的算法繼承了經(jīng)典計(jì)算能力調(diào)度算法多隊(duì)列作業(yè)調(diào)度模型所具有的穩(wěn)定性、擴(kuò)展性和并行性好的優(yōu)勢(shì)，并對(duì)交通信息數(shù)據(jù)的處理具有針對(duì)性。

計(jì)算能力調(diào)度算法支持多個(gè)隊(duì)列，以保證其計(jì)算能力，考慮到交通信息中用戶具有多樣性，設(shè)計(jì)隊(duì)列時(shí)按不同類型簡(jiǎn)單劃分為長(zhǎng)作業(yè)隊(duì)列和短作業(yè)隊(duì)列，長(zhǎng)作業(yè)隊(duì)列專門處理大作業(yè)，短作業(yè)隊(duì)列可專門處理小作業(yè)，這樣對(duì)作業(yè)的處理針對(duì)性強(qiáng)，可提高作業(yè)處理效率。隊(duì)列劃分的實(shí)現(xiàn)需要額外設(shè)計(jì)一個(gè)作業(yè)篩選器，專門負(fù)責(zé)將作業(yè)劃分歸類，歸類流程如圖1所示。

圖1 隊(duì)列與作業(yè)劃分匹配篩選

篩選器在初始化隊(duì)列時(shí)將隊(duì)列根據(jù)需要?jiǎng)澐殖砷L(zhǎng)時(shí)作業(yè)隊(duì)列與短時(shí)作業(yè)隊(duì)列，作業(yè)調(diào)度器收納作業(yè)，將不同的作業(yè)類型分別排隊(duì)，形成不同類型的作業(yè)隊(duì)列。同時(shí)對(duì)隊(duì)列類型的屬性做一些配置上的優(yōu)化，比如短作業(yè)類型的隊(duì)列，此種作業(yè)規(guī)模比較小，但往往比較多且雜，可以在初始化時(shí)將min Map和min Reduce參數(shù)調(diào)整為較大值。針對(duì)交通數(shù)據(jù)而言，經(jīng)初步統(tǒng)計(jì)這樣的作業(yè)占據(jù)大多數(shù)，所以資源分配的比重相應(yīng)也較大。通過改變參數(shù)值和加權(quán)處理，不同類型的作業(yè)在執(zhí)行時(shí)變得有序、高效，而且能夠取得較好的交互性。

在經(jīng)典的計(jì)算能力調(diào)度中，在單個(gè)隊(duì)列中默認(rèn)采用的是先進(jìn)先出的調(diào)度策略，這雖然易于實(shí)現(xiàn)，但對(duì)于處理交通信息數(shù)據(jù)這一類的分布式數(shù)據(jù)并不適用。在海量交通信息中，數(shù)據(jù)量雖然龐大，但單個(gè)作業(yè)規(guī)模往往并不會(huì)呈現(xiàn)出大文件的趨勢(shì)，而是區(qū)域化的短作業(yè)會(huì)比較多，這時(shí)若有長(zhǎng)作業(yè)一直占用系統(tǒng)資源運(yùn)行會(huì)使得短作業(yè)遲遲得不到執(zhí)行而形成饑餓。所以針對(duì)特定的交通信息在這里將算法設(shè)計(jì)成“基于先進(jìn)先出原則的短作業(yè)優(yōu)先”策略，即在短作業(yè)優(yōu)先執(zhí)行的前提下，再按先進(jìn)先出算法進(jìn)行作業(yè)隊(duì)列排序，流程圖如圖2所示。

在單個(gè)作業(yè)隊(duì)列內(nèi)部，如果用戶提交的作業(yè)中有各種不同類型的作業(yè)，例如復(fù)雜計(jì)算的大作業(yè)，簡(jiǎn)單處理的小作業(yè)，強(qiáng)數(shù)據(jù)依賴型作業(yè)，弱數(shù)據(jù)依賴型作業(yè)等。當(dāng)按照某一調(diào)度策略（如小作業(yè)優(yōu)先）時(shí)，往往小作業(yè)會(huì)出現(xiàn)在同一隊(duì)列的不同節(jié)點(diǎn)上，這個(gè)時(shí)候如果按照小作業(yè)隊(duì)列優(yōu)先執(zhí)行，那么可能會(huì)形成較大的網(wǎng)絡(luò)數(shù)據(jù)流量，造成網(wǎng)絡(luò)阻塞。所以在保證小作業(yè)優(yōu)先執(zhí)行的情況下，為了不影響網(wǎng)絡(luò)的負(fù)載能力，需要加入延時(shí)調(diào)度策略，將短作業(yè)優(yōu)先調(diào)度改進(jìn)策略與延時(shí)策略相結(jié)合，改善網(wǎng)絡(luò)間通信的質(zhì)量。程序設(shè)計(jì)見下列語(yǔ)句:

收納作業(yè)并將作業(yè)Job List初始化為隊(duì)列

if節(jié)點(diǎn)D發(fā)送HeartBeat到master then

if節(jié)點(diǎn)D釋放SparePool then

for作業(yè)（循環(huán)）

J＝Job List.get（n），0＝＜Job List.length（），n＋＋；

if作業(yè)J有一個(gè)在節(jié)點(diǎn)D上的本地性任務(wù)then

立即運(yùn)行

elseif網(wǎng)絡(luò)負(fù)載＞＝M then

調(diào)用延時(shí)函數(shù)delaysometime（）；

if作業(yè)J.wait＜T then

立即執(zhí)行長(zhǎng)任務(wù)或者強(qiáng)依賴型任務(wù)或者本地性較強(qiáng)的任務(wù)；

else

停止延時(shí)函數(shù)；

endif

endif

endfor

endif

endif

在上述調(diào)度策略下，如果出現(xiàn)較大的網(wǎng)絡(luò)流量負(fù)載，當(dāng)達(dá)到閾值M時(shí)，它會(huì)自動(dòng)觸發(fā)延時(shí)調(diào)度函數(shù)，并且在延時(shí)調(diào)度期間計(jì)算機(jī)資源會(huì)轉(zhuǎn)向運(yùn)行其它長(zhǎng)作業(yè)或者依賴型作業(yè)以及其它數(shù)據(jù)本地性較強(qiáng)的作業(yè)。延時(shí)調(diào)度的時(shí)間有一個(gè)最大值T，可以根據(jù)網(wǎng)絡(luò)負(fù)載狀況做實(shí)時(shí)調(diào)整。延時(shí)策略有利于加強(qiáng)數(shù)據(jù)的本地性，有利于減小節(jié)點(diǎn)間網(wǎng)絡(luò)數(shù)據(jù)傳輸壓力，特別地對(duì)分布式計(jì)算系統(tǒng)有實(shí)際使用價(jià)值。

交通信息的實(shí)時(shí)性和突發(fā)性決定了在處理此類信息的算法中應(yīng)該具有很強(qiáng)的交互性，這時(shí)需要引入緊急作業(yè)搶斷資源的算法來實(shí)現(xiàn)。對(duì)于常規(guī)調(diào)度算法來說，如何選擇下一個(gè)合適的作業(yè)運(yùn)行是其核心問題，所有隊(duì)列預(yù)先被初始化為一個(gè)資源量，如果有隊(duì)列處于空閑狀態(tài)，它的資源將被分配給當(dāng)前最忙的隊(duì)列。所謂忙，是指正在運(yùn)行的作業(yè)數(shù)與分配所得資源的比BR

比值越大越忙。這表示計(jì)算能力調(diào)度算法所具有的特性。但是如果在所有隊(duì)列間的隊(duì)列都無空閑資源的情況下，遇到突發(fā)情況，某一作業(yè)需要緊急執(zhí)行，就需要把低優(yōu)先級(jí)的作業(yè)先掛起，暫時(shí)把系統(tǒng)資源讓給緊急性作業(yè)。等緊急作業(yè)執(zhí)行完畢，釋放資源后再根據(jù)當(dāng)時(shí)的優(yōu)先級(jí)情況判斷是否繼續(xù)執(zhí)行暫停的作業(yè)。改進(jìn)后的狀態(tài)轉(zhuǎn)換如圖3所示。

圖3 緊急作業(yè)搶斷資源下的狀態(tài)轉(zhuǎn)換

3 算法實(shí)現(xiàn)及實(shí)驗(yàn)結(jié)論

改進(jìn)后的算法中依然是使用3種粒度的對(duì)象:queue（隊(duì)列）、job（作業(yè)）和task（任務(wù)），分別維護(hù)著相關(guān)作業(yè)的一些信息?；诟倪M(jìn)型計(jì)算能力算法是基于計(jì)算能力調(diào)度的改進(jìn)，所以基本上保持了計(jì)算能力調(diào)度算法的架構(gòu)。算法實(shí)現(xiàn)的代碼主要由5個(gè)java程序組成，改進(jìn)的算法結(jié)構(gòu)如圖4所示。

從圖4中可以看出，此改進(jìn)算法的核心類是ECapacity TaskSheduler，與之關(guān)聯(lián)的類主要有文件配置類ECapacityShedulerConf，初始化類EJobInitialzationPoller，隊(duì)列管理類EJob Queue Manager和內(nèi)存容量匹配類EMemory Matcher。

核心類ECapacity TaskSheduler中有各種不同功能的方法，其中有調(diào)度器初始化函數(shù)start（），該函數(shù)初始化各種對(duì)象和變量等并加載配置文件；當(dāng)其中有一個(gè)Task Tracker的HeartBeat到達(dá)Job Tracker時(shí)，如果有spare的slot，Job Tracker（作業(yè)追蹤器）會(huì)調(diào)用調(diào)度器ECapacityScheduler中的assign Task（），該方法會(huì)根據(jù)Task Tracker的需要找若干個(gè)合適的task。本文算法的改進(jìn)主要是在原計(jì)算能力調(diào)度算法框架下添加一些變量和函數(shù)，以達(dá)到提高處理交通信息數(shù)據(jù)效率的要求。添加的變量主要包括Task－Type、weigh、isShortJob等；添加的函數(shù)包括:優(yōu)先級(jí)設(shè)定與獲取函數(shù)setJobPriority（）/getJobPriority（），短作業(yè)判定函數(shù)isShortJob（），隊(duì)列類型作業(yè)類型匹配函數(shù)matchJoband Queue（），延時(shí)調(diào)度函數(shù)delaysometime（）。重新編寫了sort Queue（）方法，主要是在重新排序隊(duì)列時(shí)加入了短作業(yè)優(yōu)先級(jí)等屬性，還在配置文件conf中做了一些文件設(shè)定的參數(shù)配置與修改，包括map，reduce最大最小數(shù)目，隊(duì)列分配容量百分比，最大負(fù)載能力等。

實(shí)驗(yàn)測(cè)試環(huán)境采用了3個(gè)數(shù)據(jù)節(jié)點(diǎn)，一個(gè)主節(jié)點(diǎn)，PC機(jī)的設(shè)置均對(duì)等相當(dāng)。Hadoop平臺(tái)搭建好之后，為保證新的改進(jìn)型調(diào)度算法的有效執(zhí)行需要從以下幾個(gè)方面進(jìn)行優(yōu)化:

（1）優(yōu)化應(yīng)用程序。由于Map Reduce的算法是逐行迭代來解析數(shù)據(jù)文件的，所以為提高程序的編寫效率，應(yīng)優(yōu)先設(shè)計(jì)優(yōu)化迭代算法。

（2）Hadoop系統(tǒng)參數(shù)的優(yōu)化。主要包括:Linux文件系統(tǒng)參數(shù)調(diào)整，文件掛載時(shí)設(shè)置noatime和nodiratime這兩個(gè)屬性可以明顯提高文件系統(tǒng)的性能，在可行的范圍內(nèi)調(diào)整Readahead buffer參數(shù)可以明顯改變文件順序讀取的性能，其實(shí)際上是修改Linux操作系統(tǒng)中文件緩沖區(qū)的容量。另外要避免在Task Tracker和Data Node節(jié)點(diǎn)上執(zhí)行RAID和LVM的操作；Hadoop通用參數(shù)調(diào)整，namenode、jobtracker、datanode中用于處理RPC（遠(yuǎn)程過程調(diào)用）的線程數(shù)的參數(shù)以及HTTP server上運(yùn)行的線程數(shù)的參數(shù)，在針對(duì)不同規(guī)模的集群時(shí)需要做相應(yīng)的調(diào)整與設(shè)置；Hadoop作業(yè)調(diào)優(yōu)參數(shù)設(shè)置:主要包括Map（映射）階段的中間結(jié)果及最終結(jié)果的壓縮和Reduce（簡(jiǎn)化）階段task的參數(shù)調(diào)優(yōu)。

為了測(cè)試改進(jìn)型算法的有效性，實(shí)驗(yàn)?zāi)M交通信息數(shù)據(jù)的特點(diǎn)，采用兩種類型的測(cè)試場(chǎng)景及用例，I/O密集型WordCount和計(jì)算密集型Sort，采用控制變量法，分別統(tǒng)計(jì)多用戶多作業(yè)提交模式下，不同算法和不同數(shù)據(jù)規(guī)模的作業(yè)平均運(yùn)行時(shí)間。

I/O密集型計(jì)算指的是系統(tǒng)的CPU多處于空閑狀態(tài)，而I/O（硬盤/內(nèi)存）的繁忙率較高，系統(tǒng)運(yùn)行時(shí)往往呈現(xiàn)出CPU的利用率較低。在I/O密集型的測(cè)試中，本實(shí)驗(yàn)采用了詞頻統(tǒng)計(jì)WordCount基準(zhǔn)測(cè)試樣例。采用該測(cè)試樣例的原因是詞頻統(tǒng)計(jì)的數(shù)據(jù)結(jié)構(gòu)與交通數(shù)據(jù)中離散分布的數(shù)據(jù)結(jié)構(gòu)十分類似，如統(tǒng)計(jì)某一段時(shí)間里各個(gè)路口小轎車，巴士，大貨車等各類型車輛的通過數(shù)量以及其速度等，這和WordCount的詞頻統(tǒng)計(jì)是十分類似的。其實(shí)驗(yàn)結(jié)果如圖5所示。

圖5 I/O密集型計(jì)算不同調(diào)度算法效率對(duì)比

從圖5的統(tǒng)計(jì)圖可以看出，在多用戶多作業(yè)條件下，先進(jìn)先出算法對(duì)于I/O密集型的計(jì)算效率明顯不及公平調(diào)度、計(jì)算能力調(diào)度以及改進(jìn)型計(jì)算能力調(diào)度算法，在這種情況下，選用FIFO算法是非常不明智的做法，另外對(duì)于多用戶多作業(yè)情況下，數(shù)據(jù)規(guī)模越大，計(jì)算能力和改進(jìn)型計(jì)算能力調(diào)度算法為最優(yōu)算法，改進(jìn)的算法比原算法稍有提高。

計(jì)算密集型指的是系統(tǒng)的I/O（硬盤/內(nèi)存）繁忙率相對(duì)CPU的繁忙率要低，系統(tǒng)運(yùn)作時(shí)，往往是I/O（硬盤/內(nèi)存）的讀/寫時(shí)間較短，需要等待CPU的處理。在計(jì)算密集型的測(cè)試中，實(shí)驗(yàn)數(shù)據(jù)采用了一周的某出租汽車公司的GPS信息，提取其中的路徑和平均速度。分別測(cè)試了經(jīng)典算法以及改進(jìn)算法下的數(shù)據(jù)處理性能。其實(shí)驗(yàn)結(jié)果如圖6所示。

圖6 計(jì)算密集型不同調(diào)度算法之間的效率對(duì)比

從圖6可以看出，此次實(shí)驗(yàn)的執(zhí)行時(shí)間的增長(zhǎng)幅度要大于I/O密集型計(jì)算。在多用戶多作業(yè)模式下，對(duì)于數(shù)據(jù)量小于5G的作業(yè)，4種算法執(zhí)行時(shí)間相當(dāng)；對(duì)于數(shù)據(jù)量大于5G的作業(yè)，改進(jìn)的計(jì)算能力調(diào)度算法的執(zhí)行時(shí)間相比其它3種算法較短，并且增長(zhǎng)速度較緩慢，而先進(jìn)先出算法在此種情況下表現(xiàn)最不佳，公平算法次之。

兩次實(shí)驗(yàn)結(jié)果均顯示改進(jìn)型的調(diào)度算法相較之前的計(jì)算能力調(diào)度算法性能有所提高，說明本文所述的改進(jìn)方向是可行的。

對(duì)于緊急作業(yè)搶斷資源的算法通常是通過設(shè)定作業(yè)優(yōu)先級(jí)的方法來實(shí)現(xiàn)的。在實(shí)驗(yàn)中，不同優(yōu)先級(jí)下作業(yè)的運(yùn)行時(shí)間是不同的，這主要是基于調(diào)度分配的隊(duì)列和該隊(duì)列所擁有的資源所決定的。實(shí)驗(yàn)中采用改進(jìn)型計(jì)算能力算法為測(cè)試算法，初始資源分配百分比為40%，在單一緊急作業(yè)模式下（即只有一個(gè)緊急作業(yè)進(jìn)行資源搶斷），計(jì)算機(jī)三機(jī)集群分別運(yùn)行在I/O密集型和計(jì)算密集型數(shù)據(jù)集上，測(cè)試用例數(shù)據(jù)規(guī)模為1GB，結(jié)果見表1和表2。

表1 緊急作業(yè)在不同優(yōu)先級(jí)下運(yùn)行時(shí)間統(tǒng)計(jì)1

表2 緊急作業(yè)在不同優(yōu)先級(jí)下運(yùn)行時(shí)間統(tǒng)計(jì)2

從表1和表2的結(jié)果中可以看出，優(yōu)先級(jí)分為5級(jí)，從1到5依次升高，最高優(yōu)先級(jí)為5。在各級(jí)不同的優(yōu)先級(jí)中，一般會(huì)在標(biāo)準(zhǔn)或以上優(yōu)先級(jí)時(shí)才執(zhí)行搶先策略。作業(yè)會(huì)搶占系統(tǒng)資源來運(yùn)行優(yōu)先級(jí)高的作業(yè)。當(dāng)達(dá)到最高優(yōu)先級(jí)時(shí)，該作業(yè)所用時(shí)間最少，結(jié)果很明顯；對(duì)于低優(yōu)先級(jí)的作業(yè)，它們的運(yùn)行時(shí)間凸顯出很長(zhǎng)（如表1中優(yōu)先級(jí)值為1和2時(shí)），有時(shí)還不能確定（如表2中優(yōu)先級(jí)值為1和2時(shí)），原因是如果有高優(yōu)先級(jí)的作業(yè)在提交運(yùn)行，且高優(yōu)先級(jí)作業(yè)源源不斷，則低優(yōu)先級(jí)的作業(yè)就難以得到運(yùn)行，除非等到?jīng)]有高優(yōu)先級(jí)的作業(yè)提交，它才可以進(jìn)入隊(duì)列進(jìn)行排隊(duì)等待被調(diào)度。這種現(xiàn)象在計(jì)算密集型作業(yè)中特別明顯，各個(gè)隊(duì)列的資源幾乎被常規(guī)作業(yè)占用，緊急作業(yè)難以搶斷，呈現(xiàn)出一種“饑餓”的狀態(tài)。相對(duì)I/O密集型的作業(yè)，由于I/O切換期間會(huì)短暫出現(xiàn)隊(duì)列空閑的現(xiàn)象，所以呈現(xiàn)出來的運(yùn)行時(shí)間可信，但也是大大高于標(biāo)準(zhǔn)或以上優(yōu)先級(jí)的運(yùn)行時(shí)間。因此，對(duì)于緊急事件，一定首先賦予該作業(yè)較高的甚至是最高的優(yōu)先級(jí)，同時(shí)輔之以其它措施，例如，可以暫時(shí)延時(shí)其它作業(yè)的調(diào)度等，以保證緊急作業(yè)得到優(yōu)先執(zhí)行。

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

依據(jù)城市交通信息數(shù)據(jù)特點(diǎn)，對(duì)傳統(tǒng)計(jì)算能力調(diào)度算法進(jìn)行了優(yōu)化與實(shí)現(xiàn)，彌補(bǔ)了傳統(tǒng)算法的不足之處，使得優(yōu)化后的算法能夠適應(yīng)城市智能交通數(shù)據(jù)處理，實(shí)驗(yàn)結(jié)果表明，改進(jìn)的計(jì)算能力調(diào)度算法無論是從交互性，還是從數(shù)據(jù)處理性能上，在處理大規(guī)模分布式的城市交通數(shù)據(jù)時(shí)都具有一定的優(yōu)勢(shì)。城市交通將會(huì)是未來海量數(shù)據(jù)研究的重點(diǎn)之一，下一步將使用該算法對(duì)城市交通數(shù)據(jù)進(jìn)行更深層次處理，探索更加實(shí)際的應(yīng)用，以滿足用戶的需求。

［1］XU Xiaolong，WU Jiaxing，YANG Geng，et al.Mass data processing system based on large－scale low－cost computing platform［J］.Application Research of Computers，2012，29（2）:582－585（in Chinese）.［徐小龍，吳家興，楊庚，等.基于大規(guī)模廉價(jià)計(jì)算平臺(tái)的海量數(shù)據(jù)處理系統(tǒng)的研究［J］.計(jì)算機(jī)應(yīng)用研究，2012，29（2）:582－585.］

［2］Zaharia M，Borthakur D，Sen Sarma J，et al.Delay scheduling:A simple technique for achieving locality and fairness in cluster scheduling［C］//Proceedings of the 5th European Conference on Computer Systems.New York:ACM，2010:265－278.

［3］Isard M，Prabhakaran V，Currey J，et al.Quincy:Fair scheduling for distributed computing clusters［C］//Proceedings of the 22nd Symposium on Operating Systems Principles.New York:ACM，2009:261－276.

［4］DENG Chuanhua，F(xiàn)AN Tongrang，GAO Feng.Resource scheduler algorithm based on statistical optimization under Hadoop［J］.Application Research of Computers，2013，30（2）:417－419（in Chinese）.［鄧傳華，范通讓，高峰.Hadoop下基于統(tǒng)計(jì)最優(yōu)的資源調(diào)度算法［J］.計(jì)算機(jī)應(yīng)用研究，2013，30（2）:417－419.］

［5］WANG Feng.Scheduling algorithm of Hadoop cluster job scheduling algorithm［J］.Programmer，2009，10（12）:1－19（in Chinese）.［王峰.Hadoop集群作業(yè)的調(diào)度算法［J］.程序員，2009，10（12）:1－19.］

［6］Dean J，Ghemawat S.MapReduce:Simplified data processing on large clusters［J］.Communications of the ACM，2008，51（1）:107－113.

［7］You H H，Yang C C，Huang J L.A load－aware scheduler for Map Reduce framework in heterogeneous cloud environments［C］//Proceedings of the 2011 ACM Symposium on Applied Computing.New York:ACM，2011:127－132.

［8］Fischer M J，Su X，Yin Y.Assigning tasks for efficiency in Hadoop［C］//Proceedings of the 22nd ACM Symposium on Parallelism in Algorithms and Architectures.New York:ACM，2010:30－39.

［9］Liu X，Lu F，Zhang H，et al.Estimating Beijing's travel de－lays at intersections with floating car data［C］//Proceedings of the 5th International Workshop on Computational Transportation Science.New York:ACM，2012:14－19.

［10］Edwards M，Rambani A，Zhu Y，et al.Design of Hadoopbased framework for analytics of large synchrophasor datasets［J］.Procedia Computer Science，2012，12:254－258.

［11］DING Yuguang，LIU Wenjie，WANG Weilin.Research on capacity scheduling algorithm based on QoS constraints［J］.Journal of Sichuan University of Science ＆Engineering（Na－tural Science Edition），2012，25（3）:47－50（in Chinese）.［丁宇光，劉文杰，王衛(wèi)林.基于QoS約束的計(jì)算能力調(diào)度算法研究［J］.四川理工學(xué)院學(xué)報(bào)（自然科學(xué)版），2012，25（3）:47－50.］