梅 浩,代紅兵,劉 靜

(云南大學(xué) 信息學(xué)院,昆明 650000)

0 概述

Forth是基于堆棧、交互式且具有簡(jiǎn)單性哲學(xué)思想的計(jì)算機(jī)編程語(yǔ)言和環(huán)境。Forth語(yǔ)言以可延伸的詞典為核心,采用以兩個(gè)堆棧為基礎(chǔ)的高度模塊化結(jié)構(gòu),是一種具有解釋?xiě)B(tài)和編譯態(tài)的雙態(tài)系統(tǒng)[1]。區(qū)別于其他程序設(shè)計(jì)語(yǔ)言,Forth具有可交互、可重構(gòu)、可移植、可擴(kuò)展和高效精簡(jiǎn)的代碼生成等特點(diǎn),甚至可以根據(jù)需要快速構(gòu)造出一個(gè)實(shí)時(shí)多任務(wù)操作系統(tǒng)[2]。Forth語(yǔ)言自發(fā)明以來(lái),先后形成了FIG-Forth、Forth-79、Forth-83、ANS-Forth、ISO-Forth和FORTH-2012標(biāo)準(zhǔn)[3],并且已經(jīng)越來(lái)越多地用于設(shè)計(jì)嵌入式軟件和固件[4-7],幾乎覆蓋了所有主流的嵌入式平臺(tái)[8-10]。

在資源條件有限的嵌入式硬件平臺(tái)上,為滿足復(fù)雜應(yīng)用的需求,出現(xiàn)了一種全新的可重構(gòu)、可擴(kuò)展和可在線交互的基于Forth虛擬機(jī)(Forth Virtual Machine,FVM)架構(gòu)的嵌入式多任務(wù)操作系統(tǒng)(FVM Architecture-based Embedded Multitask Operating System,FVMOS)[11]。與傳統(tǒng)操作系統(tǒng)架構(gòu)不同[12],FVM架構(gòu)實(shí)現(xiàn)了上層Forth操作系統(tǒng)和底層硬件平臺(tái)的抽象,整個(gè)系統(tǒng)運(yùn)行在FVM上。與采用搶占式調(diào)度的Forth操作系統(tǒng)[2]不同,任務(wù)之間的切換需要對(duì)CPU調(diào)度現(xiàn)場(chǎng)和Forth系統(tǒng)狀態(tài)進(jìn)行保護(hù),FVMOS大多采用基于Forth虛擬機(jī)的協(xié)同調(diào)度算法[13],系統(tǒng)事先勾鏈好一個(gè)調(diào)度隊(duì)列,通過(guò)基于FVM的調(diào)度原語(yǔ)pause實(shí)現(xiàn)整個(gè)調(diào)度過(guò)程全部基于Forth虛擬機(jī)之上,不涉及底層硬件細(xì)節(jié)[14],多任務(wù)調(diào)度現(xiàn)場(chǎng)保護(hù)只需將該任務(wù)數(shù)據(jù)堆棧棧頂?shù)刂繁４嬖谄淙蝿?wù)控制塊(Task Control Block,TCB)的數(shù)據(jù)棧指針變量sp中,每個(gè)任務(wù)的任務(wù)空間相互獨(dú)立[15]。

在多任務(wù)內(nèi)存空間管理方面,Forth實(shí)時(shí)多任務(wù)操作系統(tǒng)Forth11的任務(wù)空間劃分為邏輯上獨(dú)立的4個(gè)區(qū),利用頁(yè)地址映射機(jī)制實(shí)現(xiàn)了任務(wù)邏輯地址到物理地址的映射。系統(tǒng)提供專門(mén)的公共資源接口(Common Resource Interface,CRI)進(jìn)行任務(wù)空間分配和回收[16]?；赬86架構(gòu)的PC-Forth系統(tǒng)提供了一個(gè)任務(wù)列表(Task List,TL)用來(lái)存放待執(zhí)行任務(wù)的代碼域地址(Code Field Address,CFA),任務(wù)列表常駐內(nèi)存,系統(tǒng)創(chuàng)建和刪除任務(wù)是在TL中增加或擦除一個(gè)CFA[17]。SwiftX采用FVM思想,系統(tǒng)內(nèi)部包含一個(gè)基于FVM的實(shí)時(shí)多任務(wù)操作系統(tǒng)SwiftOS,任務(wù)空間由TCB和堆棧區(qū)組成,任務(wù)空間一次性全部加載進(jìn)內(nèi)存才能運(yùn)行。在多任務(wù)啟動(dòng)后,任務(wù)無(wú)法刪除,只能強(qiáng)制阻塞任務(wù)使其不再繼續(xù)調(diào)度執(zhí)行[18],但是任務(wù)空間一直駐留在內(nèi)存中且無(wú)法釋放。

