一種新的隊(duì)列結(jié)構(gòu)形式-雙頭共享隊(duì)列

王 芃，孫 旺，許 碩

（中國鐵道科學(xué)研究院 通信信號(hào)研究所 ，北京 100081）

一種新的隊(duì)列結(jié)構(gòu)形式-雙頭共享隊(duì)列

王 芃，孫 旺，許 碩

（中國鐵道科學(xué)研究院 通信信號(hào)研究所 ，北京 100081）

通過對(duì)鐵路高安全高可靠的應(yīng)用環(huán)境下的雙CPU結(jié)構(gòu)進(jìn)行分析，發(fā)現(xiàn)當(dāng)兩顆CPU需要共享數(shù)據(jù)時(shí)，由于現(xiàn)有簡單隊(duì)列具有同一數(shù)據(jù)只能夠離隊(duì)一次的特點(diǎn)，即便隊(duì)列控制權(quán)完全被兩顆CPU共享，依然不能實(shí)現(xiàn)對(duì)隊(duì)列中的數(shù)據(jù)的共享。通過對(duì)這一缺陷成因的分析，本文對(duì)簡單隊(duì)列有針對(duì)性的做出了改進(jìn)，提出了雙頭共享隊(duì)列的方案，該方案在保持隊(duì)列順序特性不變的情況下，有效解決了簡單隊(duì)列中數(shù)據(jù)僅能離隊(duì)一次的問題，使之能夠適應(yīng)雙CPU結(jié)構(gòu)的應(yīng)用場景，提高了數(shù)據(jù)使用效率。

數(shù)據(jù)結(jié)構(gòu)；隊(duì)列；雙CPU系統(tǒng) ；雙口RAM

數(shù)據(jù)結(jié)構(gòu)是由數(shù)據(jù)元素依據(jù)某種邏輯聯(lián)系組織起來的。對(duì)數(shù)據(jù)元素間邏輯關(guān)系的描述稱為數(shù)據(jù)的邏輯結(jié)構(gòu)。數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)是數(shù)據(jù)結(jié)構(gòu)的實(shí)現(xiàn)形式。長期的實(shí)踐經(jīng)驗(yàn)表明，系統(tǒng)實(shí)現(xiàn)的困難程度和系統(tǒng)構(gòu)造的質(zhì)量都嚴(yán)重的依賴于所選擇的數(shù)據(jù)結(jié)構(gòu)的優(yōu)劣。在通常情況下，算法是在確定的數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)上設(shè)計(jì)的。同時(shí)，好的數(shù)據(jù)結(jié)構(gòu)也能夠簡化算法的復(fù)雜度?？傊x擇合適的數(shù)據(jù)結(jié)構(gòu)對(duì)于軟件設(shè)計(jì)是非常重要的。

1 鐵路高安全高可靠場景下的應(yīng)用需求

鐵路信號(hào)系統(tǒng)是強(qiáng)調(diào)高安全性與高可靠性的系統(tǒng)，為了達(dá)到較高的安全性和可靠性經(jīng)常需要使用2顆CPU相互配合來完成特定功能。常用結(jié)構(gòu)如圖1所示。

基本的工作模式為：

（1）CPUA接收A路輸入，放入雙口RAM（DPRAM）中；

（2）CPUB接收B路輸入，放入雙口RAM（DPRAM）中；

（3）CPUA和CPUB共享DPRAM中的A路輸入和B路輸入；

（4）通過對(duì)A路輸入和B路輸入的計(jì)算，分別產(chǎn)生完全相同的A路輸出和B路輸出。

兩路輸入應(yīng)具有如下特點(diǎn)：

（1）順序性：即先入先出，系統(tǒng)應(yīng)為A路和B路輸入中的先到數(shù)據(jù)先產(chǎn)生輸出；

（2）一致性：A路輸入和B路輸入為冗余關(guān)系，但是A路輸出和B路輸出要保持一致。

