李 穎 孫曉良

(航天恒星科技有限公司,北京 100086)

1 引言

遙感衛(wèi)星地面系統(tǒng)從衛(wèi)星數(shù)據(jù)接收系統(tǒng)獲取衛(wèi)星遙感數(shù)據(jù),根據(jù)不同的業(yè)務(wù)需要,進(jìn)行不同級別和類型的衛(wèi)星數(shù)據(jù)產(chǎn)品的生產(chǎn)和分發(fā)。任務(wù)調(diào)度是遙感衛(wèi)星地面應(yīng)用系統(tǒng)的一個主要功能,負(fù)責(zé)系統(tǒng)內(nèi)的各類任務(wù)的調(diào)度。隨著衛(wèi)星數(shù)據(jù)應(yīng)用業(yè)務(wù)的快速發(fā)展,衛(wèi)星地面應(yīng)用系統(tǒng)規(guī)模增大,衛(wèi)星數(shù)據(jù)產(chǎn)品種類增多,處理流程日益復(fù)雜,任務(wù)量快速增長,需要一種有效的調(diào)度方法,實現(xiàn)自動、科學(xué)高效地系統(tǒng)資源調(diào)配與任務(wù)調(diào)度,滿足遙感數(shù)據(jù)產(chǎn)品快速、高效、可靠生產(chǎn)的需求[1]。

為了有效地利用計算資源,快速完成系統(tǒng)任務(wù),本文提出了一種基于任務(wù)優(yōu)先級策略的多線程并行任務(wù)調(diào)度方法。根據(jù)遙感衛(wèi)星應(yīng)用系統(tǒng)內(nèi)的任務(wù)特點(diǎn)設(shè)計多個優(yōu)先級隊列存儲任務(wù),采用多線程調(diào)度任務(wù)執(zhí)行,并用線程池管理多線程。該方法解決了衛(wèi)星數(shù)據(jù)產(chǎn)品生產(chǎn)流程復(fù)雜、任務(wù)量大、任務(wù)種類多等問題,提高了任務(wù)調(diào)度的實時性和并行性以及系統(tǒng)的資源利用率,解決了遙感衛(wèi)星地面應(yīng)用系統(tǒng)多任務(wù)并行調(diào)度時效性低的問題,最大限度地發(fā)揮遙感衛(wèi)星對地觀測系統(tǒng)的效益。

2 應(yīng)用場景

遙感衛(wèi)星應(yīng)用系統(tǒng)一般由數(shù)據(jù)管理、用戶服務(wù)、產(chǎn)品生產(chǎn)(n 個系統(tǒng))、運(yùn)行管理、數(shù)據(jù)傳輸分系統(tǒng)等組成。遙感衛(wèi)星應(yīng)用系統(tǒng)組成如圖1 所示[2]。

圖1 遙感衛(wèi)星應(yīng)用系統(tǒng)組成Fig.1 Composition of remote-sensing satellite application system

數(shù)據(jù)管理分系統(tǒng)建立綜合數(shù)據(jù)管理平臺,形成對海量數(shù)據(jù)的集成、存檔、管理與共享;用戶服務(wù)分系統(tǒng)以直接數(shù)據(jù)存取、數(shù)據(jù)查詢檢索和定制處理等多種形式,向各用戶提供目錄查詢、產(chǎn)品訂購和產(chǎn)品分發(fā)服務(wù);各產(chǎn)品生產(chǎn)分系統(tǒng)根據(jù)業(yè)務(wù)需求生產(chǎn)不同種類的數(shù)據(jù)產(chǎn)品;數(shù)據(jù)傳輸分系統(tǒng)從衛(wèi)星地面接收站或其他衛(wèi)星應(yīng)用系統(tǒng)采集獲取衛(wèi)星遙感數(shù)據(jù)。

運(yùn)行管理分系統(tǒng)是整個遙感衛(wèi)星地面應(yīng)用系統(tǒng)業(yè)務(wù)化自動運(yùn)行的中樞。其中任務(wù)調(diào)度功能是運(yùn)行管理分系統(tǒng)的核心,負(fù)責(zé)整個系統(tǒng)的任務(wù)制定、生產(chǎn)調(diào)度、流程監(jiān)視,控制系統(tǒng)內(nèi)的業(yè)務(wù)流程和數(shù)據(jù)流程,調(diào)度系統(tǒng)資源完成衛(wèi)星數(shù)據(jù)產(chǎn)品的生產(chǎn)和分發(fā)。

