嵌入式突發任務調度方法研究與仿真

李青云，康晶晶，郭文鋒

(1.晉中信息學院信息工程學院，山西 晉中 030800；2.山西農業大學，山西 太谷 030801)

1 引言

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

2 基于Forth虛擬機技術的嵌入式突發任務調度仿真

2.1 嵌入式突發任務調度框架

Forth虛擬機又稱FVM，利用虛擬機構搭建嵌入式突發任務調度框架，將其嵌入計算機內可實現終端任務和使用者之間的交互功能[5]，嵌入式框架結構如圖1所示。

圖1 嵌入式突發任務調度框架結構示意圖

嵌入式框架由任務控制塊、RAM、FLASH任務字典和FVM(虛擬機)等組成，由RAM模塊和FLASH任務字典模塊互相協作形成突發任務，經過任務控制塊內的R/D堆棧轉換后，FVM虛擬機采用時間輪轉算法完成突發任務調度需求。

2.2 任務控制塊

任務控制塊(task Control Block)又稱TCB，是由突發任務調度信息的用戶變量構成的，負責存儲突發任務，任務控制塊內各個任務數據棧指針變量所占空間不重疊[6]，任務控制塊結構如表1所示。

表1 任務控制塊結構

表1中，每個任務控制塊結構均使用2個內存單元，使用者可依據實際需求增減任務控制塊結構，上表內所有結構均為終端任務所需，無需I/O設備連接，其中，突發調度任務最常用的為status、follower、rp0、sp0以及sp等。

2.3 后臺任務映像及突發任務建立

任務控制塊與任務R/D堆棧形成任務映像，任務映像可連續存儲于內存中，嵌入式突發任務調度框架所建立的突發任務映像通過詞語的形式存儲在RAM模塊內，通過詞語的參數域形成任務信息塊，任務映像組成如圖2所示。

圖2 后臺任務映像組成示意圖

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

在嵌入式突發任務調度時，針對需要調度的任務，在FLASH任務字典內創建任務名詞，利用靜態分配方式將該任務名詞分配到任務控制塊內并記錄該任務名詞的參數域初始地址，一個新任務的建立需經過創建、初始化等步驟，當新任務建立完成后，將該任務添加到需調度隊列內，等待調度[8]。

2.4 基于時間輪轉的負載均衡調度算法

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

時間輪轉算法依據進程情況判定優先級，屬于靜態優先級調度方法，在突發任務調度過程中，優先級先進行調度，且優先級無法調整，因此，需將嵌入式突發任務調度框架的負載均衡性作為調度優先級，再使用時間輪轉方法實現突發任務調度。

2.4.1 嵌入式突發任務調度框架負載均衡優先級判斷

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

(1)

(2)

上述公式中，Cij表示將i任務調度到節點j時嵌入式突發任務調度框架的負載均衡數值，當負載均衡數值為0時，表示此時的任務調度框架負載均衡為最佳狀態，負載均衡數值區間為0～1，因此其最大數值為1，負載均衡數值越大表明任務調度框架負載均衡狀態越差。通過該公式計算待調度任務優先級，負載均衡數值越小，其調度優先級越高，依據優先級排列后，使用時間輪轉方法進行調度。

2.4.2 時間輪轉調度算法

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

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

第二步：計算就緒隊列最高優先級，且該優先級不為空，令當前隊列等待時間為0。

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

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

3 實驗分析

使用NANDFlash燒寫器將本文嵌入式突發任務調度框架燒寫在型號為ARM1176JZF-S嵌入式開發板內，該開發板控制器參數為Atmega328P，工作電壓為5V，FLASH容量為32kB，時鐘為16MHz，使用MATLAB仿真軟件對本文方法展開測試。

3.1 負載均衡分配測試

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

圖3 負載均衡分配測試結果

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

3.2 突發任務調度流暢性測試

通過建立突發任務和刪除突發任務方式，計算其內存占用情況，以內存占用率衡量本文方法突發任務調度流暢性，結果如表2所示。

表2 突發任務調度流暢性測試結果

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

3.3 穩定性測試

令所有突發任務堆棧大小相同，且所有可用空間均被完全利用，當刪除10個任務時，統計本文方法任務調度最大數值，為更清晰明了地展示本文方法穩定性，同時使用文獻[3]方法和文獻[4]方法，其中，文獻[3]方法表示云任務調度方法，文獻[4]方法表示價值優化的任務調度算法，穩定性測試結果如表3所示。

表3 穩定性測試結果

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

3.4 突發任務調度效率測試

利用仿真軟件模擬突發任務350個，分別使用三種方法進行任務調度，測試其突發任務調度效率，結果如圖4所示。

圖4 突發任務調度效率測試

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

4 結論

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