在實(shí)際應(yīng)用中，可以利用雙CPU構(gòu)架，將2顆CPU的計(jì)算結(jié)果進(jìn)行比較，實(shí)現(xiàn)雙CPU校核，即2乘2取2結(jié)構(gòu)中的取2比較功能，提高系統(tǒng)的安全性。也可以設(shè)計(jì)2顆CPU分別處理互為冗余關(guān)系的A網(wǎng)與B網(wǎng)數(shù)據(jù)，并對(duì)兩路數(shù)據(jù)進(jìn)行綜合冗余處理，來提高系統(tǒng)的可靠性。甚至可以使用2顆CPU分別接收不同屬性的數(shù)據(jù)，在共享數(shù)據(jù)基礎(chǔ)上進(jìn)行邏輯運(yùn)算，最后得到一個(gè)綜合輸出，以達(dá)到分散功能，提高系統(tǒng)可靠性的目的?？傊@種雙CPU+雙口RAM的結(jié)構(gòu)在強(qiáng)調(diào)安全性與可靠性的系統(tǒng)中應(yīng)用十分廣泛。但是雙口RAM作為CPU的外置存儲(chǔ)器，其可選擇的容量會(huì)受到諸如CPU對(duì)外置存儲(chǔ)器尋址空間、單芯片雙口RAM容量、電路板布置等諸多限制，因此，如何既能夠保障雙CPU系統(tǒng)信息交換的安全、高效，又能夠盡量節(jié)約雙口RAM資源就成了我們?cè)O(shè)計(jì)軟件，選擇數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)時(shí)需要重點(diǎn)考慮的問題。

2 經(jīng)典的簡單隊(duì)列

通過以上對(duì)這種具有雙CPU結(jié)構(gòu)特征系統(tǒng)的分析，如何選擇合適的數(shù)據(jù)結(jié)構(gòu)，實(shí)現(xiàn)在DPRAM中存放和使用數(shù)據(jù)來滿足數(shù)據(jù)輸出的順序性和一致性是這種結(jié)構(gòu)軟件設(shè)計(jì)的核心問題。眾所周知，隊(duì)列是一種能夠很好保持?jǐn)?shù)據(jù)順序性的數(shù)據(jù)結(jié)構(gòu)，它只允許在表的頭部（front）進(jìn)行刪除操作，而在表的尾部（rear）進(jìn)行插入操作。隊(duì)列是按照“先進(jìn)先出”或“后進(jìn)后出”的原則組織數(shù)據(jù)的。如果能夠在DPRAM中構(gòu)建一個(gè)隊(duì)列，被CPUA和CPUB共享，就可以滿足雙CPU系統(tǒng)對(duì)輸出數(shù)據(jù)順序性和一致性的要求。其基本結(jié)構(gòu)如圖2所示，隊(duì)列結(jié)構(gòu)形式如圖3所示。

圖2 DPRAM中的共享隊(duì)列

圖3 簡單隊(duì)列結(jié)構(gòu)圖

圖3 中Head為隊(duì)頭，Tail為隊(duì)尾，Length為隊(duì)列長度，頭尾標(biāo)志均按逆時(shí)針（或順時(shí)針）方向移動(dòng)。當(dāng)隊(duì)頭與隊(duì)尾重合時(shí)隊(duì)列為空，當(dāng)下一個(gè)隊(duì)尾位置與隊(duì)頭重合時(shí)隊(duì)列為滿。這種一頭一尾的隊(duì)列，我們稱之為簡單隊(duì)列，其基本操作方法如下：

Bool Isfull()/*判斷隊(duì)列是否滿*/

{

If((Tail+1)%Length==Head) { Return True;

}else{ Return False；}

}

Bool IsEmpty()/*判斷隊(duì)列是否為空*/

{

If((Head)% Length ==Tail) { Return True; }else{ Return False；}

}

Void InsertQueue(Data) /*在隊(duì)列中插入一個(gè)數(shù)據(jù)*/

