丁 远

（1.中煤科工集团沈阳研究院有限公司，辽宁 抚顺113122；2.煤矿安全技术国家重点实验室，辽宁 抚顺113122）

数据缓存队列是为了协调不同吞吐速度设备之间数据通信而采用的技术[1]。在基于无主、多主通信方式煤矿监控系统[2]中，当同一分站下的多台传感器同一时间内向分站发送数据，会导致监控分站软件结构中数据处理模块短时间内处理多帧数据，由于数据处理模块需要完成解包、解析、封包上传的工作，导致因为数据接收与数据处理速度不匹配造成的数据包丢失问题。常用的环形队列策略使用之前需要预设固定尺寸的队列空间[3]，另外在环形队列写空间满时，接收的新数据因为队列不能实时扩展，所以不能及时进入缓存需丢弃，导致数据丢失，针对此问题参考了生产者/消费者模型，设计了双缓存队列结构，解决不可动态扩展、数据溢出丢失问题。此外，为了提升监控分站运行速度，监控分站软件中使用多线程技术，缓存队列被多个线程读写，各个线程之间存在竞争资源问题，如果考虑不全，会出现饥饿现象，严重的会导致死锁发生，为了避免此问题出现，将多线程安全技术融入到数据处理队列中，解决资源竞争。

1 双缓存队列与线程安全设计

1.1 基础队列原理

数据结构理论定义了一种“一端入一端出”的先进先出（FIFO）线性表称为队列[4]，数据插入端为队尾,数据读取端为队头。线性表在物理结构上分为顺序存储和链式存储，顺序存储在物理层上可以看做对1 个大数组操作，链式存储则是对分散内存的操作。

顺序存储结构队列在创建之初需要向内存申请1 块连续存储空间，队列的操作实际是对这个内存空间的操作，因为内存在队列创建之初大小已经固定，所以当进队数据量大于内存长度时，会出现队列满，无法进队，丢弃该数据，此现象称为假溢出。算法设计者常将顺序结构的队列头、尾连接，并且设计了头、尾指针以及相关算法，使队列从结构上看形成环形，称为环形队列（有关环形队列原理本文不多叙述），但是环形队列中如写速度大于读速度会出现覆盖现象。相对于顺序存储固定内存，链式存储可在插入之前现申请内存，可以在物理结构上解决因队列长度引起的问题，但是链式存储存在内存碎片、增删改查等操作的时间复杂度远大于顺序存储等问题，鉴于此本文所设计的双缓存技术建立在链式存储结构上，融入环形队列优点，避免过多内存碎片产生基础上实现队列空间充裕，数据不丢失。

1.2 双缓存队列设计

由数据缓存队列与数据溢出队列构成的双缓存队列[5]中，数据缓存队列负责实现基于生产者/消费者模型算法完成数据源输入与源数据处理模块之间数据通信功能，其数据结构采用链式队列组建成单链表环形结构。此数据结构结合了顺序存储、链式存储各自优点，既具有链式存储可动态申请内存实现队列空间动态扩展，又避免了因频繁申请释放内存带来的内存碎片。数据溢出队列存储当数据缓存队列中入队数据大于出队数据时的队列溢出数据，当数据缓存队列空间足够时，同步溢出队列中数据到数据缓存队列。溢出队列属于数据缓存队列的补充，使用频率较少，使用时申请内存，同步数据后释放空间，单链表模式。

双缓存队列的数据结构分为队列整体结构以及队列节点结构，其中队列节点结构包含于队列整体结构中，做队列整体结构的节点域。队列整体结构由头指针head、尾指针rear 以及节点计数器cnt 组成，head 与rear 用于进行入队、出队，cnt 记录当前入队数量，因为队列中的节点是可复用的，无法通过数据域本身自带信息判断是否可写入，在队列被并发访问时，cnt 不等于0 时，代表队列不为空，有数据可读；当cnt 小于队列预设最大节点数量时，代表有空余空间可以入队，因此可以通过对变量cnt 操作来保证出队、入队安全型。节点结构由数据域data、指针域next 构成。

缓存队列的数据结构图如图1。

图1 缓存队列数据结构图Fig.1 data structure of cache queue

1.3 多线程安全设计

为了同时与多路传感器进行数据通信，系统采用了多线程技术[6]实现系统并发执行。但是多线程对缓存队列同一时间操作会产生异常发生，如1 个线程或多个线程同时对队列进行入队操作时，如果不进行临界区保护，会导致不可预知的数据损坏，发生hardfault 中断，系统崩溃；另外如果1 个线程一直占用临界区，导致其他资源无法访问，会导致其他线程发生饥饿[7]现象。因此多线程访问临界资源时，必须进行同步控制。常用方法为信号量、条件锁、互斥量等。

综合各个方法优势，考虑每个方法可能导致的问题，设计如下方法：

1）条件不满足时，挂起线程。

2）条件满足时通过信号量释放通知进程访问临界区。