嵌入式環(huán)境由于資源的限制,處理器一般不具備復(fù)雜的內(nèi)存管理單元(Memory Management Unit,MMU)[19]?，F(xiàn)有FVMOS的靜態(tài)分配算法嚴(yán)格按照地址遞增的方向?yàn)槿蝿?wù)一次性分配指定大小的內(nèi)存空間,以滿足嵌入式系統(tǒng)對(duì)任務(wù)內(nèi)存分配快速、可靠和高效的現(xiàn)實(shí)需求[20],但其任務(wù)空間靜態(tài)分配后不能對(duì)其回收復(fù)用且無(wú)法刪除調(diào)度隊(duì)列中的任務(wù),造成內(nèi)存資源浪費(fèi)及系統(tǒng)不必要的開(kāi)銷,導(dǎo)致系統(tǒng)性能降低。另外,其只能指定位置勾鏈多任務(wù)調(diào)度隊(duì)列,不能滿足復(fù)雜的嵌入式應(yīng)用需求。

為解決上述問(wèn)題,本文通過(guò)對(duì)FVMOS的TCB、任務(wù)內(nèi)存分配和多任務(wù)調(diào)度隊(duì)列等關(guān)鍵問(wèn)題的研究,在保證FVMOS原有優(yōu)勢(shì)的前提下,提出一種多任務(wù)空間復(fù)用算法。

1 FVMOS框架結(jié)構(gòu)及多任務(wù)管理

1.1 FVMOS框架結(jié)構(gòu)

FVMOS框架結(jié)構(gòu)如圖1所示,FVM采用核心算法DO_NEXT進(jìn)行Forth虛擬機(jī)指令與目標(biāo)物理機(jī)指令的一一對(duì)應(yīng),實(shí)現(xiàn)了系統(tǒng)底層抽象。FVMOS中詞(words)是完成某個(gè)功能的一段代碼或一些數(shù)據(jù)的封裝,FVM和核心詞典組成了Forth基本系統(tǒng)(Forth Basic System,FBS)。操作系統(tǒng)上電啟動(dòng)運(yùn)行一個(gè)終端任務(wù)實(shí)現(xiàn)用戶交互。終端任務(wù)下可動(dòng)態(tài)定義多個(gè)后臺(tái)任務(wù),最終形成一個(gè)終端任務(wù)和多個(gè)后臺(tái)任務(wù)的嵌入式操作系統(tǒng)FVMOS。

圖1 FVMOS框架結(jié)構(gòu)

1.2 FVMOS多任務(wù)管理

1.2.1 任務(wù)控制塊

保存任務(wù)運(yùn)行信息的用戶變量組成了FVMOS的任務(wù)控制塊TCB,其結(jié)構(gòu)如表1所示。

表1 基于FVM的任務(wù)TCB

每個(gè)表項(xiàng)占兩個(gè)內(nèi)存單元,用戶可根據(jù)應(yīng)用需要裁剪或添加TCB表項(xiàng)。終端任務(wù)較特殊,該任務(wù)連接終端設(shè)備,提供用戶交互,需要在TCB中存放相關(guān)操作用到的信息,表1中的所有表項(xiàng)都為終端任務(wù)所需表項(xiàng)。后臺(tái)任務(wù)不占用I/O設(shè)備,任務(wù)調(diào)度運(yùn)行過(guò)程中只需TCB表項(xiàng)的前5項(xiàng)。

1.2.2 后臺(tái)任務(wù)映像

TCB和任務(wù)堆棧共同構(gòu)成任務(wù)映像(Task Image,TI),它們?cè)趦?nèi)存中連續(xù)存放。FVMOS在建立任務(wù)時(shí)以詞的方式保存任務(wù)映像在RAM空間中的TCB起始地址、返回堆棧起始地址和數(shù)據(jù)堆棧起始地址。以上信息全部保存在詞的參數(shù)域,構(gòu)成了任務(wù)信息塊(Task Information Block,TIB)。任務(wù)映像結(jié)構(gòu)如圖2所示。

圖2 任務(wù)映像

系統(tǒng)用戶指針(User Pointer,UP)指向當(dāng)前運(yùn)行的任務(wù)映像首地址,任務(wù)映像各自獨(dú)立,內(nèi)部以UP為基準(zhǔn),采用相對(duì)偏移編址,返回堆棧(Return Stack,RS)和數(shù)據(jù)堆棧(Data Stack,DS)共同構(gòu)成任務(wù)堆棧(Task Stack,TS)。堆棧向下生長(zhǎng),避免了任務(wù)之間互相干擾和破壞,起到了存儲(chǔ)保護(hù)作用。

1.2.3 多任務(wù)創(chuàng)建

在現(xiàn)有FVMOS中,在多任務(wù)管理方面只提供了簡(jiǎn)單的多任務(wù)創(chuàng)建算法tasks:。tasks:首先根據(jù)用戶給定的任務(wù)名在FLASH中建立一個(gè)任務(wù)詞,然后調(diào)用靜態(tài)分配算法allot依次分配TCB、RS和DS,并在任務(wù)詞的參數(shù)域(PFA)記錄相應(yīng)的起始地址。