{

if(!Isfull()){Queue[Tail]=Data; Tail=(Tail+1) %Length;}

}

Void GetQueue(Data) /*從隊(duì)列中提取一個(gè)數(shù)據(jù)*/

{

If(!IsEmpty()){Data= Queue[Head]; Head= (Head+1)%Length;}

}

常見的簡單隊(duì)列具有如下特點(diǎn)：

（1）隊(duì)尾入隊(duì)，隊(duì)頭離隊(duì)。新到的成員總是進(jìn)入隊(duì)尾（不許“加塞”），每次都是處于隊(duì)頭的成員離開隊(duì)列（不許中途離隊(duì)）。

（2）先進(jìn)者先出，后進(jìn)者后出，很好地保持了數(shù)據(jù)的順序結(jié)構(gòu)。

（3）只有處于頭尾之間（即隊(duì)列中）的數(shù)據(jù)處于管理之下，而且頭尾標(biāo)志只能向一個(gè)方向（順時(shí)針或逆時(shí)針）循環(huán)移動(dòng)，數(shù)據(jù)一旦離隊(duì)，將不可能再次被隊(duì)列管理。如圖3所示，當(dāng)CPUA取走Cell[0]后，隊(duì)頭位置就會(huì)被移動(dòng)到數(shù)據(jù)Cell[1]上，此時(shí)對(duì)于CPUB來說將不可能再取走Cell[0]，只能取走Cell[1]。依次類推，當(dāng)Cell[3]被某一CPU取走后，另一CPU將會(huì)認(rèn)為隊(duì)列空。由此可見雖然隊(duì)列被CPUA和CPUB共享，但是實(shí)際上隊(duì)列中的數(shù)據(jù)卻沒有被共享。

實(shí)踐證明當(dāng)這種隊(duì)列僅被一個(gè)對(duì)象控制時(shí)，具有很好的順序結(jié)構(gòu)，但是當(dāng)兩個(gè)控制對(duì)象共享一個(gè)簡單隊(duì)列時(shí)就會(huì)出現(xiàn)被一個(gè)控制對(duì)象取走的數(shù)據(jù)將不可能被第二個(gè)控制對(duì)象再次取走（同一數(shù)據(jù)不能兩次離隊(duì)）的現(xiàn)象。在事實(shí)上形成了兩個(gè)控制對(duì)象爭搶（而非共享）隊(duì)列數(shù)據(jù)的情形。因此這種簡單隊(duì)列只適用于單個(gè)控制對(duì)象的情形，而不適用于共享隊(duì)列的情形。

3 對(duì)簡單隊(duì)列的改進(jìn)-雙頭共享隊(duì)列

新的雙頭共享隊(duì)列在簡單隊(duì)列一頭一尾的結(jié)構(gòu)基礎(chǔ)上增加了一個(gè)頭部標(biāo)志，變?yōu)閮深^一尾的結(jié)構(gòu)。該隊(duì)列構(gòu)建于兩顆CPU之間的DPRAM中,兩顆CPU分別維護(hù)隊(duì)列的兩個(gè)頭部標(biāo)志，隊(duì)列尾部標(biāo)志則被兩顆CPU共同維護(hù)。其插入數(shù)據(jù)和提取數(shù)據(jù)操作原理與簡單隊(duì)列一致，即隊(duì)尾插入隊(duì)頭取出。與簡單隊(duì)列的區(qū)別在于：

（1）每一個(gè)隊(duì)列有兩個(gè)隊(duì)頭，兩顆CPU各控制一個(gè)。即CPUA控制Head1，CPUB控制Head2，隊(duì)尾則被兩顆CPU共享，結(jié)構(gòu)如圖4所示。

（2）隊(duì)列判滿條件分2種情況

a.當(dāng)兩個(gè)隊(duì)頭均處于隊(duì)尾一側(cè)時(shí)，判滿條件為下一個(gè)隊(duì)尾等于最小的隊(duì)頭。即(Tail+1) % Length == Min(Head1,Head2)如圖5 （情形1）所示。

