嵌入式突發(fā)任務(wù)調(diào)度方法研究與仿真

李青云，康晶晶，郭文鋒

(1.晉中信息學(xué)院信息工程學(xué)院，山西 晉中 030800；2.山西農(nóng)業(yè)大學(xué)，山西 太谷 030801)

1 引言

具備所有硬件功能可運行在特定空間內(nèi)的計算機系統(tǒng)稱為虛擬機，其具備實體計算機所有功能，通過特定CMOS和硬盤等實現(xiàn)用戶需求[1]。虛擬機技術(shù)屬于虛擬化技術(shù)的一個分支，利用虛擬機技術(shù)可轉(zhuǎn)變事務(wù)形式，依據(jù)用戶意愿將硬盤轉(zhuǎn)換為內(nèi)存，將公共網(wǎng)絡(luò)劃分出一部分作為用戶私有網(wǎng)絡(luò)。目前，嵌入式應(yīng)用被越來越多的領(lǐng)域所需求，面對日新月異的科學(xué)技術(shù)，基于Forth虛擬機技術(shù)的嵌入式應(yīng)用應(yīng)運而生[2]，尤其是在任務(wù)調(diào)度方面，應(yīng)用較為廣泛。而任務(wù)調(diào)度方法眾多，其中以李昆侖等人研究的云任務(wù)調(diào)度方法[3]和楊善超等人研究的價值優(yōu)化的任務(wù)調(diào)度算法[4]最為優(yōu)秀，前者依據(jù)用戶滿意度，利用尋優(yōu)算法實現(xiàn)任務(wù)調(diào)度，但是該方法具有較強的主觀性，且尋優(yōu)算法迭代次數(shù)眾多，調(diào)度流暢性不佳，導(dǎo)致其調(diào)度效果不理想，后者依據(jù)待調(diào)度任務(wù)的最大價值和變動斜率構(gòu)建價值函數(shù)實現(xiàn)任務(wù)調(diào)度，但該方法時間偏移量較大，導(dǎo)致計算的價值概率不夠準確，負載均衡效果較差。面對上述情況，本文研究基于Forth虛擬機技術(shù)的嵌入式突發(fā)任務(wù)調(diào)度仿真，以提升突發(fā)任務(wù)調(diào)度技術(shù)水平。

2 基于Forth虛擬機技術(shù)的嵌入式突發(fā)任務(wù)調(diào)度仿真

2.1 嵌入式突發(fā)任務(wù)調(diào)度框架

Forth虛擬機又稱FVM，利用虛擬機構(gòu)搭建嵌入式突發(fā)任務(wù)調(diào)度框架，將其嵌入計算機內(nèi)可實現(xiàn)終端任務(wù)和使用者之間的交互功能[5]，嵌入式框架結(jié)構(gòu)如圖1所示。

圖1 嵌入式突發(fā)任務(wù)調(diào)度框架結(jié)構(gòu)示意圖

嵌入式框架由任務(wù)控制塊、RAM、FLASH任務(wù)字典和FVM(虛擬機)等組成，由RAM模塊和FLASH任務(wù)字典模塊互相協(xié)作形成突發(fā)任務(wù)，經(jīng)過任務(wù)控制塊內(nèi)的R/D堆棧轉(zhuǎn)換后，F(xiàn)VM虛擬機采用時間輪轉(zhuǎn)算法完成突發(fā)任務(wù)調(diào)度需求。

2.2 任務(wù)控制塊

任務(wù)控制塊(task Control Block)又稱TCB，是由突發(fā)任務(wù)調(diào)度信息的用戶變量構(gòu)成的，負責(zé)存儲突發(fā)任務(wù)，任務(wù)控制塊內(nèi)各個任務(wù)數(shù)據(jù)棧指針變量所占空間不重疊[6]，任務(wù)控制塊結(jié)構(gòu)如表1所示。

表1 任務(wù)控制塊結(jié)構(gòu)

表1中，每個任務(wù)控制塊結(jié)構(gòu)均使用2個內(nèi)存單元，使用者可依據(jù)實際需求增減任務(wù)控制塊結(jié)構(gòu)，上表內(nèi)所有結(jié)構(gòu)均為終端任務(wù)所需，無需I/O設(shè)備連接，其中，突發(fā)調(diào)度任務(wù)最常用的為status、follower、rp0、sp0以及sp等。