當(dāng)一個(gè)任務(wù)經(jīng)過(guò)創(chuàng)建、初始化、勾鏈具體執(zhí)行任務(wù)體后,即可加入多任務(wù)調(diào)度隊(duì)列等待調(diào)度執(zhí)行。系統(tǒng)通過(guò)Forth詞onlytask和alsotask實(shí)現(xiàn)多任務(wù)調(diào)度隊(duì)列。其中,onlytask實(shí)現(xiàn)了只有一個(gè)終端任務(wù)的調(diào)度隊(duì)列,后臺(tái)任務(wù)只能通過(guò)alsotask將其勾鏈在終端任務(wù)之后。

1.3 現(xiàn)有FVMOS存在的問(wèn)題

一般嵌入式操作系統(tǒng)任務(wù)刪除功能就是回收任務(wù)TCB,任務(wù)代碼仍駐留在內(nèi)存中,只是不被再次調(diào)用[21],回收的TCB可以進(jìn)行下次分配。

現(xiàn)有FVMOS在多任務(wù)內(nèi)存空間管理方面只提供基本的靜態(tài)按需分配方式,針對(duì)不需要繼續(xù)運(yùn)行的任務(wù)無(wú)法刪除并回收利用其內(nèi)存空間,造成嵌入式硬件平臺(tái)的資源浪費(fèi)。另外,對(duì)不需要繼續(xù)運(yùn)行的任務(wù)只能通過(guò)置任務(wù)為睡眠狀態(tài)來(lái)防止被再次調(diào)度執(zhí)行,系統(tǒng)在維護(hù)調(diào)度隊(duì)列中可能再次調(diào)度執(zhí)行任務(wù)的同時(shí)還要維護(hù)刪除的任務(wù),調(diào)度過(guò)程中會(huì)不斷執(zhí)行其狀態(tài)原語(yǔ),導(dǎo)致系統(tǒng)性能下降。在調(diào)度隊(duì)列中,新建后臺(tái)任務(wù)只能勾鏈在終端任務(wù)后,不能滿足復(fù)雜應(yīng)用的需求。

2 FVMOS多任務(wù)空間復(fù)用算法及實(shí)現(xiàn)

針對(duì)現(xiàn)有FVMOS存在的問(wèn)題,本文提出一種基于FVM的多任務(wù)空間復(fù)用算法Re_allot,該算法能夠可靠、快速、高效地對(duì)整個(gè)任務(wù)映像空間進(jìn)行回收和重分配。同時(shí),對(duì)調(diào)度隊(duì)列勾鏈算法alsotask進(jìn)行改進(jìn),改進(jìn)算法能夠根據(jù)實(shí)際應(yīng)用需要,動(dòng)態(tài)勾鏈其任務(wù)調(diào)度隊(duì)列。

本文先提出基于FVM的多任務(wù)空間復(fù)用管理框架,再給出框架中空閑任務(wù)映像分區(qū)鏈表結(jié)構(gòu),并設(shè)計(jì)Re_allot算法具體的任務(wù)映像空間分配和回收算法,同時(shí)對(duì)多任務(wù)調(diào)度隊(duì)列的勾鏈算法進(jìn)行改進(jìn)。

2.1 多任務(wù)空間復(fù)用管理框架

靜態(tài)分配算法allot的每次分配都是從HERE處按照地址遞增的方向開(kāi)始分配,為不影響其他任務(wù)的運(yùn)行和保持FVMOS的穩(wěn)定,HERE值不能更改。多任務(wù)空間復(fù)用管理框架如圖3所示。

圖3 多任務(wù)空間復(fù)用管理框架

現(xiàn)有系統(tǒng)僅提供allot算法利用內(nèi)存未分配區(qū)域創(chuàng)建新任務(wù),并通過(guò)alsotask算法勾鏈在終端任務(wù)后,形成多任務(wù)調(diào)度隊(duì)列鏈表。在實(shí)現(xiàn)了Re_allot算法的FVMOS中,存在空閑任務(wù)映像分區(qū)鏈表和多任務(wù)調(diào)度隊(duì)列鏈表兩個(gè)鏈表數(shù)據(jù)結(jié)構(gòu)。

2.2 空閑任務(wù)映像分區(qū)鏈表

空閑任務(wù)映像分區(qū)鏈表是一個(gè)帶頭結(jié)點(diǎn)的單向循環(huán)鏈表,以一個(gè)只有TCB控制塊的任務(wù)映像plp作為鏈表頭結(jié)點(diǎn)。plp以詞的形式定義,當(dāng)有任務(wù)刪除時(shí),首先通過(guò)FLASH和RAM之間的互操作tib>tcb得到plp的TCB地址,然后修改TCB中的follower變量信息,把刪除的任務(wù)映像添加到分區(qū)鏈表中?？臻e任務(wù)映像分區(qū)鏈表結(jié)構(gòu)設(shè)計(jì)過(guò)程如下:

