接口透明傳輸中數(shù)據(jù)緩存的建模設(shè)計(jì)

韓東

（華北計(jì)算機(jī)系統(tǒng)工程研究所 北京 100083）

在工業(yè)應(yīng)用中，同一系統(tǒng)中常會連接許多不同類型的設(shè)備，但因設(shè)備的接口不同，嵌入式系統(tǒng)中會涉及到不同接口間的數(shù)據(jù)透傳，比如串口485/232的數(shù)據(jù)透明傳輸?shù)揭蕴W(wǎng)接口等。這樣的系統(tǒng)中需要建立接口間的數(shù)據(jù)緩存FIFO，來實(shí)現(xiàn)接口的數(shù)據(jù)接收和發(fā)送。

為了通用性，不具體指定接口，而是概念化為實(shí)現(xiàn)接口A、B、C、D、W、X、Y、Z間的數(shù)據(jù)透傳處理的數(shù)據(jù)緩存 FIFO模型。

1 名詞定義

在緩存建模前先定義幾個名詞的概念。

1.1 接口映射

考慮透傳時接口的分配，即一個接口接收到的數(shù)據(jù)需要從哪個接口發(fā)送出去。為每個接口設(shè)定一個發(fā)送到接口屬性，接口PORT(T)（T指任一接口）的發(fā)送到屬性值記為DATA_TO(T)。當(dāng)有 DATA_TO(T)=PORT(V)時，意味著 PORT(T)接收到的數(shù)據(jù)將由PORT(V)發(fā)送，這稱為DATA_TO接口映射，簡稱接口映射。

圖1 接口映射Fig.1 Interface mapping

若對于任意 T和任意 V，當(dāng) PORT(T)≠PORT(V)時，有DATA_TO(T)≠DATA_TO(V)，則稱該接口映射為接口單射[3]。

若對于任意 T和任意 V，當(dāng) PORT(T)≠PORT(V)時，可DATA_TO(T)≠DATA_TO(V)有，則稱該接口映射為接口多射。

若兩個接口 T和 V，當(dāng) PORT(T)≠PORT(V)時，有DATA_TO(T)=PORT(V)同時 DATA_TO(V)=PORT(T)，則稱該接口映射為接口T和V對射，稱PORT(T)和PORT(V)為一組對射對。

若所有2N個接口既滿足單射又滿足兩兩對射[1]，則稱2N個接口映射為接口一一映射。

1.2 數(shù)據(jù)收發(fā)有序

如有一個數(shù)據(jù)序列Q，按序列順序分為n個序列組Q(n)（n=0,1,...N），當(dāng)將 Q(n)按 n 的字典順序（Q(0),Q(1),...Q(N)）排列成序列Q’時，滿足Q′=Q，稱Q(n)為Q的有序序列組。

如果一個數(shù)據(jù)序列Q在從一個接口PORT(T)接收并按序列組Q(n)寫入緩存后，緩存中的存放的序列組Q(n)為Q的有序序列組，則稱數(shù)據(jù)有序接收。

如果緩存中的Q序列組被一個接口PORT(V)發(fā)送時，發(fā)送出的數(shù)據(jù)序列組Q(n)為Q的有序序列組，則稱數(shù)據(jù)有序發(fā)送。

如果一個數(shù)據(jù)序列Q在從接口PORT(T)接收后在接口PORT(V)發(fā)送出，發(fā)送出的數(shù)據(jù)序列組Q(n)與為Q的有序序列組，則稱數(shù)據(jù)有序收發(fā)，簡稱有序。

1.3 分塊緩存

如果每次寫入或讀出操作的緩存對象是直接數(shù)據(jù)，則稱之為無分塊緩存；而如果操作對象是一個緩存區(qū)的地址，則稱之為分塊緩存，且該地址指明的是一個緩存塊的首地址[2]。

如果一個緩存塊，在其使用過程中涉及建立一個新的緩存塊。若緩存允許此操作，則稱之為可嵌套分塊緩存；若緩存不允許此操作，則稱之為無嵌套分塊緩存。

如果一個分塊緩存，每個緩存塊的大小固定相等，則稱之定長分塊緩存；而若每個緩存塊的大小可變，則稱之可變長分塊緩存。