2.3 后臺任務(wù)映像及突發(fā)任務(wù)建立

任務(wù)控制塊與任務(wù)R/D堆棧形成任務(wù)映像，任務(wù)映像可連續(xù)存儲于內(nèi)存中，嵌入式突發(fā)任務(wù)調(diào)度框架所建立的突發(fā)任務(wù)映像通過詞語的形式存儲在RAM模塊內(nèi)，通過詞語的參數(shù)域形成任務(wù)信息塊，任務(wù)映像組成如圖2所示。

圖2 后臺任務(wù)映像組成示意圖

使用者指針位置即為當(dāng)前任務(wù)映像首地址，各個任務(wù)之間互相獨立，通過相對偏移編址、數(shù)據(jù)堆棧等組成任務(wù)堆棧，任務(wù)堆棧依次形成，各個任務(wù)之間存儲獨立，不互相影響[7]。

在嵌入式突發(fā)任務(wù)調(diào)度時，針對需要調(diào)度的任務(wù)，在FLASH任務(wù)字典內(nèi)創(chuàng)建任務(wù)名詞，利用靜態(tài)分配方式將該任務(wù)名詞分配到任務(wù)控制塊內(nèi)并記錄該任務(wù)名詞的參數(shù)域初始地址，一個新任務(wù)的建立需經(jīng)過創(chuàng)建、初始化等步驟，當(dāng)新任務(wù)建立完成后，將該任務(wù)添加到需調(diào)度隊列內(nèi)，等待調(diào)度[8]。

2.4 基于時間輪轉(zhuǎn)的負載均衡調(diào)度算法

嵌入式突發(fā)任務(wù)調(diào)度時需保證其分配性能與效率，為使其調(diào)度吞吐量達到最大和任務(wù)資源使用最大化，嵌入式突發(fā)任務(wù)調(diào)度框架的負載均衡達到最佳狀態(tài)是其必要途徑。本文利用時間輪轉(zhuǎn)算法，將虛擬機調(diào)度任務(wù)時間劃分為獨立時間片，依據(jù)時間距離對獨立時間片進行排序，按照次序使用虛擬機處理器資源，完成后退出并按照退出次序排列，等待下一次調(diào)度，時間片使用虛擬機處理器的過程稱為進程[9]，進程調(diào)度順序也依據(jù)時間排序，當(dāng)某個進程使用虛擬機處理器時，僅占用一個時間片，該時間片使用完成后，該進程結(jié)束。

時間輪轉(zhuǎn)算法依據(jù)進程情況判定優(yōu)先級，屬于靜態(tài)優(yōu)先級調(diào)度方法，在突發(fā)任務(wù)調(diào)度過程中，優(yōu)先級先進行調(diào)度，且優(yōu)先級無法調(diào)整，因此，需將嵌入式突發(fā)任務(wù)調(diào)度框架的負載均衡性作為調(diào)度優(yōu)先級，再使用時間輪轉(zhuǎn)方法實現(xiàn)突發(fā)任務(wù)調(diào)度。

2.4.1 嵌入式突發(fā)任務(wù)調(diào)度框架負載均衡優(yōu)先級判斷

以判斷負載均衡優(yōu)先級的方式實現(xiàn)負載均衡分配，在判斷嵌入式突發(fā)任務(wù)調(diào)度框架負載均衡優(yōu)先級時，令C表示負載均衡度，參數(shù)和計算節(jié)點數(shù)量分別為n和m，則在n維參數(shù)空間內(nèi)，計算節(jié)點投影中間位置為O(y1，y2，…，yn)，則節(jié)點映射到中心距離均值表達公式如下

(1)

(2)

上述公式中，Cij表示將i任務(wù)調(diào)度到節(jié)點j時嵌入式突發(fā)任務(wù)調(diào)度框架的負載均衡數(shù)值，當(dāng)負載均衡數(shù)值為0時，表示此時的任務(wù)調(diào)度框架負載均衡為最佳狀態(tài)，負載均衡數(shù)值區(qū)間為0～1，因此其最大數(shù)值為1，負載均衡數(shù)值越大表明任務(wù)調(diào)度框架負載均衡狀態(tài)越差。通過該公式計算待調(diào)度任務(wù)優(yōu)先級，負載均衡數(shù)值越小，其調(diào)度優(yōu)先級越高，依據(jù)優(yōu)先級排列后，使用時間輪轉(zhuǎn)方法進行調(diào)度。

