嵌入式系统环形缓冲区快速读写方法的设计与实现

樊利军 田柏林 彭淑梅

（1.北京工业职业技术学院信息工程学院，北京 100042；2.北京市煤炭矿用机电设备技术开发公司，北京 100042；3.北京工业职业技术学院基础教育学院，北京 100042）

0 引言

环形缓冲区在嵌入式系统软件设计中是一种很重要的数据结构，广泛应用在数据采集、数字通信中数据产生率和数据处理率存在差异的场合。在实时性要求较高的嵌入式应用场合，由于内存资源非常有限，如果系统在很短的时间内获取大量数据且不允许数据丢失，采用环形缓冲区是一种理想的方法［1］。

目前常用的环形缓冲区采用链表形式和数组形式实现。链表形式采用动态内存管理方式，在读写数据时频繁进行内存申请和释放，形成内存碎片，内存使用效率低；数组形式采用静态内存管理方式，在读写数据以及判断缓冲区状态时需要进行取模操作，存在代码运行效率低的缺点。丁远［2］研究了单链表环形数据结构，该结构既具有链表存储动态申请内存实现缓冲区动态扩展的优点，又避免了频繁申请释放内存带来的内存碎片。李为民［3］提出通过设置数组形式缓冲区大小为2的幂，可以快速进行缓冲区读写操作。杨凯乔［4］提出利用数组形式缓冲区读写指针之间的关系，借助读写指针的差值作为缓冲区有效数据个数实现缓冲区状态判断，提高了内存利用率和运行效率。

本文提出一种基于数组形式的环形缓冲区数据快速读写方法，通过位与逻辑运算修改读写指针值，利用读写指针的差值作为缓冲区有效数据个数来实现环形缓冲区状态判断。此方法突出的优点是可以提高系统读写缓冲区代码的运行效率。

1 常用环形缓冲区实现方法

环形缓冲区是一种首尾相连、先入先出（First In First Out，FIFO）的数据队列结构，数据组织简单，判断缓冲区状态和读写数据操作简单［5］。常用的数组形式环形缓冲区示意图如图1所示，先利用数组定义在内存中开辟所需的空间，再定义一个队头指针变量（head）指向缓冲区读取数据的第一个数据地址，最后定义一个队尾指针变量（tail）指向缓冲区写数据的第一个数据地址。

图1 数组形式环形缓冲区示意图

常用环形缓冲区设置缓冲区的大小为N，缓冲区存放数组ring［N］，缓冲区状态标记tag，缓冲区数据长度存放在变量size。缓冲区初始化时队头指针变量、队尾指针变量都指向缓冲区首地址。读写数据开始，先判断缓冲区的状态，如果缓冲区满或空则返回相应状态；读写操作后，队头、队尾指针值加1并对N取模修改指针值，然后再判断缓冲区状态，缓冲区满tag＝1，缓冲区空tag＝0；通过队头、队尾指针差值加上N，再对N取模计算缓冲区数据长度。常用环形缓冲区的读写数据流程如图2所示。

图2 常用环形缓冲区读写数据流程图

2 快速读写环形缓冲区的设计原理

快速读写环形缓冲区设计时，设置缓冲区大小为M，其中M＝2n且2n－1＜N＜2n。修改队头、队尾指针时，通过指针值和M－1进行位与逻辑运算实现，以队头、队尾指针差值作为缓冲区数据长度。把常用环形缓冲区实现过程的取模运算，用位与逻辑运算和差值计算替代，可以提高程序运行效率。

2.1 修改队头、队尾指针分析

以M＝16＝24为例，即M－1＝15，设队头或队尾指针值为x，以下分三种情况，通过位与逻辑运算和直接取模运算结果对比，验证位与逻辑运算修改缓冲区队头、队尾指针在环形缓冲区内存映射的正确性。

（1）当x＜M时，x＆（M－1）＝x＆15＝x，x%M＝x%16＝x，即x＆（M－1）＝x%M。

（2）当x＝M时，x＆（M－1）＝x＆15＝0，x%M＝x%16＝0，即x＆（M－1）＝x%M。

（3）当x＞M时，x＝20＋21＋…＋2n，n≥4的部分，采用位与逻辑运算后的值为0；n＜4部分运算结果同（1），即x＆（M－1）＝x%M。

