基于Forth虛擬機的嵌入式多核任務調(diào)度研究

任鳳琴 ，張俊生，程耀瑜

(1.太原學院計算機科學與技術系，山西 太原 030032；2.太原工業(yè)學院電子工程系，山西 太原，030008；3.中北大學信息與通信工程學院，山西 太原，030051)

1 引言

雖然嵌入式系統(tǒng)性能已經(jīng)足夠強大了，但在其研究領域中仍然存在許多無法預測的問題，人們希望能夠在特殊情況下，使用可以進行拓展且在線維護的多任務操作系統(tǒng)對程序進行修改。針對嵌入式系統(tǒng)的復雜需求，對基于Forth虛擬機的嵌入式多任務操作系統(tǒng)進行研究，完成協(xié)同式的多核任務調(diào)度非常有必要。Forth語言具有極強的擴展性與交互性，可以非常迅速地構(gòu)建出完整的多核任務操作系統(tǒng)[1]。

大量學者針對多核任務算法進行研究，并取得了不錯的研究成果。文獻[2]對LLF調(diào)度算法采取一定的優(yōu)化措施，避免ED算法產(chǎn)生的Dhall效應，同時減少任務上下文切換次數(shù)的計算量，實驗結(jié)果表明該算法能夠在有限時間內(nèi)完成盡可能多的任務調(diào)度。文獻[3]為了實現(xiàn)代碼的共享以及多任務可協(xié)同管理的功能，采用分類的方式進行映射存儲，將Forth向量定義與用戶變量進行分離，實驗結(jié)果表明，改方法在發(fā)揮Forth系統(tǒng)特性的同時，不僅減少了系統(tǒng)所占用的空間，還提高了系統(tǒng)的運行效率，但該方法的實時性還需要進一步提高。文獻[4]通過新提出的終端任務類型對突發(fā)事件進行處理，并通過新的調(diào)度算法調(diào)度Forth系統(tǒng)中的任務，實驗結(jié)果表明該算法較適用于具有實時要求的嵌入式系統(tǒng)。

在現(xiàn)有研究的基礎上，本文重新創(chuàng)建了中斷任務的處理機制，將中斷任務的TCB根據(jù)后臺任務的TCB模式進行設計，提高多核任務調(diào)度過程中突發(fā)事件的處理能力。

2 基于Forth系統(tǒng)多任務調(diào)度機制

在計算機操作過程中，為了降低系統(tǒng)與環(huán)境間的相關性，通過對計算機運行環(huán)境進行模擬，這種環(huán)境被稱作虛擬機[5-6]。FVM是一種介于裸機與程序間的軟件系統(tǒng)，它由Forth語言編寫，F(xiàn)VM與傳統(tǒng)的虛擬機比具有較強的擴展性，移植與構(gòu)建起來更加便捷、快速。Forth系統(tǒng)引入多任務的概念，對于多個任務系統(tǒng)可循環(huán)使用CPU資源，達到多任務“同時”處理的效果，提高用戶體驗。若要完成多任務的運行，F(xiàn)orth操作系統(tǒng)需要把任務調(diào)度到內(nèi)存中，F(xiàn)orth系統(tǒng)內(nèi)存布局如圖1所示。

圖1 Forth系統(tǒng)內(nèi)存布局

Forth啟動時，存儲的預編譯Forth部分會自動加載到低地址區(qū)，系統(tǒng)變量中產(chǎn)生的數(shù)據(jù)變量可供除了用戶外的整個系統(tǒng)使用。為了節(jié)省空間，任選定義區(qū)存放著以源文本形式存放在磁盤區(qū)的地址。用戶區(qū)的大小由任務的類型決定，是用來存放任務的內(nèi)存區(qū)。塊緩沖區(qū)是每次對磁盤塊訪問時，都將磁盤塊復制到該區(qū)，并對程序進行處理的緩沖區(qū)。

基于Forth系統(tǒng)采用輪詢調(diào)度機制，若函數(shù)或子程序占用CPU，則會讓該函數(shù)或子程序繼續(xù)執(zhí)行，否則跳過該函數(shù)或子程序執(zhí)行下一個函數(shù)或子程序，從而完成對CPU的依次有序循環(huán)占用[7]。Forth系統(tǒng)中的每個任務均可簡化為一個Forth字，類似于函數(shù)或子程序，F(xiàn)orth系統(tǒng)中任務輪詢調(diào)度如圖2所示。

圖2 輪詢調(diào)度

在多任務調(diào)度過程中，當任務執(zhí)行完一個Forth字后，若遇到任務調(diào)度原語時，系統(tǒng)會將任務的執(zhí)行信息進行保存，進而去執(zhí)行下一個任務，直到所有任務執(zhí)行完畢，返回到任務循環(huán)檢測狀態(tài)。由于任務調(diào)度原語具有暫停當前任務的作用，因此可以采用在適當?shù)臅r間嵌入任務調(diào)度原語的方法，使所有任務都具有可運行的機會。