1.4 私用緩存

如果一個緩存區(qū)只有一個特定接口PORT(T)可以訪問和得到使用權(quán)，則稱之為PORT(T)的私有緩存區(qū)，否則如果所有端口都能訪問及得到使用權(quán)，則稱之為公用緩存。

2 接口單射有序私有無分塊緩存的設(shè)計(jì)

首先構(gòu)建最精簡的FIFO緩存模型，接口單射私有無分塊緩存，它僅須實(shí)現(xiàn)單字節(jié)數(shù)據(jù)序列的寫入和讀出操作，無其它特殊要求。

為每個接口PORT(T)建立一個私有的數(shù)據(jù)FIFO緩存區(qū)BUF(T)，緩存區(qū)大小為SIZE_BUF(T)，以輔助 T接口數(shù)據(jù)的接收和發(fā)送操作[4]。

緩存模型建立如下：

1)選定一個連續(xù)的RAM地址空間，在此空間上開辟一段大小為SIZE_BUF(T)的連續(xù)空間，將此塊空間初始化為環(huán)形FIFO區(qū)作為T接口的緩存區(qū)，記作BUF(T)。

2)設(shè)置輔助指針T_PUT_POINTER和T_GET_POINTER，及變量 T_BUF_LENGTH。 其中，T_PUT_POINTER指向BUF(T)中下一個可寫入數(shù)據(jù)的地址；T_GET_POINTER指向BUF(T)中下一個可讀出的數(shù)據(jù)的地址；T_BUF_LENGTH為BUF(T)中有效字節(jié)數(shù)據(jù)的數(shù)量[6]。

①寫入操作

字節(jié)數(shù)據(jù)寫入BUF(T)緩存時執(zhí)行寫入操作，首先判斷緩存區(qū)是否已經(jīng)寫滿。緩存區(qū)已經(jīng)寫滿的標(biāo)志是T_BUF_LENGTH大小為 SIZE_BUF(T)，此時 T_PUT_POINTER與T_GET_POINTER指相同一空間。如緩存已滿，則該數(shù)據(jù)被丟棄。否則，將其寫入T_PUT_POINTER指向的空間。同時，T_PUT_POINTER增加一個字節(jié)空間，如果增加后超過了BUT(T)的底地址，則T_PUT_POINTER指向其首地址。最后更新T_BUF_LENGTH增加一字節(jié)長度[5]。

②讀出操作

讀出BUF(T)緩存中數(shù)據(jù)時執(zhí)行讀出操作，首先判斷緩存區(qū)是否已空。緩存區(qū)空的標(biāo)志是T_BUF_LENGTH大小為0，此時T_PUT_POINTER與T_GET_POINTER指相同一空間。如果緩存已空，則讀出無效標(biāo)志。否則讀出T_GET_POINTER指向的空間。同時T_GET_POINTER增加一個字節(jié)空間，如果增加后超過了BUF(T)的底地址，則T_GET_POINTER指向其首地址。最后更新T_BUF_LENGTH減少一字節(jié)長度[7]。

圖2 單字節(jié)FIFOFig.2 Single byte FIFO

3)建立好以上緩存區(qū)后，為T接口增添數(shù)據(jù)接收和發(fā)送操作函數(shù)，其中接收操作映射為緩存區(qū)BUF(T)的寫入操作，發(fā)送操作映射為T的對應(yīng)接口X的緩存區(qū)BUF(X)的讀出操作。

3 接口單射有序私有定長無嵌套分塊緩存

考慮接口接收到的字節(jié)序列為幀格式報(bào)文塊，實(shí)現(xiàn)其收發(fā)有序。

假設(shè)一個數(shù)據(jù)塊的接收或發(fā)送過程中，沒有其它接口數(shù)據(jù)插入，仍為接口單射私有緩存。這樣，在上個模型的基礎(chǔ)上建立可分塊的緩存組，稱作緩存塊。

假設(shè)各報(bào)文塊的大小不會超過緩存塊的數(shù)據(jù)容量，且接收報(bào)文到一個數(shù)據(jù)塊或發(fā)送一個數(shù)據(jù)塊的報(bào)文到接口的過程中，沒有其它數(shù)據(jù)塊的借出，即緩存塊無嵌套。