2.4.2 時間輪轉(zhuǎn)調(diào)度算法

將上個小節(jié)獲取的待調(diào)度任務(wù)優(yōu)先級排序后的數(shù)據(jù)分為兩個就緒隊列，分別用AQi0和AQi1表示，令BTk表示進程時限，BTavg表示所有進程剩余時限平均數(shù)值，當(dāng)進程時限小于剩余時限平均數(shù)值時，將該進程放置就緒隊列AQi1末尾，反之放置于就緒隊列AQi0末尾，時間輪轉(zhuǎn)算法在調(diào)度過程中，依據(jù)最高優(yōu)先級對該就緒隊列展開調(diào)度，當(dāng)該進程為空時，更換下一個就緒隊列。令N、E分別表示進程數(shù)量和剩余進程總和，ut為當(dāng)前隊列等待時間，時間輪轉(zhuǎn)調(diào)度算法具體步驟如下

第一步：計算優(yōu)先級為j的節(jié)點的進程時限，當(dāng)時限小于剩余平均時限時，將該進程放置就緒隊列AQi1末尾，反之放置在就緒隊列AQi0末尾，更新進程數(shù)量、剩余進程數(shù)量總和、有進程剩余時限平均數(shù)值。

第二步：計算就緒隊列最高優(yōu)先級，且該優(yōu)先級不為空，令當(dāng)前隊列等待時間為0。

第三步：當(dāng)就緒隊列為AQi1空時，令TQ=max(g，BTavg)表示該隊列的第一個進程時間片，當(dāng)全部進程剩余時限BT在其自身時間片內(nèi)完成時，更新剩余進程總和與有進程剩余時限平均數(shù)值，并將該進程在屬于其就緒隊列內(nèi)剔除，放置另一就緒隊列末尾，再次更新剩余進程總和與有進程剩余時限平均數(shù)值后，令當(dāng)前隊列等待時間為進程調(diào)度時間和隊列等待時間之和，當(dāng)任務(wù)i調(diào)度時間高于所有進程剩余時限平均數(shù)值的2倍，將該進程放置在AQi1的末尾，此時ut數(shù)值為0，反之則更新剩余進程總和與有進程剩余時限平均數(shù)值，將該進程放置于在AQi0的末尾，再次更新剩余進程總和與有進程剩余時限平均數(shù)值。

通過上述步驟，進程時間片始終在變化，在調(diào)度任意進程時，該進程的時間片即為當(dāng)前所有進程剩余時限平均數(shù)值。當(dāng)任意進程的時間片消耗盡后，其調(diào)度運行時間未停止時，將該進程放置于就緒隊列AQi0末尾，等待下一次調(diào)度，在全部優(yōu)先級內(nèi)引入等待時間E，利用等待時間對就緒隊列內(nèi)調(diào)度耗時過長的進程展開追蹤，當(dāng)?shù)却龝r間超出BTavg的兩倍時，將該進程添加至另一就緒隊列最先調(diào)度，從而完成突發(fā)任務(wù)調(diào)度過程。

3 實驗分析

使用NANDFlash燒寫器將本文嵌入式突發(fā)任務(wù)調(diào)度框架燒寫在型號為ARM1176JZF-S嵌入式開發(fā)板內(nèi)，該開發(fā)板控制器參數(shù)為Atmega328P，工作電壓為5V，F(xiàn)LASH容量為32kB，時鐘為16MHz，使用MATLAB仿真軟件對本文方法展開測試。

3.1 負載均衡分配測試

本文方法在調(diào)度突發(fā)任務(wù)時，需判斷負載均衡優(yōu)先級，并依據(jù)優(yōu)先級實現(xiàn)負載均衡分配，以突發(fā)任務(wù)就緒隊列變化情況和任務(wù)初始地址衡量本文負載均衡分配情況，創(chuàng)建3組待調(diào)度突發(fā)任務(wù)，分別標記為任務(wù)一、任務(wù)二、任務(wù)三，利用MATLAB仿真軟件繪制測試走勢圖，結(jié)果如圖3所示。