假设x＝39，则x＝1＋2＋4＋32 ＝20＋21＋22＋25，x＆（M－1）＝39＆15＝7，x%M＝39%16＝7，即x＆（M－1）＝x%M。

由上可知，当缓冲区大小M为2的幂时，无论x值为多少，x＆（M－1）＝x%M恒成立，因此快速读写环形缓冲区大小设置为M，通过位与逻辑运算修改队头、队尾指针值可得缓冲区内存地址正确的映射。

2.2 缓冲区数据长度计算分析

在快速读写环形缓冲区设计中需要定义队头、队尾指针为无符号整型。当队头或队尾指针值为最大值M时，如果缓冲区再进行读或写操作，队头或队尾指针值需要加1，会出现溢出情况，即M＋1＝0。根据缓冲区读写数据的操作，缓冲区中的数据总是维持在［*head，*tail）这个区间中，由于溢出可能存在，这个区间有三种情况。

（1）*head和*tail值都没有溢出，缓冲区中数据长度size＝*tail－*head。

（2）*head值没溢出，*tail值溢出，数据长度size＝M－*head＋1＋*tail＝*tail－*head＋M＋1＝*tail－*head。

（3）*head值和*tail值都溢出，数据长度size＝*tail－*head。

根据上述分析，size＝*tail－*head总是表示环形缓冲区中数据的长度。

3 快速读写环形缓冲区实现方法

在快速读写环形缓冲区实现方法中设置缓冲区大小为M，缓冲区存放数组ring［M］，队头和队尾指针值为无符号整型，其余的定义与常用环形缓冲区相同。快速读写环形缓冲区的读写数据流程如图3所示。

图3 快速读写环形缓冲区读写数据流程图

快速读写环形缓冲区在读写数据时，首先判断缓冲区的状态，缓冲区满或空则返回相应状态；然后读缓冲区数据到相应变量或写数据到缓冲区中；读写操作后，队头、队尾指针值加1和M－1进行位与逻辑运算修改指针值；再次判断缓冲区状态，缓冲区满tag＝1，缓冲区空tag＝0；通过队头、队尾指针差值计算缓冲区数据长度。

4 实验与结果分析

用C语言编写常用环形缓冲区、快速读写环形缓冲区两种方法的单字节读写数据程序代码，分别测量读写缓冲区数据运行的时间。为了避免多字节连续写缓冲区呈现满状态而使程序终止，在测试程序中写缓冲区采用数据覆盖方式。测试实验方案基于STM32F103VE6芯片，采用Keil uVision5.33进行代码编译，J－Link仿真器的串行调试（Serial Wire Debug，SWD）模式进行仿真调试运行，仿真调试中CPU运行主频设置为72 MHz，利用Keil软件调试中的时间计时器进行程序运行时间测量。

测试实验中常用环形缓冲区的大小为200 B，即N＝200；快速读写环形缓冲区的大小为256 B，即M＝256。两种环形缓冲区分别按150，250，500，1 000，2 000 B读写数据各5次，记录5次程序运行时间ti，并计算平均值tav和读写单字节平均值tbav，如表1、表2所示。

表1 两种环形缓冲区读数据时间表

表2 两种环形缓冲区写数据时间表

根据表1、表2中常用环形缓冲区和快速读写环形缓冲区读写单字节平均时间tbav，分别计算两种缓冲区读写数据平均时间差值tTD和提高效率。如表3、表4所示，快速读写环形缓冲区在读数据比常用环形缓冲区提高效率约22%；在缓冲区状态未满情况下，写入数据提高效率约14%，在缓冲区满且数据覆盖状态下，写入数据提高效率约10.5%。

表3 两种环形缓冲区读单字节平均时间和提高效率对比表

表4 两种环形缓冲区写单字节平均时间和提高效率对比表

5 结论

本文在常用环形缓冲区实现方法的基础上，提出了一种快速读写环形缓冲区的方法，实现原理是设置缓冲区大小M为2的幂，通过指针值和M－1位与逻辑运算修改队头、队尾指针，直接利用队头、队尾指针差值计算缓冲区数据长度和判断缓冲区状态。把常用环形缓冲区实现过程的取模运算，用位与逻辑运算和差值计算替代，通过仿真测试验证了这种快速读写环形缓冲区的方法可以显著提高缓冲区读写效率，可应用到需要环形缓冲区的各种嵌入式系统中。