如此，只需在上節(jié)模型基礎(chǔ)上將單字節(jié)FIFO緩存，替換成緩存塊地址的FIFO緩存，實(shí)現(xiàn)緩存塊的地址取出和存入處理即可。以下將緩存塊的取出稱為緩存塊借出，將緩存塊的存入稱為緩存塊歸還。

模型改進(jìn)如下：

1)將上節(jié)緩存中接口PORT(T)的緩存BUF(T)分為N個固定字節(jié)長度為BUF_DIV_SIZE(T)的緩存塊BUF_DIV(T)。

2)為每個分塊添加固定字節(jié)長度為HEAD_SIZE(T)的信息頭。其中，信息頭位于BUF_DIV(T)的起始位的BUF_DIV_HEAD_SIZE(T)個字節(jié)的地址空間。信息頭依次固定包含分塊狀態(tài)、分塊數(shù)據(jù)長度及下一個分塊起始地址。分塊數(shù)據(jù)長度最大為BUF_DIV_SIZE(T)-BUF_DIV_HEAD_SIZE(T)，標(biāo)記為 BUF_DIV_BODY_SIZE(T)。

3)建立兩個如上節(jié)模型所述的FIFO，將其操作對角由單字節(jié)替換成對32位的4字節(jié)，輔助緩存塊的寫入借出、寫入歸還和讀出借出、讀出歸還操作。設(shè)置其中一個FIFO存放還未寫入數(shù)據(jù)的緩存塊地址，稱為T_FREE_TABLE，另一個存放已經(jīng)寫入數(shù)據(jù)的緩存塊地址，稱為T_USED_TABLE。

4)為T_FREE_TABLE添加輔助指針T_FREE_TABLE_P UT_POINTER和T_FREE_TABLE_GET_POINTER，及變T_FR EE_TABLE_LENGTH。T_FREE_TABLE_PUT_POINTER指向下一個可存入要?dú)w還的分塊地址的FIFO地T_FREE_TABLE_GET_POINTER指向下一個存儲著可借出的FREE分塊地址的FIFO地址。T_FREE_TABLE_LENGTH指示FIFO中存儲的可用FREE空分塊地址數(shù)據(jù)的數(shù)量。其借出和歸還操作，類同于上節(jié)所述的讀出和寫入操作，不同的是操作的對象現(xiàn)在是FREE分塊地址數(shù)據(jù)，而上節(jié)中是單字節(jié)數(shù)據(jù)?，F(xiàn)在指針增加或減小1，是指一個緩存塊大小。對于整個分塊模型來說，T_FREE_TABLE中的借出是指報(bào)文的寫入前借出，即借出的FREE分塊地址用來寫入接收來的報(bào)文數(shù)據(jù)分組，以下簡稱寫入借出；T_FREE_TABLE中的歸還是指報(bào)文的讀出后歸還，即歸還的分塊地址是已經(jīng)完成了其中報(bào)文數(shù)據(jù)分組的讀空操作的FREE分塊地址，以下簡稱讀出歸還。

5)為T_USED_TABLE添加輔助指針T_USED_TABLE_PUT_POINTER和T_USED_TABLE_GET_POINTER，及變量T_USED_TABLE_LENGTH。T_USED_TABLE_PUT_POINTER指向下一個可存入要?dú)w還的USED分塊地址數(shù)據(jù)的FIFO地址T_USED_TABLE_GET_POINTER指向下一個存儲著可借出的USED分塊地址數(shù)據(jù)的FIFO地址。T_USED_TABLE_L ENGTH指示FIFO中存儲的可用USED分塊地址數(shù)據(jù)的數(shù)量。對于整個模型來說，T_USED_TABLE中的借出是指報(bào)文的讀空前借出，即借出的USED分塊地址用來讀出發(fā)送其中的報(bào)文數(shù)據(jù)分組，以下簡稱讀出借出；T_USED_TABLE中的歸還是指報(bào)文的寫入后歸還，即歸還的分塊地址是已經(jīng)完成了其中報(bào)文數(shù)據(jù)分組的寫入操作的USED分塊地址，以下簡稱寫入歸還。

