一种新的队列结构形式-双头共享队列

王 芃，孙 旺，许 硕

（中国铁道科学研究院 通信信号研究所 ，北京 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

王 芃，助理研究员；孙 旺，助理研究员。