步驟1入口參數(shù)全為0,使用task:在詞典中建立一個(gè)任務(wù)名為plp的任務(wù)詞,其對(duì)應(yīng)任務(wù)映像空間只有TCB塊。

步驟2建立空閑任務(wù)映像分區(qū)鏈表。首先初始化plp的任務(wù)映像空間,然后通過(guò)互操作得到TCB地址,根據(jù)TCB內(nèi)變量的相對(duì)位置,獲取到follower變量并使用RAM寫(xiě)操作,賦該值為plp的TCB首地址。

步驟3采用FVMOS獨(dú)有的延遲詞技術(shù),把空閑任務(wù)映像分區(qū)鏈表的建立過(guò)程定義為系統(tǒng)的啟動(dòng)行為。

根據(jù)FORTH2012標(biāo)準(zhǔn),算法實(shí)現(xiàn)如下:

1.0 0 task:plp (RS DS- )

2.partition_list 鏈表結(jié)構(gòu)建立

3.plp task-init 初始化

4.plp tib>tcb dup cell+ !

5.‘partition_list’ turnkey defer!

至此,系統(tǒng)上電就會(huì)存在一個(gè)只有plp的單向循環(huán)鏈表——空閑任務(wù)映像分區(qū)鏈表。當(dāng)有任務(wù)刪除時(shí),勾鏈到該分區(qū)鏈表即可,具體過(guò)程如算法1所示。

算法1空閑任務(wù)映像分區(qū)鏈表勾鏈

輸入刪除待回收的任務(wù)映像空間首地址,即TCB首地址

輸出刪除任務(wù)被勾鏈到plp之后

步驟1終端任務(wù)執(zhí)行plp,通過(guò)定義plp時(shí)DOES>后的默認(rèn)行為得到其TIB,互操作獲取TCB中的follower變量值,并寫(xiě)入輸入的刪除任務(wù)TCB對(duì)應(yīng)表項(xiàng)中。

步驟2同步修改任務(wù)plp的TCB表項(xiàng)follower為輸入的刪除任務(wù)TCB。

采用FORTH2012標(biāo)準(zhǔn),算法實(shí)現(xiàn)如下:

1.partition_list_insert ( d_tcb- )

2.dup plp tib>tcb cell+ @swap cell+ !

3.plp tib>tcb cell+ !

plp的主要作用是系統(tǒng)用來(lái)感知空閑任務(wù)映像分區(qū)鏈表的存在,不能勾鏈任務(wù)體投入運(yùn)行。同時(shí),待回收任務(wù)映像空間直接勾鏈在plp之后,不用遍歷分區(qū)鏈表,算法時(shí)間花費(fèi)主要集中在follower變量指針的修改和賦值方面,時(shí)間復(fù)雜度為O(1),整個(gè)算法執(zhí)行期間最多僅需6個(gè)內(nèi)存單元。

2.3 空閑任務(wù)映像分配

在系統(tǒng)進(jìn)行任務(wù)空間分配時(shí),實(shí)現(xiàn)了空閑任務(wù)映像分區(qū)鏈表之后就可采取兩種方式分配,一種是使用系統(tǒng)原分配算法allot,另一種是本文實(shí)現(xiàn)的多任務(wù)空間復(fù)用算法Re_allot。FVMOS后臺(tái)任務(wù)必須在可接受的時(shí)間范圍內(nèi)運(yùn)行完畢,終端任務(wù)與用戶交互才不會(huì)感受到明顯延遲,并由于后臺(tái)任務(wù)堆?？臻g分配后不能動(dòng)態(tài)增加,其所執(zhí)行的任務(wù)體往往都是多個(gè)Forth定義嵌套組合而成,很難精確計(jì)算出運(yùn)行期間所需的堆?？臻g大小,因此后臺(tái)任務(wù)的映像空間基本控制在一個(gè)范圍內(nèi)。鑒于嵌入式操作系統(tǒng)中對(duì)內(nèi)存分配的要求和FVMOS中多任務(wù)的特殊情況,本文采用快速高效的首次適應(yīng)(First Fit,FF)算法進(jìn)行空閑任務(wù)映像分區(qū)分配,算法執(zhí)行流程如圖4所示。

圖4 空閑任務(wù)映像分區(qū)分配算法流程

Fig.4 Procedure of the distribution algorithm for idle task image partition

在進(jìn)行空閑任務(wù)映像分配時(shí),沿著空閑任務(wù)映像分區(qū)鏈表plp開(kāi)始遍歷,查找到首個(gè)大小能滿足申請(qǐng)要求的空閑任務(wù)映像分區(qū)給用戶。如果空閑任務(wù)映像分區(qū)鏈表中沒(méi)有滿足大小要求的空閑分區(qū),則調(diào)用靜態(tài)分配算法allot來(lái)分配任務(wù)空間,整個(gè)過(guò)程不涉及任務(wù)映像移動(dòng),分配過(guò)程中只需修改一個(gè)follower變量指針,具體過(guò)程如算法2所示。

算法2空閑任務(wù)映像分區(qū)分配

