循环缓冲区

简介: 循环缓冲区在一些竞争问题上提供了一种免锁的机制,免锁的前提是,生产者和消费都只有一个的情况下,否则也要加锁。下面就内核中提取出来,而经过修改后的fifo进行简要的分析。

循环缓冲区在一些竞争问题上提供了一种免锁的机制,免锁的前提是,生产者和消费
都只有一个的情况下,否则也要加锁。下面就内核中提取出来,而经过修改后的fifo进
行简要的分析。

先看其只要数据结构:
struct my_fifo {
    unsignedchar *buffer;/*the buffer holding the data*/
    unsignedint size;    /*the size of theallocated buffer*/
    unsignedint in;      /*data is addedat offset (in % size)*/
    unsignedint out;     /*data isextracted from off. (out % size)*/
};
也不用多说,一看就明白。size, in, out 都设成无符号型的,因为都不存在负值的情型。

/*
form kernel/kfifo.c
*/

#include<stdio.h>
#include<stdlib.h>
#include<fifo.h>

#define min(a,b) ((a) < (b) ? (a):(b))
/*
my_fifo_init
*/
struct my_fifo *my_fifo_init(unsignedchar*buffer, unsignedint size)
{
    structmy_fifo *fifo;


    fifo = malloc(sizeof(structmy_fifo));
    if(!fifo)
        returnNULL;

    fifo->buffer = buffer;
    fifo->size = size;
    fifo->in = fifo->out = 0;

    returnfifo;
}
这个初始化fifo结构的函数一般也不会在应用层里进行调用,而是被下面的fifo_alloc调用。依我的观点来看,这两个函数合成一个函数会更加的清晰,但是这一情况只针对buffer是系统开辟的空间,如果buffer的空间是由其它的函数来提供,就只能用上面的这个函数。

 

/*
my_fifo_alloc
*/
struct my_fifo *my_fifo_alloc(unsignedintsize)
{
    unsignedchar *buffer;
    structmy_fifo *ret;

    /*
* round up to the next power of 2, since our 'let theindices
* wrap' tachnique works only in this case.
*/

    buffer = malloc(size);
    if(!buffer)
        returnNULL;

    ret = my_fifo_init(buffer, size);

    if(ret == NULL)
        free(buffer);

    returnret;
}
/*
* my_fifo_free
*/
void my_fifo_free(struct my_fifo *fifo)
{
    free(fifo->buffer);
    free(fifo);
}

这两个函数也不作过多的分析,都很清晰。

  

/*
my_fifo_put()
*/
unsigned intmy_fifo_put(struct my_fifo *fifo,
             unsignedchar *buffer,unsigned intlen)
{
    unsignedint l;

    len = min(len, fifo->size -fifo->in + fifo->out);/*可能是缓冲区的空闲长度或者要写长度*/

    /*first putthe data starting from fifo->in to buffer end*/
    l = min(len, fifo->size -(fifo->in & (fifo->size - 1)));
   memcpy(fifo->buffer + (fifo->in & (fifo->size - 1)), buffer, l);

    /*then putthe rest (if any) at the beginning of the buffer*/
    memcpy(fifo->buffer, buffer + l,len - l);

    fifo->in += len;

    returnlen;
}

/*
my_fifo_get
*/
unsigned intmy_fifo_get(struct my_fifo *fifo,
             unsignedchar *buffer,unsigned intlen)
{
    unsignedint l;

    len = min(len, fifo->in -fifo->out); /*可读数据*/

    /*first getthe data from fifo->out until the end of the buffer*/
    l = min(len, fifo->size -(fifo->out & (fifo->size - 1)));
    memcpy(buffer, fifo->buffer +(fifo->out & (fifo->size - 1)),l);

    /*then getthe rest (if any) from the beginning of the buffer*/
    memcpy(buffer + l, fifo->buffer,len - l);

    fifo->out += len;

    returnlen;
}这两个读写结构才是循环缓冲区的重点。在fifo结构中,size是缓冲区的大小,是由用户自己定义的,但是在这个设计当中要求它的大小必须是2的幂次。当in==out时,表明缓冲区为空的,当(in-out)==size    时,说明缓冲区已满。我们看下具体实现,在86行处如果size-in+out ==0,也即获得的len值会0,而没有数据写入到缓冲区中。所以在设计缓冲区的大小的时候要恰当,读出的速度要比定入的速度要快,否则缓冲区满了会使数据丢失,可以通过成功写入的反回值来做判断尝试再次写入.另一种情况则是缓冲区有足够的空间给要写入的数据,但是试想一下,如果空闲的空间在缓冲的首尾两次,这又是如何实现呢?这部分代码实现得非常巧妙。我们看fifo->in &(fifo->size-1)这个表达式是什么意思呢?我们知道size是2的幂次项,那么它减1即表示其值的二进制所有位都为1,与in相与的最终结果是in%size,比
size要小,所以看in及out的值都是不断地增加,但再相与操作后,它们即是以size为周期的一个循环。89行就是比较要写入的数据应该是多少,如果缓冲区后面的还有足够的空间可写,那么把全部的值写到后面,否则写满后面,再写到前面去93行。读数据也可以作类似的分析,108行表示请求的数据要比缓冲区的数据要大时,只读取缓冲区中可用的数据。

static inlinevoid my_fifo_reset(struct my_fifo *fifo)
{
    fifo->in = fifo->out = 0;
}

static inlineunsignedintmy_fifo_len(struct my_fifo *fifo)
{
    returnfifo->in - fifo->out;
}

在头文件里还有缓冲区置位及返回缓冲区中数据大小两个函数,很简单,不必解释。

相关文章
|
存储 缓存 Java
Java内存区域(二)
Java内存区域
67 0
|
14天前
|
Java
java内存区域
1)栈内存:保存所有的对象名称 2)堆内存:保存每个对象的具体属性 3)全局数据区:保存static类型的属性 4)全局代码区:保存所有的方法定义
20 1
|
6月前
|
程序员 编译器 C++
C++内存分区模型(代码区、全局区、栈区、堆区)
C++内存分区模型(代码区、全局区、栈区、堆区)
|
7月前
|
程序员 编译器 C++
内存分区模型(代码区、全局区、栈区、堆区)
内存分区模型(代码区、全局区、栈区、堆区)
|
7月前
|
定位技术
环形缓冲区RingBuff
环形缓冲区RingBuff
获取不同时区的时间
获取不同时区的时间
60 0
如何设置交换区swap空间
如何设置交换区swap空间
123 0
|
存储
环形缓冲区
环形缓冲区 是一段 先进先出 的循环缓冲区,有一定的大小,我们可以把它抽象理解为一块环形的内存。 我们使用环形缓冲区主要有两个原因; (1)当我们要存储大量数据时,我们的计算机只能处理先写入的数据,处理完毕释放数据后,后面的数据需要前移一位,大量的数据会频繁分配释放内存,从而导致很大的开销。使用环形缓冲区 可以减少内存分配继而减少系统的开销。 (2)如果我们频繁快速的持续向计算机输入数据,计算机可能执行某个进程不能及时的执行输入的数据,导致数据丢失。这时,我们可以将要输入的数据放入环形缓冲区内,计算机就不会造成数据丢失。
111 0
|
缓存
缓存区的类型
缓存区的类型
150 0
|
存储 程序员 编译器
关于栈区、堆区、全局区、文字常量区、程序代码区
一个由C/C++编译的程序占用的内存分为以下几个部分: 栈区、栈区、堆区、全局区、文字常量区、程序代码区
183 0