3 基于Forth系統(tǒng)多核任務調(diào)度

3.1 Forth系統(tǒng)突發(fā)事件處理

很多操作系統(tǒng)都會面臨突發(fā)事件，從而發(fā)出請求占用CPU的情況，同時這些突發(fā)事件需要在很短時間內(nèi)被處理完成，但Forth系統(tǒng)并沒有面對突發(fā)事件的處理機制。Forth系統(tǒng)采用輪詢調(diào)度機制，在正常運行時，對于任何突發(fā)事件的請求都不會給予反應。若要對Forth系統(tǒng)的突發(fā)事件進行處理，只能等待所有任務運行完畢后，在系統(tǒng)返回終端任務時將突發(fā)任務加入到任務鏈中，使系統(tǒng)重新構(gòu)建任務鏈，完成突發(fā)任務的處理，F(xiàn)orth系統(tǒng)突發(fā)事件處理過程如圖3所示。

圖3 Forth系統(tǒng)突發(fā)事件處理過程

由于Forth系統(tǒng)無法對突發(fā)事件做出及時的響應，導致突發(fā)事件處理的時間較長，大大降低了系統(tǒng)的處理效率。針對該問題，本文提出了一種新的中斷任務處理方法，當突發(fā)事件向請求占用CPU時，系統(tǒng)會根據(jù)其發(fā)出的觸發(fā)中斷信號，置位相應的中斷標志，同時跳轉(zhuǎn)至中斷處，實現(xiàn)突發(fā)事件的快速響應。該機制不僅可以保證Forth系統(tǒng)調(diào)度的穩(wěn)定運行，還可以增加系統(tǒng)對突發(fā)事件的處理能力。中斷任務處理機制執(zhí)行的過程可描述為：

1)將中斷程序的代碼地址載入到中斷向量表中，并對中斷向量表初始化，將中斷狀態(tài)設為允許狀態(tài)，若系統(tǒng)檢測出中斷信號便做出響應。

2)創(chuàng)建完中斷任務后，需對中斷任務的TCB初始化，并把用戶變量設置為pass狀態(tài)，使中斷任務參與到任務隊列中。

3)在響應過程中，將系統(tǒng)置于關中斷狀態(tài)，當突發(fā)事件將中斷任務響應成喚醒狀態(tài)時，突發(fā)事件便會得到及時地處理。

4)中斷任務處理完畢后，將其設置為睡眠狀態(tài)，直到遇到突發(fā)事件，再次被喚醒。中斷響應過程如圖4所示。

圖4 中斷響應過程

3.2 多核任務調(diào)度算法

為了提高任務調(diào)度的效率，中斷任務的TCB可根據(jù)后臺任務的TCB模式進行設計。中斷任務的TCB用兩個存儲單元保留一條用戶信息，TCB中主要存儲中斷任務的狀態(tài)信息、下一個任務的地址信息、中斷任務返回的堆棧起始地址和數(shù)據(jù)堆棧的起始地址、數(shù)據(jù)堆棧的棧頂?shù)刂?，中斷任務TCB如圖5所示。

圖5 中斷任務TCB

對于中斷事件的處理，需要創(chuàng)建中斷任務，中斷任務的創(chuàng)建采用Forth2012[8]標準對存儲空間進行分配，并生成詞典字。中斷任務的創(chuàng)建過程為：一、文本解釋程序獲取，作為分配數(shù)據(jù)堆棧空間、預留區(qū)域空間大小的十進制數(shù)據(jù)，并將十進制數(shù)據(jù)存放到當前的任務堆棧中。二、當執(zhí)行到“create”時，系統(tǒng)以字典指針作為依據(jù)，按照地址遞增的方式為中斷任務分配存儲空間，生成名字域(存放中斷任務名的字符串)和鏈接域(存放最后一個Forth字的入口地址)的詞典條目。三、通過“here”變量指向中斷任務控制塊TCB的起始地址，利用“，”變量將該地址進行保存，并作為任務控制塊的入口地址。四、通過“&12+allot”操作，為任務控制塊TCB分配12個記錄任務信息的存儲空間。五、通過“allot”變量將數(shù)據(jù)堆棧中的十進制數(shù)據(jù)取出，并分別取出數(shù)據(jù)個大小的存儲單元作為中斷任務返回堆棧區(qū)域。六、通過Forth字“，”對棧底地址進行保存，完成數(shù)據(jù)堆棧的分配。

中斷任務的創(chuàng)建和存儲空間的分配完成后，需要進一步創(chuàng)建中斷服務程序來建立中斷響應機制。中斷服務程序的算法描述如下：

當系統(tǒng)執(zhí)行完第5行的操作后，便獲得了中斷任務的程序入口地址，然后執(zhí)行第6行的操作對中斷任務進行喚醒，中斷任務喚醒程序的算法如下：

