概述
ring buffer称作环形缓冲区,也称作环形队列(circular queue),是一种用于表示一个固定尺寸、头尾相连的缓冲区的数据结构,适合缓存数据流。
使用场景
在任务间的通信、串口数据收发、log缓存、网卡处理网络数据包、音频/视频流处理中均有环形缓冲区(ring buffer) 的应用。在RT-Thread的ringbuffer.c和ringbuffer.h文件中,Linux内核文件kfifo.h和kfifo.c中也有环形缓冲区(ring buffer)的代码实现。
特点
- 适合于事先明确了缓冲区的最大容量的情形。缓冲区的容量(长度)一般固定,可以用一个静态数组来充当缓冲区,无需重复申请内存;
- 如果缓冲区的大小需要经常调整,就不适合用环形缓冲区,因为在扩展缓冲区大小时,需要搬移其中的数据,这种场合使用链表更加合适;
实现
一般的,对一个环形缓冲区进行读写操作,最少需要4个信息:
- 在内存中的实际开始位置(例如:一片内存的头指针,数组的第一个元素指针);
- 在内存中的实际结束位置(也可以是缓冲区实际空间大小,结合开始位置,可以算出结束位置);
- 在缓冲区中进行写操作时的写索引值;
- 在缓冲区中进行读操作时的读索引值。
缓冲区开始位置和缓冲区结束位置(或空间大小) 实际上定义了环形缓冲区的实际逻辑空间和大小。读索引和写索引标记了缓冲区进行读操作和写操作时的具体位置。
struct rt_ringbuffer
{
rt_uint8_t *buffer_ptr;
rt_uint16_t read_mirror : 1;
rt_uint16_t read_index : 15;
rt_uint16_t write_mirror : 1;
rt_uint16_t write_index : 15;
rt_int16_t buffer_size;
};
struct kfifo {
unsigned char *buffer; /* the buffer holding the data */
unsigned int size; /* the size of the allocated buffer */
unsigned int in; /* data is added at offset (in % size) */
unsigned int out; /* data is extracted from off. (out % size) */
spinlock_t *lock; /* protects concurrent modifications */
};
总结
- 环形缓冲区(ring buffer)适合于事先明确了缓冲区的最大容量的情形。缓冲区的容量(长度)一般固定,可以用一个静态数组来充当缓冲区,无需重复申请内存;
- 如果缓冲区的大小需要经常调整,就不适合用环形缓存区,因为在扩展缓冲区大小时,需要搬移其中的数据,这种场合使用链表更加合适;
- 因为缓冲区成头尾相连的环形,写操作可能会覆盖未及时读取的数据,有的场景允许这种情况发生,有的场景又严格限制这种情况发生。选择何种策略和具体应用场景相关;
- 环形缓冲区(ring buffer)特别适合于通信双方循环发送数据的场景;
- 镜像指示位是一种高效判断缓冲区是否为空或满的策略,在RT-Thread和linux中都使用了该策略(或者是该策略的扩展),其能够保证在只有一个读线程(或进程)和一个写线程(或进程)中无需锁也能做到线程安全;
- 注意区分写指针和写索引,读指针和读索引,最终对缓冲区进行操作还是需要写索引和读索引;
- 如果自己嵌入式项目中需要使用环形缓冲区(ring buffer),可以借鉴linux 2.6版本的kfifo实现,很容易改写,而且非常高效。