輸入任務(wù)所需RS、DS大小

輸出重利用的任務(wù)映像空間首地址

步驟1執(zhí)行plp,獲取空閑任務(wù)映像分區(qū)鏈表地址并開(kāi)始鏈表遍歷。

步驟2通過(guò)獲取TCB中SP0變量存放的數(shù)據(jù)棧起始地址,與TCB首地址和TCB大小相減,得到當(dāng)前訪問(wèn)映像空間堆棧大小。

步驟3判斷當(dāng)前任務(wù)映像空間大小是否滿足要求,若滿足要求,則執(zhí)行步驟4;否則轉(zhuǎn)到步驟5。

步驟4從空閑任務(wù)映像分區(qū)鏈表中得到滿足要求的任務(wù)映像空間并利用終端任務(wù)給出該映像空間地址和ok提示,清理算法臨時(shí)數(shù)據(jù)并退出。

步驟5繼續(xù)向下遍歷空閑任務(wù)映像分區(qū)鏈表。

步驟6對(duì)空閑任務(wù)映像分區(qū)鏈表是否遍歷完畢進(jìn)行判斷,若是則通過(guò)終端任務(wù)給出提示并結(jié)束算法;否則轉(zhuǎn)到步驟2繼續(xù)執(zhí)行算法流程。

根據(jù)FORTH2012標(biāo)準(zhǔn),算法實(shí)現(xiàn)如下:

1.Re_allot (RS DS- )

2.+plp tib>tcb

3.begin

4.cell+ @dup dup 6 + @swap-10-

5.swap>r 返回堆棧暫存數(shù)據(jù)

6.over swap 1+<

7.if

8.r > dup partition_list_delete @

9.-1 abort ‘ok’

10.else

11.r> cell+@ dup plp tib>tcb =

12.until

13.‘no suitable task TI’ 2drop

步驟4中置換出滿足要求的任務(wù)映像空間對(duì)應(yīng)的算法partition_list_delete和任務(wù)映像回收算法原理一致,在保證鏈表結(jié)構(gòu)不被破壞的情況下修改follower值,邏輯上置換出將要重分配的分區(qū),具體過(guò)程如算法3所示。

算法3partition_list_delete

輸入待置換出進(jìn)行分配的任務(wù)映像空間TCB首地址

輸出置換出指定任務(wù)映像空間后的空閑任務(wù)映像分區(qū)鏈表

步驟1輸入數(shù)據(jù)合法性判斷,如果是plp,則給出提示并終止算法。

步驟2對(duì)當(dāng)前訪問(wèn)任務(wù)映像的follower執(zhí)行RAM讀操作@,獲取該值并判斷是否為需要摘取的目標(biāo)任務(wù)映像,若是則執(zhí)行步驟3;否則執(zhí)行步驟4。

步驟3獲取目標(biāo)任務(wù)映像所在分區(qū)鏈表中的下一個(gè)任務(wù)映像TCB首地址,并以此值修改當(dāng)前訪問(wèn)任務(wù)映像的follower。plp的TCB首地址壓入數(shù)據(jù)堆棧,轉(zhuǎn)步驟5,提前結(jié)束算法流程。

步驟4繼續(xù)遍歷訪問(wèn)鏈表結(jié)構(gòu)中的下一個(gè)任務(wù)映像空間。

步驟5對(duì)空閑任務(wù)映像分區(qū)鏈表是否遍歷完畢進(jìn)行判斷,如果遍歷完畢,即棧中存放的下一個(gè)要訪問(wèn)的任務(wù)映像地址是plp,則執(zhí)行步驟6;否則程序跳轉(zhuǎn)到步驟2繼續(xù)執(zhí)行。

步驟6丟棄算法執(zhí)行過(guò)程中的臨時(shí)數(shù)據(jù)并結(jié)束算法。

根據(jù)FORTH2012標(biāo)準(zhǔn),算法實(shí)現(xiàn)如下:

1.partition_list_delete (tcb- )

2.plp tib>tcb 2dup =

3.if

4.-1 abort ‘forbidden’

5.then

6.begin

7.2dup cell+ @=

8.if

9.dup cell+ @cell+@

10.swap cell+ ! plp tib>tcb

11.else

12.cell+ @

13.then

14.dup plp tib>tcb =

15.until

16.2drop

2.4 任務(wù)映像回收

若多任務(wù)調(diào)度隊(duì)列中某個(gè)任務(wù)的任務(wù)體執(zhí)行完畢且以后不需要再次執(zhí)行,則對(duì)其運(yùn)行載體——任務(wù)映像進(jìn)行回收,具體過(guò)程如算法4所示。

算法4任務(wù)映像回收

輸入多任務(wù)調(diào)度隊(duì)列鏈表中待回收任務(wù)TCB首地址

輸出多任務(wù)調(diào)度隊(duì)列鏈表中刪除指定任務(wù)映像并回收到空閑任務(wù)映像分區(qū)鏈表

