1、前言
最近项目中用到一个环形缓冲区（ring buffer），代码是由linux内核的kfifo改过来的。缓冲区在文件系统中经常用到，通过缓冲区缓解cpu读写内存和读写磁盘的速度。例如一个进程A产生数据发给另外一个进程B，进程B需要对进程A传的数据进行处理并写入文件，如果B没有处理完，则A要延迟发送。为了保证进程A减少等待时间，可以在A和B之间采用一个缓冲区，A每次将数据存放在缓冲区中，B每次冲缓冲区中取。这是典型的生产者和消费者模型，缓冲区中数据满足FIFO特性，因此可以采用队列进行实现。Linux内核的kfifo正好是一个环形队列，可以用来当作环形缓冲区。生产者与消费者使用缓冲区如下图所示：
2、linux 内核kfifo
kfifo设计的非常巧妙，代码很精简，对于入队和出对处理的出人意料。首先看一下kfifo的数据结构：
kfifo提供的方法有：
定义自旋锁的目的为了防止多进程/线程并发使用kfifo。因为in和out在每次get和out时，发生改变。初始化和创建kfifo的源代码如下：
在kfifo_init和kfifo_calloc中，kfifo->size的值总是在调用者传进来的size参数的基础上向2的幂扩展，这是内核一贯的做法。这样的好处不言而喻--对kfifo->size取模运算可以转化为与运算，如：kfifo->in % kfifo->size 可以转化为 kfifo->in & (kfifo->size – 1)
kfifo的巧妙之处在于in和out定义为无符号类型，在put和get时，in和out都是增加，当达到最大值时，产生溢出，使得从0开始，进行循环使用。put和get代码如下所示：
put和get在调用__put和__get过程都进行加锁，防止并发。从代码中可以看出put和get都调用两次memcpy，这针对的是边界条件。例如下图：蓝色表示空闲，红色表示占用。
（1）空的kfifo，
（2）put一个buffer后
（3）get一个buffer后
（4）当此时put的buffer长度超出in到末尾长度时，则将剩下的移到头部去
3、测试程序
仿照kfifo编写一个ring_buffer，现有线程互斥量进行并发控制。设计的ring_buffer如下所示：
采用多线程模拟生产者和消费者编写测试程序，如下所示：
测试结果如下所示：
4、参考资料
<a href="http://blog.csdn.net/linyt/article/details/5764312">http://blog.csdn.net/linyt/article/details/5764312</a>
<a href="http://en.wikipedia.org/wiki/Circular_buffer">http://en.wikipedia.org/wiki/Circular_buffer</a>
<a href="http://yiphon.diandian.com/post/2011-09-10/4918347">http://yiphon.diandian.com/post/2011-09-10/4918347</a>