b.當(dāng)個(gè)兩個(gè)隊(duì)頭分別位于隊(duì)尾兩側(cè)時(shí)，判滿條件為下一個(gè)隊(duì)尾等于最大的隊(duì)頭。即(Tail+1) % Length == Max(Head1,Head2) 如圖5 情形2所示。

（3）兩顆CPU可分別列用本地控制的隊(duì)頭對(duì)隊(duì)列判空，即(Head1)%Length==Tail或 (Head2)%Length==Tail，如圖6、圖7所示。

圖4 雙頭共享隊(duì)列結(jié)構(gòu)圖

圖5 雙頭共享隊(duì)列判滿頭尾相對(duì)位置圖

圖6 雙頭共享隊(duì)列CPUA判空頭尾相對(duì)位置圖

圖7 雙頭共享隊(duì)列CPUB判空頭尾相對(duì)位置圖

這種兩頭一尾的隊(duì)列，為雙頭共享隊(duì)列?；静僮鞣椒ㄈ缦拢?/p>

Bool Isfull()/*判斷隊(duì)列是否滿*/

{

If(Tail＞ Max(Head1,Head2)|| Tail＜Mi(Head1,Head2))

If(((Tail+1) %Length )== Min(Head1,Head2))){ Return True;}else{ Return False；}

Else

If(((Tail+1) %Length )== Max(Head1,Head2))) { Return True;}else{ Return False；}

}

Bool CPUA_IsEmpty()/*CPUA判斷隊(duì)列是否為空*/

{

If((Head1)%Length==Tail) { Return True;}else{ Return False；}

}

Bool CPUB_IsEmpty()/*CPUB判斷隊(duì)列是否為空*/

{

If((Head2)%Length==Tail) { Return True; }else{ Return False；}

}

Void CPUA_GetQueue(Data) /*CPUA從隊(duì)列中提取一個(gè)數(shù)據(jù)*/

{

If(!CPUA_IsEmpty()){Data= Queue[Head1]; Head1=(Head1+1)%Length;}

}

Void CPUB_GetQueue(Data) /*CPUB從隊(duì)列中提取一個(gè)數(shù)據(jù)*/