步驟1算法輸入數(shù)據(jù)合法性判斷,如果待刪除任務(wù)映像是終端任務(wù),則終止算法并給出禁止提示。

步驟2從終端任務(wù)映像開(kāi)始遍歷調(diào)度隊(duì)列。

步驟3判斷當(dāng)前訪問(wèn)任務(wù)映像follower是不是指向待回收任務(wù),若是則執(zhí)行步驟4;否則執(zhí)行步驟6。

步驟4使用待回收任務(wù)映像的follower值對(duì)應(yīng)修改當(dāng)前訪問(wèn)的任務(wù)映像,邏輯上從調(diào)度隊(duì)列中刪除待回收任務(wù)映像并把該任務(wù)映像首地址壓入終端任務(wù)數(shù)據(jù)堆棧。

步驟5終端任務(wù)數(shù)據(jù)堆棧彈出棧頂數(shù)據(jù)作為partition_list_insert的輸入,邏輯勾鏈到空閑任務(wù)映像分區(qū)鏈表后跳轉(zhuǎn)到步驟7。

步驟6繼續(xù)多任務(wù)調(diào)度隊(duì)列的遍歷,如果隊(duì)列遍歷完畢則執(zhí)行步驟7;否則轉(zhuǎn)到步驟3。

步驟7清除算法執(zhí)行過(guò)程中終端任務(wù)數(shù)據(jù)堆棧中暫存的臨時(shí)數(shù)據(jù)并結(jié)束算法。

根據(jù)FORTH2012標(biāo)準(zhǔn),算法實(shí)現(xiàn)如下:

1.task_delete (d_tcb- )

2.dup status =

3.if

4.-1 abort ‘forbidden’

5.then

6.status

7.begin

8.2dup cell+ @=

9.if

10.dup cell+ @cell+@swap cell+ !

dup partition_list_insert status

11.else

12.cell+ @

13.then

14.dup status =

15.until

16.2drop

由以上分析可以得出,Re_allot算法的整個(gè)過(guò)程都采用FVMOS的基本詞實(shí)現(xiàn),涉及的都是堆棧操作,算法效率高。算法時(shí)間復(fù)雜度為O(N),其中,N為空閑任務(wù)映像分區(qū)鏈表的長(zhǎng)度,空間復(fù)雜度為O(1)。

2.5 多任務(wù)調(diào)度隊(duì)列

FVMOS任務(wù)調(diào)度采用的是協(xié)同式調(diào)度算法,任務(wù)按照事先確定的調(diào)度隊(duì)列順序依次調(diào)度執(zhí)行,系統(tǒng)不能完成實(shí)時(shí)性要求高的任務(wù)。

多任務(wù)空間復(fù)用算法的前提是能夠根據(jù)需求操作多任務(wù)調(diào)度隊(duì)列,系統(tǒng)原有的alsotask算法只能在一個(gè)位置勾鏈多任務(wù),這樣的方式不能滿足復(fù)雜的嵌入式應(yīng)用需求,因此設(shè)計(jì)并實(shí)現(xiàn)了基于FVM的多任務(wù)調(diào)度隊(duì)列勾鏈算法queue_schedule,具體過(guò)程如算法5所示。

算法5queue_schedule

輸入指定勾鏈位置和目標(biāo)勾鏈任務(wù)的TCB首地址

輸出勾鏈完畢后的調(diào)度隊(duì)列

步驟1調(diào)度隊(duì)列中指定勾鏈位置對(duì)應(yīng)的任務(wù)映像TCB中的follower值更新目標(biāo)勾鏈任務(wù)的follower。

步驟2重新修改指定勾鏈位置所在任務(wù)映像的follower值為目標(biāo)勾鏈任務(wù)首地址。

根據(jù)FORTH2012標(biāo)準(zhǔn),算法實(shí)現(xiàn)如下:

1.queue_schedule (ftcb ntcb- )

2. 任務(wù)ftcb之后勾鏈ntcb

3.2dup swap cell+ @

4.swap cell+ !

5.swap cell+ !

alsotask算法都是采用基于FVM的基本詞實(shí)現(xiàn),整個(gè)過(guò)程只需要一次RAM讀操作和兩次RAM寫(xiě)操作,算法時(shí)間復(fù)雜度都為O(1),alsotask需要4個(gè)內(nèi)存單元,queue_schedule需要8個(gè)內(nèi)存單元。

FVMOS以詞的形式定義任務(wù)體并添加到Forth詞典,任務(wù)體運(yùn)行所需的數(shù)據(jù)放在任務(wù)映像空間的DS,執(zhí)行代碼地址放在RS,實(shí)現(xiàn)程序和數(shù)據(jù)分離。后臺(tái)任務(wù)所執(zhí)行的具體任務(wù)體代碼中都要插入pause原語(yǔ)作為調(diào)度點(diǎn),當(dāng)任務(wù)執(zhí)行到pause就轉(zhuǎn)到調(diào)度隊(duì)列中的下一個(gè)任務(wù),同時(shí)任務(wù)體必須用begin…again Forth詞包圍。因?yàn)槿蝿?wù)投入運(yùn)行前需把任務(wù)體的代碼域地址CFA壓入RS——勾鏈任務(wù)體,所以基于FVM的多任務(wù)運(yùn)行無(wú)需進(jìn)行任務(wù)虛擬地址到物理地址的映射,整個(gè)過(guò)程如圖5所示。