6)假設(shè)完成接口對射組PORT(T)與PORT(X)之間的數(shù)據(jù)透傳。設(shè)定接口PORT(T)的接收操作映射到T的緩存區(qū)BUF(T)，PORT(T)的發(fā)送操作映射到接口X的緩存區(qū)BUF(X)；當(dāng)接口PORT(T)有數(shù)據(jù)需要接收時，首先執(zhí)行寫入借出操作，T_FRE E_TABLE中借出一個可供數(shù)據(jù)寫入的FREE緩存塊地址，使用該分塊地址再執(zhí)行PORT(T)接收數(shù)據(jù)的寫入操作；寫入完成后，執(zhí)行寫入歸還操作，將已寫入數(shù)據(jù)的FREE緩存塊標(biāo)志成USED緩存塊，并將其地址歸還到在T_USED_TABLE中。而需要X接口發(fā)送數(shù)據(jù)時，首先要執(zhí)行讀出借出操作，在T_USED_TABLE中借出一個已經(jīng)寫入了數(shù)據(jù)的USED緩存塊的地址，使用該分塊地址去執(zhí)行PORT(X)的數(shù)據(jù)讀出發(fā)送操作，讀出完成后，執(zhí)行讀出歸還操作，將已經(jīng)讀空了的USED緩存塊標(biāo)志成FREE緩存塊，并將其地址歸還到T_FREE_TABLE中。

圖3 無嵌套傳輸過程Fig.3 No nested transmitting procedure

4 接口單射有序私用定長可嵌套分塊緩存

現(xiàn)在在上節(jié)的基礎(chǔ)上設(shè)計(jì)接口單射有序定長可嵌套分塊緩存?？汕短椎囊馑际窃趯懭虢璩鲆粋€FREE分塊后,記作FREE_BUF_0，寫入數(shù)據(jù)過程仍在進(jìn)行中且還未標(biāo)志成USED分塊，尚未執(zhí)行寫入歸還操作前，又需要一個新的寫入借出FREE分塊，記作FREE_BUF_1。同時后借出的分塊FREE_BUF_1會先于FREE_BUF_0執(zhí)行寫入歸還操作。歸還后FREE_BUF_0標(biāo)記為USED_BUF_0，而FREE_BUF_1標(biāo)記為 USED_BUF_1。

這樣在相應(yīng)USED_TABLE表中USED_BUF_1排列在USED_BUF_0前，即執(zhí)行讀出借出時會先借出分塊USED_BUF_1，但是要求 USED_BUF_0會先于USED_BUF_1讀出借出。在寫入數(shù)據(jù)時因?yàn)閿?shù)據(jù)量超過一個分塊最大數(shù)據(jù)長度而會在出現(xiàn)嵌套分塊情況。

模型改進(jìn)如下：

1)在上節(jié)模型中為接口PORT(T)的緩存塊BUF_DIV(T)的信息頭添加上一個新的 32位信息標(biāo)志USED_LINK_NEXT_DIVBUF，用來存放嵌套時的下一個借出分塊地址。

2)嵌套接收操作過程為：接收開始，執(zhí)行寫入借出操作借出第一個FREE_BUF_0，根據(jù)需求執(zhí)行寫入借出操作借出第 二 個 FREE_BUF_1并 將 FREE_BUF_0的USED_LINK_NEXT_DIVBUF置為 FREE_BUF_1的地址，如需要第三個 FREE_BUF_2則將 FREE_BUF_1的USED_LINK_NEXT_DIVBUF置為 FREE_BUF_2的地址，以此類推直到最后一個的FREE_BUF_LAST，此時將FREE_BUF_LAST的 USED_LINK_NEXT_DIVBUF置為NULL。當(dāng)寫入數(shù)據(jù)完成后需要執(zhí)行寫入歸還操作時，除了FREE_BUF_0須要執(zhí)行寫入歸還之外，嵌套中其它FREE_BUF則不執(zhí)行寫入歸還操作。