{

If(!CPUB_IsEmpty()){Data= Queue[Head2]; Head2=( Head2+1)%Length;

}

Void InsertQueue(Data) /*向隊(duì)列中插入一個(gè)數(shù)據(jù)*/

{

If(!Isfull()){Queue[Tail]= Data; Head =(Tail+1)%Length;}

}

通過以上描述可以發(fā)現(xiàn)，在為簡單隊(duì)列增加一個(gè)隊(duì)頭標(biāo)志，并使兩個(gè)隊(duì)頭標(biāo)志分別由2顆CPU維護(hù)后，一個(gè)顯而易見的好處是隊(duì)列中的每一個(gè)數(shù)據(jù)都可以在2顆CPU的控制下分別離隊(duì)兩次了，而且由于只有一個(gè)尾部標(biāo)志，當(dāng)執(zhí)行隊(duì)列插入操作時(shí)，數(shù)據(jù)依然是按照被操作的先后順序進(jìn)入隊(duì)列的，隊(duì)列的空閑容量由最小的隊(duì)頭與隊(duì)尾之間的距離決定。改進(jìn)后的隊(duì)列結(jié)構(gòu)在保持了簡單隊(duì)列順序性的基礎(chǔ)上，賦予了共享單個(gè)隊(duì)列時(shí)其中的數(shù)據(jù)也同時(shí)被雙CPU共享的特性。從而解決了簡單隊(duì)列共享隊(duì)列不能共享數(shù)據(jù)的問題。雙頭共享隊(duì)列與簡單隊(duì)列的異同點(diǎn)如表1所示。

表1 雙頭共享隊(duì)列和簡單隊(duì)列性能比較

4 結(jié)束語

在簡單隊(duì)列中，由于只有一個(gè)隊(duì)頭，數(shù)據(jù)離隊(duì)后隊(duì)頭必須移動(dòng)，所以隊(duì)列中的任意一個(gè)數(shù)據(jù)只能離隊(duì)一次。當(dāng)隊(duì)列被兩個(gè)對(duì)象共享時(shí)，就會(huì)出現(xiàn)數(shù)據(jù)只能被某一個(gè)控制對(duì)象使用的情況，若一定要通過在雙CPU間的雙口RAM中構(gòu)建簡單隊(duì)列來共享兩顆CPU的輸入數(shù)據(jù)，則需要建立4條隊(duì)列，其中，任意一個(gè)CPU需要維護(hù)兩條一樣的隊(duì)列。當(dāng)數(shù)據(jù)到來時(shí)，分別插入兩條隊(duì)列中，提取數(shù)據(jù)時(shí)，一條隊(duì)列供本地CPU使用，另一條隊(duì)列專供系統(tǒng)中另外一顆CPU使用。無疑會(huì)增加存儲(chǔ)空間資源的開銷，而且使得數(shù)據(jù)共享算法非常復(fù)雜。但是，當(dāng)給隊(duì)列增加一個(gè)隊(duì)頭，變成兩個(gè)控制對(duì)象各自維護(hù)一個(gè)隊(duì)頭標(biāo)志后，數(shù)據(jù)離隊(duì)時(shí)只需要移動(dòng)本地控制的隊(duì)頭，而不影響另外一個(gè)控制對(duì)象控制的隊(duì)頭。隊(duì)列中的任意一個(gè)數(shù)據(jù)均可在兩個(gè)控制對(duì)象的控制下離隊(duì)兩次，從而輕松實(shí)現(xiàn)兩顆CPU共享隊(duì)列的功能。由此可見，當(dāng)在雙CPU+雙口RAM這樣結(jié)構(gòu)的系統(tǒng)中使用雙頭共享隊(duì)列將會(huì)比使用簡單隊(duì)列具有更高的存儲(chǔ)空間使用效率，更簡單的數(shù)據(jù)操作流程。

[1]龔舒群，任 煜，陳衛(wèi)衛(wèi). 循環(huán)隊(duì)列中的頭尾指針設(shè)計(jì)[J].現(xiàn)代計(jì)算機(jī)，2007（2）.

[2]蘇德富，鐘 誠.計(jì)算機(jī)算法設(shè)計(jì)與分析[M]. 北京：電子工業(yè)出版社，2005.

[3]李春葆.數(shù)據(jù)結(jié)構(gòu)教程[M]. 北京：清華大學(xué)出版社，2005.

[4]馬海瑛. 數(shù)據(jù)結(jié)構(gòu)中遞歸算法的描述與實(shí)現(xiàn)[J]. 大眾科技，2007（3）.

[5]仇德成. 循環(huán)隊(duì)列隊(duì)空和隊(duì)滿的判定算法[J]. 電腦開發(fā)與應(yīng)用，2005（11）.

責(zé)任編輯 徐侃春

New queue solution-shared queue with two heads

WANG Peng, SUN Wang, XU Shuo
( Signal &Communication Institute, China Academy of Railway Sciences, Beijing 100081, China )

Through the analysis of the dual CPU structure, which was commonly used in the high safety and reliability railway application scenarios, it was found that even if the queue control right was totally shared by two CPUs, because the existing characteristic was that the same data could be only popped out once, the sharing of the data in the queue still couldn’t be implemented. By analyzing the cause of this defect, this paper made improvement to the simple queue, and proposed a solution with two heads in one shared queue. This solution could not only keep the queue order characteristics, but also effectively solve the problem that the same data could be only popped out once, which made the queue structure more adapted to the application scene of dual CPU, and improved the use eff i ciency of data.

data structure; queue; dual CPU; dual port RAM

U284∶TP39

A

1005-8451（2014）11-0051-04

2014-05-19

王 芃，助理研究員；孫 旺，助理研究員。