静态链表在通信消息队列的应用——基于嵌入式项目开发

谭家兴

(长江工程职业技术学院，湖北武汉430212)

1 链表和队列

链表是一种常见的重要的数据结构.链表可分为静态链表和动态链表.静态链表的“静态”二字是指内存的来源为静态内存，也就是说，静态链表的空间是事先走义的.在C语言中，静态链表是用数组实现，其存储结构是顺序，其物理地址是连续的.而动态链表是动态申请临时开辟的内存空间，所以每个节点的物理地址不连续，要通过指针来顺序访问.

队列(Queue)是只允许在一端进行插入，而在另一端进行删除的运算受限的线性表［1］.

(1)允许删除的一端称为队头(Front).

(2)允许插入的一端称为队尾(Rear).

(3)当队列中没有元素时称为空队列.

(4)队列亦称作先进先出(First In First Out)的线性表，简称为FIFO表.

队列的修改是依先进先出的原则进行的.新来的成员总是加入队尾(即不允许“加塞”)，每次离开的成员总是队列头上的(不允许中途离队)，即当前“最老的”成员离队.

2 静态链表实现的消息队列模型

消息队列机制属于消息机制的一种，也具有队列的特性，主要用来实现线程间少量数据的传输，是一种间接的通信方式，即发送方往消息队列发送消息，而接受方进行选择性的接受.消息队列中的消息是指内存空间中一段长度可变的缓冲区，其长度和内容均可由用户定义，而对于操作系统而言所有的消息都是字节流，既没有确切的格式也没有特定的含义，对消息的解析是通过应用来完成的，应用根据自己定义的消息格式，将消息解释成为特定的含义，如某种类型的数据、指针或空，鉴于这种通信方式的灵活性、安全性和高效性，并且任务间通常需要传递的数据信息量不大，因此消息队列机制能够很好的满足嵌入式项目开发的要求.

消息队列可以由链表、数组或静态链表来实现，这几种实现方式各有特点.用链表实现消息队列，能随时对消息的插入和删除，同时可以节省大量的内存，但是比较耗费时间，这是因为程序中的各个任务创建消息非常频繁，每次消息创建都要在运行期间向操作系统申请动态分配内存，而数组在定义时分配的内存空间则在编译时就已经确定了.用数组实现消息队列，不方便随时进行消息的插入和删除，且需要消耗较大的内存，但可以节省时间.随着嵌入式芯片的内存的增大，因此在消息队列地设计时结合了以上两种方式的优点，采用了静态链表进行消息队列的设计，即在一开始就定义了数组中数据的类型和数组的大小，并在消息体的设计中增加对下一条消息的索引，实现在消息队列上对消息能够方便的插入和删除.

消息队列模型的设计包括两个方面，首先需要设计消息结构体，消息结构体包括消息的类型、优先级、名称和参数，其次需要设计消息队列，消息队列包括首尾消息的索引、消息队列的长度，并在消息体的基础上增加对下一条消息的索引.下图是本文设计的用静态链表实现的消息队列模型［2］:

图1 静态链表实现的消息队列模型Fig.1 Message queuing model base on static chain

3 消息队列的实现

消息队列机制需要为任务间通信提供两个基本的操作:send操作，用来向消息队列发送一条消息;receive操作，用来从消息队列中接受一条消息.本文设计了消息的发送包和接受包.它们的具体实现如下［3］:

消息的发送包包括消息的优先级、消息的名称以及消息需要传递的参数.其中消息的优先级分为五级，数值越小代表其优先级越高.

消息的接收包包含所要接收的发送包和一个任务的回复名称.其中消息的发送任务名称是由消息的发送方式所引入的，本文中消息的发送方式有两种:一种是无返回的发送，此时任务的回复名称被设置为空;另外一种是有返回的发送，即接受消息的任务在完成消息的处理后需要向该消息的发送任务返回消息的处理结果，此时这个任务的回复名称会被设置为该消息的发送任务名称.

消息队列通过静态链表来构建.即在消息的接受包的基础上增加了对下一条消息的索引，实现数组的链式结构.静态链表实现过程如下:首先定义一个长度为两百，数据类型为消息链表的静态数组，并对其进行初始化，项目在运行期间，所有的消息都保存在这个数组中，数组中的消息按照任务的类型进行分类，对每类消息都用该类首尾消息索引，并计算它们的长度，这样每类消息都形成独立的链表，成为一个子消息队列.实现代码如下:

在嵌入式应用中通常有自己的子消息队列，子消息队列能够实现对本类型的消息进行统一的删除或读取工作，这样可以方便对消息队列的维护和管理.消息按照任务分类可以分为以下几种［4］:

这些按照任务分类的子消息队列之间主要是并列的关系，即各个需要进行通信的任务都拥有自己的消息队列，并根据消息的需求进行相应处理.同时子消息队列之间也有嵌套的关系，比如在系统任务消息队列的管理中［5］，会进行系统消息的处理函数，但处理过程需要依靠其它任务来完成，因此会向其它任务模块发送消息并使之进行相应处理.

［1］安训国.数据结构［M］.大连:大连理工大学出版社，2009.

［2］偶建磊，田大庆，茅志宏.一种基于UDP电子政务消息传输的新技术［J］.信息技术.2014，(1):124-127.

［3］刘加海.C语言程序设计［M］.北京:科学出版社，2010.

［4］黄建灯.C程序设计［M］.广州:华南理工大学出版社.2014.

［5］胡志辉，牛德雄，许国庆.消息队列管理在信息交换中的研究［J］.计算机与现代化，2009，161(1):28-31.