一种新的环形缓冲区设计与实现方法

杨凯乔

摘要：针对环形缓冲区传统实现中判断“满”状态采用保留缓冲区元素或者引入缓冲区有效数据变量导致的缓冲区空间利用率较低问题，本文提出了一种新的不引入计数变量、不存在内存浪费的缓冲区实现方法，其核心思想是借助于读写索引之间的关系，使得读写索引一直递增而不清零，直到递增溢出后自动清零，该读写索引的差值就是缓冲区有效数据的个数。基于以上原理给出了不可覆盖和可覆盖环形缓冲区的实现过程，缓冲区“满”状态时，内存利用率为100%，并且仿真实验表明代码执行效率优于传统方法。

关键词：环形缓冲区；嵌入式系统；“满”状态；读写索引

中图分类号：TP212.9 文献标识码：A

文章编号：1009-3044（2019）09-0055-04

Abstract： According to problem involving in the ring buffer in the traditional implementation judgment "full" state with retaining an element without introducing cache data or effective number of variables makes utilization rate of the buffer space lower， a new the realization method of a new buffer is proposed in this paper without counter variables introduced and memory waste. The main ideas is based on the relationship between reading and writing index， the read-write index always increase until automatic reset when overflow. The number of valid data in buffer is read and write index difference. Based on the above principle gives the realization process for the ring buffer override or not override. The method of memory utilization rate is 100% when the buffer is in "full" state. The simulation experiment shows that the code execution efficiency is better than the traditional method.

Key words： Ring Buffer； Embedded Systems； "Full" State； Read and write index

環形缓冲区在嵌入式系统软件设计中是一种很重要的数据结构[1-4]，也可由硬件实现[5][6]，广泛应用到数据产生速率和数据处理速率不匹配的场合 [7-10]。在设计上一般采用先入先出（FIFO）的方式，可以采用动态分配内存或预先静态分配内存的方式，由于嵌入式系统的内存资源非常有限，动态内存管理在多数情况下的运行效率和内存利用率都非常低，特别是频繁进行小容量内存单元的分配释放，会造成内存碎片，故多采用静态分配的方式[11] [12]。

用静态内存分配实现环形缓冲区的传统方法存在运行效率低以及内存利用率不高的缺点，本文提出了一种新的利用读写索引之间的关系，借助于读写索引的差值作为缓冲区有效数据个数来实现环形缓冲区状态判断，此方法突出了两个优点即（1）提高内存利用率；（2）提高运行效率。

1 环形缓冲区基本实现方法及分析

环形缓冲区在实现上可以采用数组形式和链表形式，链表形式利用动态内存管理动态生成每个入队出队的元素，形式灵活、结构简单，但由于涉及内存申请、释放效率较低；另外一种就是数组形式，数组在物理存储上是一维的连续线性结构，一次性分配，访问效率很高，本文针对数组形式的环形缓冲区。数组型环形缓冲区就是用数组定义在内存中开辟所需要的内存空间，然后定义两个索引用于对缓冲区元素进行读取，缓冲区有“空”“满”“非空非满”三种状态，在“空”状态时，可以写入新的元素，但读取元素为空，在“满”状态时，可以正确读取元素，写入元素时有两种可以选择的操作，一种是不执行写入操作，直接返回，一种是覆盖写入，覆盖最先写入的数据，两种方式在不同的场合都有应用。在“非空非满”状态可以正确进行读写操作。环形缓冲区基本操作如图1所示：

其中缓冲区使用的数组为Buff[QUEUE_SIZE]，QUEUE_SIZE为缓冲区大小，Wi为写入索引，指向当前要写入的单元地址，Ri为读出索引，指向当前要读出的单元地址。缓冲区为空时，Ri=Wi；当有数据写入时，将数据写入下标为Wi的单元Buff[Wi]，然后将Wi递增，如果Wi的值等于QUEUE_SIZE，Wi重新赋值为0；当有数据需要读出时，首先判断缓冲区是否为空，即Ri是否等于Wi，如果不为空，则返回Buff[Ri]，然后将Ri递增，如果Ri的值等于QUEUE_SIZE，Ri重新赋值为0。运行中如果写入的速度大于读出的速度，Wi和Ri之间的距离越来越大，直到Wi追上Ri即Wi=Ri，此时就是缓冲区写“满”的状态，如果再写入的话，将覆盖老数据，并且此时Wi=Ri正好也是缓冲区空的条件，如果不做调整读出操作将判断缓冲区为“空”而不能正确操作，因此，环状缓冲区的关键核心就是对缓冲区“满”状态的判断和处理[13]。