3 并行調(diào)度方法設(shè)計

3.1 優(yōu)先級隊列

傳統(tǒng)的優(yōu)先級隊列都是采用單一隊列存儲不同優(yōu)先級別的任務(wù),在優(yōu)先級隊列中任務(wù)按照優(yōu)先級大小排序,有新的任務(wù)加入到優(yōu)先級隊列時,需要在隊列中尋找合適的位置,即使采用最快速的排序算法,隊列的排序和任務(wù)的插入操作所耗費(fèi)的時間也隨著任務(wù)量的增加呈線性增長,而且算法復(fù)雜,不易于實現(xiàn)。另外,在單一的隊列中,優(yōu)先級別低的任務(wù)可能會一直排在隊列的末尾,會造成長時間得不到執(zhí)行的問題[3]。

本文設(shè)計的方法采用多個優(yōu)先級隊列存儲不同優(yōu)先級的任務(wù),改變了傳統(tǒng)采用單一隊列需要使用排序算法將任務(wù)插入到相應(yīng)位置的優(yōu)先級隊列管理方式。根據(jù)遙感衛(wèi)星應(yīng)用系統(tǒng)內(nèi)任務(wù)類別和任務(wù)特性,定義任務(wù)優(yōu)先級別,系統(tǒng)運(yùn)行時創(chuàng)建相應(yīng)數(shù)量的線程安全的隊列,分別存儲相應(yīng)級別的任務(wù)[4]。

任務(wù)的優(yōu)先級由操作員的優(yōu)先級別和任務(wù)類型共同決定。任務(wù)類型分為常規(guī)和應(yīng)急兩類,應(yīng)急任務(wù)的優(yōu)先級高于常規(guī)任務(wù)。其次,操作員的級別越高,任務(wù)的優(yōu)先級越高。根據(jù)業(yè)務(wù)需要,任務(wù)優(yōu)先級的計算算法為

1)假設(shè)常規(guī)任務(wù)的優(yōu)先級權(quán)重為1,應(yīng)急任務(wù)的優(yōu)先級權(quán)重為n;

2)則操作員的優(yōu)先級別分為0～(n-1)級;

3)任務(wù)優(yōu)先級等于操作員優(yōu)先級加任務(wù)種類優(yōu)先級權(quán)重,共1～(2n-1)個級別。

該計算方式可以確保應(yīng)急任務(wù)的優(yōu)先級不低于常規(guī)任務(wù),并且相同類型任務(wù)優(yōu)先級的高低由操作員優(yōu)先級決定。

在制定衛(wèi)星數(shù)據(jù)產(chǎn)品生產(chǎn)任務(wù)時,根據(jù)業(yè)務(wù)需要,確定任務(wù)的優(yōu)先級和任務(wù)在優(yōu)先級隊列中的最長等待時間,任務(wù)生成后按照優(yōu)先級插入到相應(yīng)的優(yōu)先級隊列中,并為任務(wù)增加一個時間戳,記錄該任務(wù)加入到隊列的時間。

任務(wù)的執(zhí)行按優(yōu)先級由高到低的順序執(zhí)行,首先從高優(yōu)先級隊取出任務(wù)執(zhí)行,在高優(yōu)先級隊列為空后,再從下一級優(yōu)先級隊列取任務(wù),以此類推,直至所有優(yōu)先級隊列都為空。

為防止低優(yōu)先級的任務(wù)長時間得不到執(zhí)行,在任務(wù)調(diào)度過程中,檢查非最高優(yōu)先級隊列中每個任務(wù)的等待時間,如果等待時間超過設(shè)定的任務(wù)最長等待時間,而該任務(wù)仍未被執(zhí)行,則將該任務(wù)轉(zhuǎn)移到上一級優(yōu)先級更高的隊列中,并更改時間戳為當(dāng)前加入隊列的時間。

3.2 線程池設(shè)計

