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

任鳳琴 ，張俊生，程耀瑜

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

1 引言

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

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

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

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

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

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

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

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

圖2 輪詢調(diào)度

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

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

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

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

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

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

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

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

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

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

圖4 中斷響應(yīng)過程

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

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

圖5 中斷任務(wù)TCB

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

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

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

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

4 實(shí)驗評估

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

表1 環(huán)境配置

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

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

(1)

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

(2)

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

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

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

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

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

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

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

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

5 結(jié)束語

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