一種新的隊列結構形式-雙頭共享隊列

王 芃，孫 旺，許 碩

（中國鐵道科學研究院 通信信號研究所 ，北京 100081）

一種新的隊列結構形式-雙頭共享隊列

王 芃，孫 旺，許 碩

（中國鐵道科學研究院 通信信號研究所 ，北京 100081）

通過對鐵路高安全高可靠的應用環境下的雙CPU結構進行分析，發現當兩顆CPU需要共享數據時，由于現有簡單隊列具有同一數據只能夠離隊一次的特點，即便隊列控制權完全被兩顆CPU共享，依然不能實現對隊列中的數據的共享。通過對這一缺陷成因的分析，本文對簡單隊列有針對性的做出了改進，提出了雙頭共享隊列的方案，該方案在保持隊列順序特性不變的情況下，有效解決了簡單隊列中數據僅能離隊一次的問題，使之能夠適應雙CPU結構的應用場景，提高了數據使用效率。

數據結構；隊列；雙CPU系統 ；雙口RAM

數據結構是由數據元素依據某種邏輯聯系組織起來的。對數據元素間邏輯關系的描述稱為數據的邏輯結構。數據的存儲結構是數據結構的實現形式。長期的實踐經驗表明，系統實現的困難程度和系統構造的質量都嚴重的依賴于所選擇的數據結構的優劣。在通常情況下，算法是在確定的數據結構基礎上設計的。同時，好的數據結構也能夠簡化算法的復雜度。總之，選擇合適的數據結構對于軟件設計是非常重要的。

1 鐵路高安全高可靠場景下的應用需求

鐵路信號系統是強調高安全性與高可靠性的系統，為了達到較高的安全性和可靠性經常需要使用2顆CPU相互配合來完成特定功能。常用結構如圖1所示。

基本的工作模式為：

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

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

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

（4）通過對A路輸入和B路輸入的計算，分別產生完全相同的A路輸出和B路輸出。

兩路輸入應具有如下特點：

（1）順序性：即先入先出，系統應為A路和B路輸入中的先到數據先產生輸出；

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

在實際應用中，可以利用雙CPU構架，將2顆CPU的計算結果進行比較，實現雙CPU校核，即2乘2取2結構中的取2比較功能，提高系統的安全性。也可以設計2顆CPU分別處理互為冗余關系的A網與B網數據，并對兩路數據進行綜合冗余處理，來提高系統的可靠性。甚至可以使用2顆CPU分別接收不同屬性的數據，在共享數據基礎上進行邏輯運算，最后得到一個綜合輸出，以達到分散功能，提高系統可靠性的目的。總之，這種雙CPU+雙口RAM的結構在強調安全性與可靠性的系統中應用十分廣泛。但是雙口RAM作為CPU的外置存儲器，其可選擇的容量會受到諸如CPU對外置存儲器尋址空間、單芯片雙口RAM容量、電路板布置等諸多限制，因此，如何既能夠保障雙CPU系統信息交換的安全、高效，又能夠盡量節約雙口RAM資源就成了我們設計軟件，選擇數據存儲結構時需要重點考慮的問題。

2 經典的簡單隊列

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

圖2 DPRAM中的共享隊列

圖3 簡單隊列結構圖

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

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

{

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

}else{ Return False；}

}

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

{

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

}

Void InsertQueue(Data) /*在隊列中插入一個數據*/

{

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

}

Void GetQueue(Data) /*從隊列中提取一個數據*/

{

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

}

常見的簡單隊列具有如下特點：

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

（2）先進者先出，后進者后出，很好地保持了數據的順序結構。

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

實踐證明當這種隊列僅被一個對象控制時，具有很好的順序結構，但是當兩個控制對象共享一個簡單隊列時就會出現被一個控制對象取走的數據將不可能被第二個控制對象再次取走（同一數據不能兩次離隊）的現象。在事實上形成了兩個控制對象爭搶（而非共享）隊列數據的情形。因此這種簡單隊列只適用于單個控制對象的情形，而不適用于共享隊列的情形。

3 對簡單隊列的改進-雙頭共享隊列

新的雙頭共享隊列在簡單隊列一頭一尾的結構基礎上增加了一個頭部標志，變為兩頭一尾的結構。該隊列構建于兩顆CPU之間的DPRAM中,兩顆CPU分別維護隊列的兩個頭部標志，隊列尾部標志則被兩顆CPU共同維護。其插入數據和提取數據操作原理與簡單隊列一致，即隊尾插入隊頭取出。與簡單隊列的區別在于：

（1）每一個隊列有兩個隊頭，兩顆CPU各控制一個。即CPUA控制Head1，CPUB控制Head2，隊尾則被兩顆CPU共享，結構如圖4所示。

（2）隊列判滿條件分2種情況

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

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

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

圖4 雙頭共享隊列結構圖

圖5 雙頭共享隊列判滿頭尾相對位置圖

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

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

這種兩頭一尾的隊列，為雙頭共享隊列。基本操作方法如下：

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

{

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判斷隊列是否為空*/

{

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

}

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

{

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

}

Void CPUA_GetQueue(Data) /*CPUA從隊列中提取一個數據*/

{

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

}

Void CPUB_GetQueue(Data) /*CPUB從隊列中提取一個數據*/

{

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

}

Void InsertQueue(Data) /*向隊列中插入一個數據*/

{

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

}

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

表1 雙頭共享隊列和簡單隊列性能比較

4 結束語

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

[1]龔舒群，任 煜，陳衛衛. 循環隊列中的頭尾指針設計[J].現代計算機，2007（2）.

[2]蘇德富，鐘 誠.計算機算法設計與分析[M]. 北京：電子工業出版社，2005.

[3]李春葆.數據結構教程[M]. 北京：清華大學出版社，2005.

[4]馬海瑛. 數據結構中遞歸算法的描述與實現[J]. 大眾科技，2007（3）.

[5]仇德成. 循環隊列隊空和隊滿的判定算法[J]. 電腦開發與應用，2005（11）.

責任編輯 徐侃春

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

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