由于遙感衛(wèi)星地面應(yīng)用系統(tǒng)的生產(chǎn)和發(fā)布任務(wù)數(shù)量巨大,如果為每一個任務(wù)調(diào)度請求創(chuàng)建單獨(dú)線程,并在任務(wù)完成后銷毀該線程,系統(tǒng)開銷會很大。雖然創(chuàng)建和銷毀一個線程只需耗費(fèi)較少的系統(tǒng)資源,但對于并發(fā)任務(wù)數(shù)特別多的遙感衛(wèi)星地面應(yīng)用,頻繁地創(chuàng)建和銷毀線程會占用大量CPU 時間和內(nèi)存,同時會花費(fèi)大量時間。線程池是一種多線程處理形式,為線程生命周期開銷問題和資源不足問題提供了解決方案,降低了操作系統(tǒng)的負(fù)擔(dān),從而可以獲得更好的調(diào)度性能[5-6]。

線程池的工作流程是先啟動一定數(shù)量的線程,并讓這些線程處于休眠狀態(tài)。當(dāng)有一個新的任務(wù)開始執(zhí)行時,喚醒線程池中的某一個休眠線程處理該任務(wù)的執(zhí)行,任務(wù)執(zhí)行完成后,線程重新轉(zhuǎn)換為休眠狀態(tài)[7]。

本文設(shè)計的線程池能夠根據(jù)任務(wù)數(shù)量動態(tài)地調(diào)整線程池中線程數(shù)量。線程池中的線程分為守護(hù)線程和任務(wù)線程。任務(wù)線程是為系統(tǒng)內(nèi)的任務(wù)調(diào)度執(zhí)行而創(chuàng)建的,負(fù)責(zé)調(diào)度任務(wù)的執(zhí)行線程。守護(hù)線程維護(hù)線程池中任務(wù)線程的數(shù)量和任務(wù)線程狀態(tài)表,記錄和控制任務(wù)線程狀態(tài)的變化。本文的多任務(wù)并行調(diào)度的方法,首先是創(chuàng)建任務(wù)線程和守護(hù)線程,由守護(hù)線程維護(hù)線程池中任務(wù)線程的數(shù)量和任務(wù)線程的狀態(tài)。

1)任務(wù)線程創(chuàng)建

任務(wù)調(diào)度為每一個任務(wù)創(chuàng)建線程。任務(wù)線程數(shù)量是設(shè)計的關(guān)鍵,任務(wù)線程太多或太少都會降低任務(wù)調(diào)度的性能。線程池內(nèi)任務(wù)最大和最小線程數(shù)量根據(jù)系統(tǒng)資源確定。根據(jù)系統(tǒng)CPU 的數(shù)量、任務(wù)的I/O 等待時間和任務(wù)生成頻率等情況,確定任務(wù)線程的最大數(shù)量和最小數(shù)量,并設(shè)置任務(wù)線程的最長空閑時間。

任務(wù)線程的數(shù)量計算算法:假設(shè)任務(wù)的I/O 等待時間為Tw(單位:s),真正占用CPU 的時間為Ts(單位:s),系統(tǒng)CPU 的數(shù)量為N,任務(wù)生成頻率為Fc(單位:個/s),則:

線程池中的任務(wù)線程的最大數(shù)量設(shè)定為

任務(wù)線程的最小數(shù)量設(shè)定為

任務(wù)線程的最長空閑時間設(shè)定為

2)守護(hù)線程創(chuàng)建

線程池創(chuàng)建并啟動唯一的守護(hù)線程,根據(jù)設(shè)定的任務(wù)線程的最小數(shù)量創(chuàng)建任務(wù)線程,并為每個任務(wù)線程分配唯一的ID;將任務(wù)線程的狀態(tài)分為Ready 態(tài)、空閑態(tài)、運(yùn)行態(tài)和終結(jié)態(tài)四種狀態(tài)。任務(wù)線程狀態(tài)轉(zhuǎn)變?nèi)鐖D2 所示:任務(wù)線程創(chuàng)建成功但未啟動時,任務(wù)線程為Ready 態(tài);如果任務(wù)線程開始執(zhí)行任務(wù),則轉(zhuǎn)變?yōu)檫\(yùn)行態(tài);如果優(yōu)先級隊列全部為空,則將任務(wù)線程在空隊列上阻塞,并設(shè)置最長阻塞時間,此時任務(wù)線程轉(zhuǎn)變空閑態(tài);如果任務(wù)線程被守護(hù)線程終止或達(dá)到最長空閑時間, 則轉(zhuǎn)變?yōu)榻K結(jié)態(tài)[8-9]。