圖5 基于Forth虛擬機(jī)的協(xié)同式調(diào)度隊(duì)列

Fig.5Collaborative scheduling queue based on Forth virtual machine

3 實(shí)驗(yàn)評(píng)估

本文在AVR8架構(gòu)的Arduino Uno Rev3嵌入式開(kāi)發(fā)板上,移植一個(gè)開(kāi)源的FVMOS,實(shí)現(xiàn)多任務(wù)空間復(fù)用算法。在實(shí)驗(yàn)環(huán)境中,利用FVMOS提供的內(nèi)存地址訪問(wèn)接口和一些硬件傳感器,設(shè)計(jì)了一個(gè)環(huán)境溫度監(jiān)控程序,程序的整個(gè)過(guò)程分為采集、處理、檢測(cè)和控制,環(huán)境溫度監(jiān)控程序流程如圖6所示。

圖6 環(huán)境溫度監(jiān)控程序流程

下面給出程序主要步驟的核心代碼,根據(jù)FORTH2012標(biāo)準(zhǔn),算法實(shí)現(xiàn)如下:

1.20 20 task:task02

2.:startup (-) 定義系統(tǒng)啟動(dòng)任務(wù)

3.init

4.task02 task-init

5. 任務(wù)映像空間初始化

6.task02 tib>tcb activate ledBlink

7. task02勾鏈ledBlink任務(wù)體

8.onlytask

9.task02 tib>tcb alsotask

10.multi; 開(kāi)啟多任務(wù)調(diào)度

11.20 20 task:task03

12.task03 task-init

13.:linkTask03

14.task03 tib>tcb activate sensor

15. activate勾鏈其后的任務(wù)體

16.task02 tib>tcb task03 tib>tcb

17.queue_schedule task03添加到task02之后

18.task02 tib>tcb task_delete

19. 刪除任務(wù)task02

20.20 20 task:task04

21.task04 task-init

22.:linkTask04

23.task04 tib>tcb activate buzzer

24.task03 tib>tcb task04 tib>tcb

25.queue_schedule

步驟1～步驟10(對(duì)應(yīng)圖6中的①)定義了任務(wù)task02并在startup中勾鏈控制led閃爍的任務(wù)體,加入到多任務(wù)調(diào)度隊(duì)列。開(kāi)啟多任務(wù),若led閃爍則表示多任務(wù)運(yùn)行正常。步驟11～步驟17(對(duì)應(yīng)圖6中的②)添加后臺(tái)任務(wù)task03并勾鏈控制溫度傳感器并獲取外界溫度的任務(wù)體sensor。步驟18、步驟19(對(duì)應(yīng)圖6中的③)回收不再需要的指示任務(wù)task02。步驟20～步驟25(對(duì)應(yīng)圖6中的④)添加task04,勾鏈對(duì)task03獲取到的溫度進(jìn)行判斷觸發(fā)警報(bào)的任務(wù)體buzzer。

本文改進(jìn)的系統(tǒng)程序中各任務(wù)的TCB塊和堆棧大小(包含返回堆棧和數(shù)據(jù)堆棧)對(duì)比原系統(tǒng)中采用同樣方法創(chuàng)建的任務(wù),內(nèi)存單元數(shù)據(jù)如表2所示。

表2 程序任務(wù)內(nèi)存單元對(duì)比Table 2 Comparison of program task memory units

在TCB表項(xiàng)中,有關(guān)終端控制的變量在后臺(tái)任務(wù)中無(wú)法使用,對(duì)原系統(tǒng)的任務(wù)創(chuàng)建過(guò)程進(jìn)行分析和實(shí)驗(yàn),系統(tǒng)啟動(dòng)即對(duì)終端任務(wù)TCB進(jìn)行初始化,有關(guān)配置信息存放在E2PROM中,在創(chuàng)建任務(wù)時(shí)只對(duì)TCB中前5項(xiàng)進(jìn)行初始化,本文在實(shí)現(xiàn)多任務(wù)空間復(fù)用算法時(shí)對(duì)系統(tǒng)創(chuàng)建任務(wù)也進(jìn)行了改進(jìn),保持原有接口不變,TCB精簡(jiǎn)至前5項(xiàng)。

在環(huán)境溫度監(jiān)控程序的每一步操作后采集HERE值、查看后臺(tái)任務(wù)數(shù)和計(jì)算當(dāng)前系統(tǒng)內(nèi)存利用率,并與原系統(tǒng)作對(duì)比,結(jié)果如表3所示。其中HERE值表示下一個(gè)可分配利用的地址空間,系統(tǒng)通過(guò)unused詞獲取當(dāng)前系統(tǒng)可用RAM內(nèi)存空間大小,實(shí)驗(yàn)硬件平臺(tái)的RAM空間大小為2 KB。