圖3 負載均衡分配測試結(jié)果

分析圖3可知，三個任務(wù)的AQi0、AQi1數(shù)值不同，其原因在于本文方法在分配負載均衡過程中，優(yōu)先級較高的任務(wù)先被調(diào)整的結(jié)果，而任務(wù)的初始地址與AQi0數(shù)值相同，且AQi1數(shù)值不斷增加，表明本文方法負載均衡分配較合理。

3.2 突發(fā)任務(wù)調(diào)度流暢性測試

通過建立突發(fā)任務(wù)和刪除突發(fā)任務(wù)方式，計算其內(nèi)存占用情況，以內(nèi)存占用率衡量本文方法突發(fā)任務(wù)調(diào)度流暢性，結(jié)果如表2所示。

表2 突發(fā)任務(wù)調(diào)度流暢性測試結(jié)果

分析表2可知，在建立任務(wù)時內(nèi)存占用率逐漸上升，當(dāng)所建立的任務(wù)占用空間數(shù)值較大時，其內(nèi)存占用率上升幅度也較大，同理刪除某個任務(wù)后其內(nèi)存占用率有所下降，且該任務(wù)占用空間數(shù)值較大，其內(nèi)存占用率下降幅度也較大，且內(nèi)存占用率最高僅為30.2%，由此可知，本文方法在調(diào)度突發(fā)任務(wù)過程中具備較強的流暢性。

3.3 穩(wěn)定性測試

令所有突發(fā)任務(wù)堆棧大小相同，且所有可用空間均被完全利用，當(dāng)刪除10個任務(wù)時，統(tǒng)計本文方法任務(wù)調(diào)度最大數(shù)值，為更清晰明了地展示本文方法穩(wěn)定性，同時使用文獻[3]方法和文獻[4]方法，其中，文獻[3]方法表示云任務(wù)調(diào)度方法，文獻[4]方法表示價值優(yōu)化的任務(wù)調(diào)度算法，穩(wěn)定性測試結(jié)果如表3所示。

表3 穩(wěn)定性測試結(jié)果

分析表3可知，當(dāng)獨立任務(wù)占用空間相同時，在無任務(wù)刪除的情況下，三種方法的最大調(diào)度任務(wù)數(shù)量均為55個，當(dāng)刪除10個任務(wù)后，本文方法最大調(diào)度任務(wù)數(shù)量為65個，較文獻[3]方法和文獻[4]方法分別高出10個和3個任務(wù)數(shù)，由此可知，本文方法可在調(diào)度任務(wù)過程中不受任務(wù)建立、刪除等操作影響，具有較強穩(wěn)定性。

3.4 突發(fā)任務(wù)調(diào)度效率測試

利用仿真軟件模擬突發(fā)任務(wù)350個，分別使用三種方法進行任務(wù)調(diào)度，測試其突發(fā)任務(wù)調(diào)度效率，結(jié)果如圖4所示。

圖4 突發(fā)任務(wù)調(diào)度效率測試

分析圖4可知，隨著突發(fā)任務(wù)數(shù)量的增加，三種方法調(diào)度耗時也隨之增加，其中文獻[3]方法和文獻[4]方法隨著突發(fā)任務(wù)數(shù)量的增加其調(diào)度耗時迅速增加，當(dāng)突發(fā)任務(wù)數(shù)量為350個時，二者調(diào)度任務(wù)耗時均超過14s，反觀本文方法，其調(diào)度耗時增加緩慢，突發(fā)任務(wù)數(shù)為350個時，該方法較文獻[3]方法和文獻[4]方法調(diào)度耗時低，在測試中，本文方法最低調(diào)度耗時僅為2s，由此可知，本文方法突發(fā)任務(wù)調(diào)度效率較高。

4 結(jié)論

本文利用Forth虛擬機技術(shù)進行嵌入式突發(fā)任務(wù)調(diào)度，并仿真基于Forth虛擬機技術(shù)的嵌入式突發(fā)任務(wù)調(diào)度情況，實驗結(jié)果表明：本文方法負載均衡分配較為合理；在調(diào)度流暢性方面其內(nèi)存占用率最高僅為30.2%，具有較高調(diào)度流暢性；在調(diào)度任務(wù)過程中不受任務(wù)建立、刪除等操作影響，具有較強穩(wěn)定性。