圖2 任務(wù)線程狀態(tài)轉(zhuǎn)移示意圖Fig.2 Diagram of task-thread state shifting

3)守護(hù)線程運(yùn)行

線程創(chuàng)建完成后,啟動線程池中所有任務(wù)線程,所有任務(wù)線程變?yōu)檫\(yùn)行態(tài),任務(wù)線程按優(yōu)先級由高到低的順序,從優(yōu)先級隊列中取出任務(wù)進(jìn)行執(zhí)行。守護(hù)線程維護(hù)調(diào)整線程池中任務(wù)線程的數(shù)量和任務(wù)線程狀態(tài)表,記錄和控制任務(wù)線程狀態(tài)的變化,守護(hù)線程執(zhí)行流程如圖3 所示,具體算法如下[10]:

(1)如果有新任務(wù)加入到隊列,而當(dāng)前無處于Ready 態(tài)或空閑態(tài)的任務(wù)線程,并且任務(wù)線程總數(shù)小于設(shè)定的任務(wù)線程最大數(shù)量,則守護(hù)線程負(fù)責(zé)創(chuàng)建新的任務(wù)線程執(zhí)行任務(wù);

(2)如果所有優(yōu)先級隊列為空,即無需要執(zhí)行的任務(wù),任務(wù)線程進(jìn)入空閑狀態(tài),如果處于空閑態(tài)的時間超過設(shè)定的最長空閑時間,則任務(wù)線程自動結(jié)束轉(zhuǎn)變?yōu)榻K結(jié)態(tài);

(3)如果所有優(yōu)先級隊列為空,守護(hù)線程掃描所有的空閑線程,由守護(hù)線程設(shè)置終結(jié)標(biāo)識,結(jié)束處于空閑態(tài)的任務(wù)線程將其轉(zhuǎn)變?yōu)榻K結(jié)態(tài),但守護(hù)線程要保證線程池中任務(wù)線程的數(shù)量不少于設(shè)定的任務(wù)線程的最小數(shù)量。

圖3 守護(hù)線程的流程示意圖Fig.3 Diagram of w atch-thread working flow

4 多任務(wù)并行調(diào)度方法的實現(xiàn)

多任務(wù)并行調(diào)度分為5 部分:任務(wù)制定、任務(wù)管理、生產(chǎn)調(diào)度、流程監(jiān)視和故障處理,如圖4 所示。

1)任務(wù)制定提供任務(wù)錄入的人機(jī)界面,對錄入任務(wù)參數(shù)進(jìn)行檢驗并生成任務(wù);

2)任務(wù)管理負(fù)責(zé)任務(wù)列表顯示、存儲和維護(hù),根據(jù)任務(wù)執(zhí)行結(jié)果,更新任務(wù)狀態(tài);

3)任務(wù)調(diào)度按照任務(wù)類型、所需數(shù)據(jù)、可用數(shù)據(jù)等情況,確定任務(wù)調(diào)度的流程,安排任務(wù)執(zhí)行日程和策略,根據(jù)任務(wù)優(yōu)先級將任務(wù)加入相應(yīng)級別的任務(wù)隊列,由線程池中的任務(wù)線程執(zhí)行任務(wù),生成調(diào)度命令,依次下發(fā)調(diào)度命令給系統(tǒng)內(nèi)的其他分系統(tǒng);

4)流程監(jiān)視監(jiān)測業(yè)務(wù)流程中的各類任務(wù)執(zhí)行狀態(tài)。將任務(wù)執(zhí)行過程以流程結(jié)構(gòu)圖的形式顯示在監(jiān)視界面上,在接收到任務(wù)狀態(tài)數(shù)據(jù)后,能夠通過節(jié)點(diǎn)顏色變化反映節(jié)點(diǎn)狀態(tài)的變化;

圖4 任務(wù)調(diào)度功能組成圖Fig.4 Composition of task scheduling function