3）条件等待是线程间同步的一种手段，如果只有1 个线程，条件不满足，一直等下去都不会满足，所以必须要有1 个线程通过某些操作，改变共享变量，使原先不满足的条件变得满足，并且友好的通知等待在条件变量上的线程。

4）条件不会无缘无故的突然变得满足了，必然会牵扯到共享数据的变化。所以一定要用互斥锁来保护。没有互斥锁就无法安全的获取和修改共享数据。

2 算法设计

2.1 出入队

入队操作时首先判断缓冲队列是否满队，如果队列满，将待入队数据插入溢出队列，否则插入缓冲队列。当缓冲队列非满并且溢出队列为空，通过对cnt 值确定是否回收缓冲队列冗余空间；若缓冲队列非满并且溢出队列非空，将溢出队列数据同步到缓冲队列中。出队时需要先判断队列是否为空，若非空说明队列有数据可读。在预设长度为L 的队列中，保持head 与read 的相对空间为2 个节点数据长度，每入队1 个数据head 循环加1，每读出1 个数据tail 循环加1。读写数据时，读写指针以不对的速度环绕着缓冲队列旋转，head 在前tail 在后。在数据输入的初始阶段，头指针更新。如果指针指向缓冲区末尾部分，它就会重新回到初始位置，当写入抵达尾指针，就会停止，在此，缓冲区的数据量已达到顶峰，数据无法录入。当其指向数据区尾端，且发送工作结束，进行位置刷新；假使其抵达缓冲区尾部，那么指针就会回到初始位置，一旦与头指针相遇，就表明数据传输工作完成。队列操作示意图如图2。

2.2 数据同步与冗余回收

定义数据缓存对列为Qbuf, 溢出队列为Qof,将Qbuf 的rear 和rear-＞next 分别队列Qof 的head 与rear，为了获取Qbuf 的队尾节点地址，需要将Qbuf-＞rear-＞next 指向Qof 的rear，Qbuf-＞rear 指向Qof-＞head。为了实现多线程安全，同步过程避免缓存队列各个数据节点次序打乱，在同步数据之前需确保缓存队列中至少有1 个节点可写入数据。当Qbuf 队列满队时进行数据同步，根据Qbuf-＞rear 的位置可以判断有队列数据要出队，如果此时暂停入队操作将Qof 数据同步到Qbuf 队尾后进行出队操作，Qbuf-＞head 指针将异常偏移，导致缓存队列节点数据间顺序错乱。

当缓存队列节点cnt 不等于0 时，缓存队列存在冗余节点，可对Qbuf 进行冗余空间回收[8]，常用算法为申请临时节点指针t，并且t 指向待回收节点，改变rear 指针指向Qbuf-＞rear-＞next-＞next，释放t，并且cnt 减1。在回收操作之前，要保证缓冲队列至少有2 个可以写入的空间，如果只有1 个节点可以写入数据，此时进行回收空间操作，根据当前的head 位置可知Qbuf 正在进行出队操作，如果此时暂停，将t 指向待回收节点，并且释放。当恢复出队操作时，由于原待出队节点已经释放，Qbuf-＞head 已经下移，该指针域未知，导致指针越界,这是类似多路数据采集与处理系统[9]中最为关键严重的问题。

3 试验验证

以沈阳研究院KJ1177X 煤矿监控系统为平台，该系统是全国首家符合AQ 6201—2019 行业标准[10]的煤矿监控系统，该系统下的每台监控分站可接32个传感器。在实验室采用与现场井工矿一致的线缆布置搭建采煤工作面环境后，其中传感器以甲烷传感器，风速风向传感器，开停传感器为主，并且接入少于5 台断电器后，配置监控分站为采煤面煤与瓦斯突出断电与报警模式后进行超限断电、故障断线、突出预警实验以及稳定性试验。使用Wireshark 工具在PC 端进行以太网异常数据监测，在监控分站软件中的接收传感器数据以及上传数据接口中分别打印相关传感器数据，人工随机调整传感器数据以及制造传感器断线故障，观察相关断电器是否执行闭锁操作，并且监控PC 与监控分站端所对应的数据状态是否一致。在闭锁试验后，系统进行不间断40 d 稳定试验，查看监测软件，无异常中断与数据，并且在此期间无监控分站上传的传感器通信中断指令，表明监控分站到传感器之间无数据丢失发生。

4 结 语

针对煤矿监控系统中，监控分站既需要处理中心站软件的指令，又要与大量传感器进行数据通信，如果处理传感器数据不及时或数据丢失可能判断传感器通信故障，导致相关联断电器断电的问题;设计了带有多线程安全的双数据缓存技术的缓存队列,监控分站先将传感器数据帧插入队列存放后，再进行解析处理，另外考虑避免饥饿或死锁发生。实际应用证明该数据缓存队列软件架构清晰，占用内存小，易实现，提升了系统数据处理能力，解决了分站对中心站指令、传感器数据处理不及时、丢失等问题。