通過Wake-INT-Task的定義，把中斷任務的置為wake，使中斷任務處于喚醒狀態(tài)。系統(tǒng)運行過程中，當有中斷事件加入時，系統(tǒng)會執(zhí)行到任務最近的原語pause，然后開始執(zhí)行中斷任務。中斷任務程序運行完畢后，F(xiàn)orth系統(tǒng)會對當前的任務繼續(xù)執(zhí)行，直到運行到原語pause時，系統(tǒng)才會尋找下一任務的TCB首地址。再次獲取任務TCB中的狀態(tài)值是否為wake狀態(tài)，若為wake狀態(tài)，則CPU運行該任務；若為pass狀態(tài)，則繼續(xù)尋找下一個任務的TCB首地址，直到所有任務都執(zhí)行完畢。

4 實驗評估

基于Forth虛擬機架構(gòu)的嵌入式多核任務調(diào)度是否可以很好的執(zhí)行以及該方法是否有效，本文通過實驗進行驗證，實驗的硬件環(huán)境與軟件環(huán)境如表1所描述。測試程序采用終端任務、后臺任務和中斷任務三種任務類型的多核任務來完成，為了方便驗證，分別在終端任務和后臺任務處設置兩處原語pause，中斷發(fā)生區(qū)如圖6所示。

表1 環(huán)境配置

圖6 中斷發(fā)生區(qū)

當終端任務與后臺任務執(zhí)行時，有三個區(qū)域(one區(qū)、two區(qū)、three區(qū))可發(fā)生中斷請求。測試程序針對每個區(qū)域設置10個中斷觸發(fā)點，驗證中斷觸發(fā)后，系統(tǒng)對突發(fā)事件的響應情況。在多核任務調(diào)度系統(tǒng)中，系統(tǒng)的響應時間可表示為：

(1)

其中，Ttask＿k表示各個任務的完成時間；Tswi表示各個任務的切換時間；N表示同時發(fā)生的任務個數(shù)。如果采用優(yōu)先級算法，那么用公式可表示為：

(2)

其中，Ttask＿min表示各個任務完成時間的最小值；α表示比例因子；Ptask＿k表示任務優(yōu)先級。將本文算法分別與文獻[2]、文獻[3]和文獻[4]進行對比，驗證系統(tǒng)的響應時間，實驗結(jié)果如圖7所示。

圖7 系統(tǒng)響應時間對比結(jié)果

從圖中可以看出，文獻[2]的響應時間隨著任務數(shù)的增多，呈指數(shù)形式增長；文獻[3]的響應時間呈直線式增長狀態(tài)；文獻[4]的響應時間與任務數(shù)量也近似于線性增長。然而本文的調(diào)度算法，即使任務數(shù)不斷地增加，任務切換與在線交互時間都沒有明顯的延遲，系統(tǒng)的響應時間幾乎不受任務數(shù)量影響，始終保持較快的響應速度。不僅如此，本文方法的各個任務完成時間均可由用戶自行定義。對one區(qū)的程序設置10個中斷觸發(fā)點，程序代碼如下：

Two區(qū)與three區(qū)的中斷觸發(fā)代碼與one區(qū)類似，在原系統(tǒng)與改進后的系統(tǒng)中，分別對這三個區(qū)的10個中斷點進行測試，測試結(jié)果分別如圖8、9、10所示。

圖8 one區(qū)突發(fā)事件對比結(jié)果

圖9 two區(qū)突發(fā)事件對比結(jié)果

圖10 three區(qū)突發(fā)事件對比結(jié)果

從圖中可以看出，采用本文改進的Forth虛擬機操作系統(tǒng)后，one區(qū)、two區(qū)和three區(qū)突發(fā)事件的等待時間明顯降低了。后臺任務two區(qū)和three區(qū)的第10個中斷點的中斷任務等待時間均小于2ms，這恰巧是后臺任務運行到原語pause時，發(fā)生了中斷的結(jié)果。綜上所述，說明采用本文改進后的多核任務調(diào)度系統(tǒng)具有良好的可行性與有效性。

5 結(jié)束語

針對嵌入式多核任務調(diào)度問題，本文以Forth系統(tǒng)的輪詢調(diào)度機制作為基礎，對中斷任務程序進行改進，提高系統(tǒng)對多核任務突發(fā)事件的處理能力。通過本文改進后的Forth操作系統(tǒng)驗證多核任務調(diào)度的可行性與有效性。實驗從系統(tǒng)的響應時間以及改進前后突發(fā)事件的等待時間兩方面進行驗證，得出的結(jié)論為：采用本文提出的調(diào)度算法，系統(tǒng)的響應速度較快，響應時間大約為1s，任務切換與在線交互時間沒有明顯的延遲；改進后的系統(tǒng)中斷任務的等待明顯低于原系統(tǒng)的中斷任務等待時間，表明本文方法具有良好的可行性。