3)無嵌套接收過程為：接收開始，執(zhí)行寫入借出操作借出個FREE_BUF_0，根據(jù)需求不用嵌套分塊，這時將FREE_BUF_0的USED_LINK_NEXT_DIVBUF置為NULL。當(dāng)寫入數(shù)據(jù)完成后執(zhí)行寫入歸還操作。

4)發(fā)送分塊操作過程為：

①發(fā)送開始，執(zhí)行讀出借出操作借出第一個USE_BUF_0；

②然后讀空其中的數(shù)據(jù)，并在讀出歸還操作前讀出USE_BUF_0中的USED_LINK_NEXT_DIVBUF值；

③最后執(zhí)行在讀出歸還操作。如果USED_LINK_NEXT_DIVBUF值不為空，則利用該值作為下一個USE_BUF，轉(zhuǎn)回到②。如果為空，則結(jié)束。

圖4 嵌套緩存塊Fig.4 Nested cache block

5 接口單射有序公用定長可嵌套分塊緩存

為了節(jié)省及更有效率的利用緩存塊，可將所有接口的各自私有緩存塊公用化。

模型改進(jìn)如下：

1)取消各自的私用緩存區(qū)和FREE_TALBE表，建立公用緩存區(qū)和公用FREE_TABLE表[9]，指示公用緩存中的空緩存塊信息。保留各接口的USED_TABLE表。

2)將各接口的寫入借出和讀出歸還操作合并為對公用FREE_TABLE的寫入和讀出操作。而寫入歸還和讀出歸還操作保留。

3)PORT(T)接收操作變?yōu)椋簣?zhí)行寫入借出操作從公用FREE_TABLE中借出公用FREE__BUF，寫入數(shù)據(jù)后，執(zhí)行寫入歸還操作將其放入PORT(T)的私有T_USED_TABLE中。

4)PORT(T)的對射方發(fā)送操作變?yōu)椋簣?zhí)行讀出借出操作從公用T_USED_TABLE中借出私有USED__BUF，讀空數(shù)據(jù)后，執(zhí)行讀出歸還操作將其放入公用FREE_TABLE中。

6 結(jié)束語

多接口間的數(shù)據(jù)透傳如果采用單字節(jié)的一收一發(fā)，效率不如分塊收發(fā)。尤其是當(dāng)所用的接口芯片中自帶有硬件緩存時，更是如此，因此分塊緩存很有必要。但是在緩存分了塊后，還存在著分塊容量大小的限制，如果要存下的數(shù)據(jù)大于一個分塊或更多，則可嵌套的分塊可以保證接收數(shù)據(jù)序列間的連續(xù)性，特別是在接口多射或是接口還有其它任務(wù)時。

[1]沈建華.ARM嵌入式系統(tǒng)開發(fā)-軟件設(shè)計(jì)與優(yōu)化[M].北京：北京航空航天大學(xué)出版社，2005.

[2]Reek K A.C和指針[M].北京：人民郵電出版社，2008.

[3]趙亮，候國銳.單片機(jī)C語言編程與實(shí)例[M].北京：人民郵電出版社，2003.

[4]譚浩強(qiáng).C程序設(shè)計(jì)[M].北京：清華大學(xué)出版社，1991.

[5]周立功.ARM嵌入式系統(tǒng)基礎(chǔ)教程[M].北京:北京航空航天大學(xué)出版社,2005.

[6]Labrosse J J.嵌入式實(shí)時操作系統(tǒng)μC/OS-II[[M].2版.邵貝貝，等譯.北京：北京航空航天大學(xué)出版社，2005.

[7]沈建華.ARM處理器與嵌入式系統(tǒng)[J].單片機(jī)與嵌入式系統(tǒng)應(yīng)用，2010(11):5-7.SHEN Jian-hua.ARM processors and embedded systems[J].Microcontroller and Embedded Systems，2010(11):5-7.

[8]Linden P V D.C專家編程[M].北京：人民郵電出版社,2008.

[9]施先旺，王鵬武.發(fā)動機(jī)工況實(shí)時調(diào)節(jié)軟件設(shè)計(jì)[J].火箭推進(jìn)，2012（5）：70-76.SHI Xian-wang,WANG Peng-wu.Design of real-time regulation software for engine power[J].Journal of Rocket Propulsion,2012（5）：70-76.