常用有兩种方法进行“满”状态判断和处理：

方法一：保持一个元素不用。当Wi差一个等于Ri时，判断缓冲区为满，不再增加Wi，如图2所示。此方法处理虽然简单，但保留了一个元素空间未能使用，存在内存单元浪费问题，从而导致数据存储空间利用率不高现象。

方法二：引入一个缓存区有效数据个数的变量QLen。每次入队、出队操作时首先根据有效数据个数

判断队列的状态，如果QLen

2 读写指针直接计算实现状态判断

经过对上述实现方法的分析，本文提出一种新的不引入计数变量不存在内存浪费的实现方法，方法的核心就是利用读写索引Wi、Ri之间的关系。不同于上述Wi、Ri递增到QUEUE_SIZE变0的方法，本方法一直递增Wi、Ri而不清零，直到递增溢出后自动清零，这样Wi和Ri之间的距离就可以通过Wi-Ri直接得到，Wi-Ri就是缓冲区有效数据的个数，如果Wi-Ri=0，则队列为“空”；如果Wi-Ri=QUEUE_SIZE，则队列为“满”，如果Wi-Ri

通过上面Wi、Ri的操作获取了缓冲区有效数据个数，进而就可以得到缓冲区的“空”、“满”等状态。另外，知道了Wi、Ri的值，如果想读写缓冲区对应的单元，只需要把Wi、Ri的值用QUEUE_SIZE取模运算，即可得到实际访问数组的下标值。

3 实现过程

根据上述工作原理，给出环形缓冲区的实现过程。定义环形缓冲区存放数组为Buff；缓冲区大小QUEUE_SIZE；缓冲区有效数据个数N，N为无符号整数；Wi写索引，Ri读索引，Wi、Ri均为无符号整数，初始化为0；I为实际读写索引，I≤QUEUE_SIZE-1；读写数据为Data。不可覆盖环形缓冲区的写入过程如图6所示。可覆盖环形缓冲区的写入过程如图7所示。两种缓冲区读取操作相同，如图8所示。

4 性能分析

4.1 内存利用率

假设缓冲区共M个元素，每个元素长度为S字节，保持一个元素不用的方法（以下简称方法A）的“满”状态利用率为：

引入有效数据个数变量的方法（以下简称方法B）的“满”状态利用率为：

其中Q为有效数据个数变量所占的内存，最大值为缓冲区大小QUEUE_SIZE，一般为无符号整数所占的字节数。

本文提出的方法的“满”状态利用率为：

图9为方法A在S=1、S=2、S=4、S=8、S=16，方法B在Q=4，和本文方法在缓冲区为1000字节内的“满”状态利用率比较，可以看出本文方法的利用率不论缓冲区大小都为100%，方法B效率次之，方法A最差，并且随着单个元素所占内存越大效率越差。

4.2 代码效率测试

分别编写三种方法的C语言实现代码，采用不可覆盖策略，用Keil uVision5.14进行编译，基于STM32F103ZE芯片进行软件仿真，编译器优化级别设为最高（-O3）。本文提出的方法读写缓冲区函数为SQueue_Push、SQueue_Pop，方法A读写函数为SQueue_Push1、SQueue_Pop1，方法B读写函数为SQueue_Push2、SQueue_Pop2，编译后代码量如图10所示。可见三种方法代码量差不多，但本文的方法少几条指令。

在主函数中分别进行三种方法的单次写入读出，重复10万次，得到执行效率和代码覆盖率如图11所示。

可见在缓冲区未满、部分代码未覆盖的情况下，本文方法的写入方法效率最高，读出方法居中，相差1～2ms。在正常使用中，缓冲区占用容量处于动态调整过程，整个效率决定于读写效率最差的操作，这样三种方法的效率为本文效率>B方法>A方法。

为了使代码覆盖率达到100%，分别写缓冲区2048次，然后读缓冲区2048次，重复100次，测试结果如图12所示。

可见在综合测试中，本文写缓冲方法只用了80.811ms比其他两种方法快8～30ms左右，而读缓冲区方法效率居中，B方法最高，A方法差不多。以缓冲区动态读写效率最差计算，本文效率>B方法>A方法。

5 结论

本文在环形缓冲区基本实现方法的基础上，提出了一种新的不引入计数变量、不存在内存浪费的缓冲区实现方法，其核心思想是利用读写索引Wi、Ri之间的关系，让Wi、Ri一直递增而不清零，直到递增溢出后自动清零，Wi和Ri之间的距离Wi-Ri就是缓冲区有效数据的个数，这个同样适用于Wi