表3 嵌入式Forth操作系統(tǒng)綜合性能對(duì)比

Table 3 Comparison of overall performance between embedded Forth systems

任務(wù)階段原系統(tǒng)本文改進(jìn)的系統(tǒng)HERE值任務(wù)數(shù)量?jī)?nèi)存利用率/%HERE值任務(wù)數(shù)量?jī)?nèi)存利用率/%系統(tǒng)啟動(dòng)450113.4461113.9task02521216.8512216.4task03592320.3563318.9刪除task02592320.3563218.9task04663423.8563318.9

在系統(tǒng)啟動(dòng)階段,由于多任務(wù)空間復(fù)用算法引入了空閑任務(wù)映像分區(qū)鏈表來(lái)維護(hù)后臺(tái)刪除任務(wù)映像分區(qū)信息,plp占用一部分空間,但其精簡(jiǎn)了后臺(tái)任務(wù)TCB和Re_allot算法,使得系統(tǒng)空間資源得到更有效的利用。task04重利用了task02的任務(wù)映像,HERE值沒(méi)有改變。整個(gè)應(yīng)用程序內(nèi)存使用率為18.9%,沒(méi)有采用本文實(shí)現(xiàn)算法下的原系統(tǒng)最終程序內(nèi)存使用率為23.8%。同樣地,以Arduino Uno Rev3平臺(tái)為例,假設(shè)任務(wù)堆棧空間大小均為40,對(duì)比高負(fù)荷情況下兩種方式能支持系統(tǒng)運(yùn)行的最大任務(wù)數(shù),如表4所示。

表4 堆?？臻g大小為40時(shí)高負(fù)荷情況下的任務(wù)數(shù)量

Table 4 Number of tasks under high loads when the stack size is 40

比較項(xiàng)目原系統(tǒng)本文改進(jìn)的系統(tǒng)無(wú)回收任務(wù)2434回收N個(gè)任務(wù)24-N34

當(dāng)無(wú)回收任務(wù)時(shí),本文多任務(wù)空間復(fù)用算法改進(jìn)的系統(tǒng)和原系統(tǒng)均采用靜態(tài)分配,TCB表項(xiàng)精簡(jiǎn)至前5項(xiàng),使得前者的任務(wù)數(shù)明顯多于后者。當(dāng)系統(tǒng)運(yùn)行過(guò)程中有任務(wù)回收時(shí),由于前者實(shí)現(xiàn)了多任務(wù)空間復(fù)用算法且對(duì)比實(shí)驗(yàn)中堆?？臻g都為40,回收的所有任務(wù)映像空間均能再次分配利用,相比無(wú)多任務(wù)空間復(fù)用算法下的原系統(tǒng),最終運(yùn)行的任務(wù)數(shù)為24-N,其中N小于系統(tǒng)最大支持任務(wù)數(shù)。

本文實(shí)現(xiàn)的算法基于FVM架構(gòu),不涉及宿主機(jī)底層硬件細(xì)節(jié),平臺(tái)移植可以不更改代碼,保證了FVMOS的可移植、可交互、可擴(kuò)展和可重構(gòu)等特性,算法時(shí)間復(fù)雜度為O(N),空間復(fù)雜度為O(1)。

4 結(jié)束語(yǔ)

FVMOS系統(tǒng)在運(yùn)行過(guò)程中無(wú)法刪除后臺(tái)任務(wù)映像,導(dǎo)致內(nèi)存利用率低和系統(tǒng)性能下降。本文算法在保留FVM固有特性的前提下,時(shí)間復(fù)雜度控制在線性時(shí)間范圍內(nèi),空間復(fù)雜度也在一個(gè)較小的常數(shù)范圍內(nèi)。實(shí)驗(yàn)結(jié)果表明,該算法在資源有限的嵌入式環(huán)境下,提高了內(nèi)存利用率,系統(tǒng)調(diào)度隊(duì)列中無(wú)需維護(hù)刪除的任務(wù),系統(tǒng)性能也有所提升,支持運(yùn)行更多的任務(wù)。但目前系統(tǒng)采用的是協(xié)同調(diào)度算法,不能滿足實(shí)時(shí)性任務(wù)的需求,因此下一步將改進(jìn)多任務(wù)調(diào)度算法,對(duì)強(qiáng)實(shí)時(shí)任務(wù)采用靜態(tài)分配方式,一般任務(wù)采用多任務(wù)空間復(fù)用算法,增強(qiáng)算法實(shí)時(shí)性,并且在實(shí)現(xiàn)基于優(yōu)先級(jí)的可搶占調(diào)度算法時(shí),需對(duì)算法中的相關(guān)操作進(jìn)行互斥訪問(wèn),保證系統(tǒng)內(nèi)存分配的可靠性。