5)故障處理模塊:當(dāng)任務(wù)執(zhí)行的節(jié)點(diǎn)出現(xiàn)故障時,根據(jù)故障信息對故障發(fā)生位置信息進(jìn)行定位,并按照該類故障的處理預(yù)案進(jìn)行處理。處理方式包括報警和異常中止控制令下發(fā)。報警方式主要有客戶端的聲光報警,以及服務(wù)端部署的短信報警,短信報警服務(wù)實現(xiàn)了在無人值守的情況下及時報告故障信息的功能。

任務(wù)調(diào)度的任務(wù)管理和流程監(jiān)視的界面如圖5和圖6 所示。

圖5 任務(wù)管理列表Fig.5 List of tasks

圖6 任務(wù)調(diào)度的實時效果Fig.6 Real-time effect of task scheduling

5 結(jié)論

本文提出的基于優(yōu)先級的遙感衛(wèi)星產(chǎn)品生產(chǎn)任務(wù)調(diào)度方法,根據(jù)任務(wù)優(yōu)先級順序調(diào)度任務(wù)執(zhí)行,解決了任務(wù)處理流程復(fù)雜、任務(wù)量大、并行處理要求高等帶來的調(diào)度問題,能同時調(diào)度的任務(wù)數(shù)量大大增加,滿足了任務(wù)調(diào)度的實時性、并行性和高效率的需求。目前該技術(shù)已經(jīng)在某遙感衛(wèi)星應(yīng)用系統(tǒng)得到應(yīng)用,實踐檢驗效果良好,在Window s Server 2008 操作系統(tǒng),4 路4 核主頻2.4G Hz 的CPU,32Gbyte 內(nèi)存的運(yùn)行環(huán)境下,該調(diào)度方法同時能夠調(diào)度的任務(wù)數(shù)量可以達(dá)到2 000 個;此外,由于采用多優(yōu)先級隊列的方式,在任務(wù)量增加時,低優(yōu)先級任務(wù)的延遲時間平均比單優(yōu)先級隊列減少20s 左右。該方法提高了遙感衛(wèi)星數(shù)據(jù)產(chǎn)品的生產(chǎn)效率,能夠應(yīng)對突發(fā)事件快速調(diào)度產(chǎn)品生產(chǎn),相應(yīng)地提高了衛(wèi)星地面應(yīng)用系統(tǒng)的經(jīng)濟(jì)效益和社會效益。

)

[1]吳美蓉.中巴地球資源衛(wèi)星應(yīng)用系統(tǒng)及其數(shù)據(jù)處理系統(tǒng)[C]// 臺灣臺北:2001年海峽兩岸空間資訊與防災(zāi)科技研討會,2001

[2]周海鶯, 祝春萌,黃錦淵.風(fēng)云三號衛(wèi)星廣州地面數(shù)據(jù)接收處理系統(tǒng)設(shè)計[C]//北京:中國氣象學(xué)會2008年會, 2008

[3]劉殿興, 杜忠華.一種新型的多優(yōu)先級隊列緩存管理算法[C]//沈陽:遼寧省通信學(xué)會2005年年會,2005

[4]田杭沛,高德遠(yuǎn), 樊曉椏,等.面向?qū)崟r流處理的多核多線程處理器訪存隊列[J].計算機(jī)研究與發(fā)展, 2009, 46(10)

[5]孫凌.基于Java 多線程的任務(wù)調(diào)度實現(xiàn)策略[J].計算機(jī)工程,2004, 30(z1)

[6]王菁,魏霞.Java 語言多線程技術(shù)及應(yīng)用探討[J].農(nóng)業(yè)網(wǎng)絡(luò)信息,2009(5)

[7]胡寧,張德運(yùn),史宏鋒.一種低開銷的多任務(wù)調(diào)度模型[J].微電子學(xué)與計算機(jī), 2005,22(4)

[8]劉瑞敏,張云生.實時多任務(wù)調(diào)度程序設(shè)計[C]//昆明:第三屆工業(yè)控制系統(tǒng)應(yīng)用學(xué)術(shù)會議, 1997

[9]黃寶邊,曾文華.網(wǎng)格環(huán)境中任務(wù)調(diào)度算法的分析與比較[C]// 武漢:2005 中國計算機(jī)大會, 2005

[10]黃金貴, 康寶生.并行任務(wù)調(diào)度的近似算法[C]// 青島:第一屆全國幾何設(shè)計與計算學(xué)術(shù)會議,2002