环形缓冲区的实现

http://blog.csdn.net/wanxiao009/article/details/5519514

    环形缓冲区是嵌入式系统中十分重要的一种数据结构，比如在一个视频处理的机制中，环形缓冲区就可以理解为数据码流的通道，每一个通道都对应着一个环形缓冲区，这样数据在读取和写入的时候都可以在这个缓冲区里循环进行，程序员可以根据自己需要的数据大小来决定自己使用的缓冲区大小。

    环形缓冲区，顾名思义这个缓冲区是环形的，那么何谓环形这个意思也很好理解，就是用一个指针去访问该缓冲区的最后一个内存位置的的后一位置时回到环形缓冲区的起点。类似一个环一样。这样形容就很好理解了，当然有办法实现了。我在这里采用了2种方式实现了环形缓冲区，一个是用数组的方法，一个是用链表的方法。

    数组是一块连续的内存，所以顺序访问时只要根据下标的增加而增加，但是最后一个元素之后需要回到起始位置，这就需要我们对这个地方进行特殊处理。只要最后一个地址访问结束能顺利回到起始地址，这个缓冲区就可以实现。代码如下：

/* File name: ringbuf.c
 * Author   : wanxiao
 * Function :Implement a circular buffer,
             you can read and write data in the buffer zone.
 */

#include

#define MAXSIZE 8

int ringbuf[MAXSIZE];
int readldx=0;
int writeldx=0;

int next_data_handle(int addr)
{
    return (addr+1) == MAXSIZE ? 0:(addr+1) ;
}

int write_data(int data)
{
    int i;
    *(ringbuf+writeldx) = data;
    writeldx = next_data_handle(writeldx);
    for(i=0;i
    {
        printf("%4d",*(ringbuf+i));
        if(MAXSIZE-1 == i)
            printf("/n");
    }
}

int read_data()
{
    printf("read data is : %d/n",*(ringbuf+readldx));
    readldx = next_data_handle(readldx);
}

int main(int argc , char **argv)
{
    int data;
    char cmd;

    do{
        printf("select:/nw/t--write/nr/t--read/nq/t--quit/n");
        scanf("%s",&cmd);

        switch(cmd)
        {
            case 'w' :
                printf("please input data:");
                scanf("%d",&data);
                write_data(data);
                break;
            case 'r' :
                data = read_data();
                break;
            case 'q' :
                printf("quit/n");
                break;
            default :
                printf("Command  error/n");
        }
    }while(cmd != 'q');
    return 0;
}

 

    链表实现，实际上就是一个单向循环链表。这个方法的优点是不需要最后一个元素进行特殊处理，但是实现起来比数组稍微麻烦一点，单思路还是很清晰简单的。代码如下：

#include
#include


typedef struct signal_loop_chain
{
    int data;
    struct signal_loop_chain *next;
}NODE;

NODE *Create_loop_chain(int n)
{
    int i;
    NODE *head , *previous , *current ;
    previous = (NODE *)malloc(sizeof(NODE));
    if(previous == NULL)
        exit(1);

    previous->data =0;
    previous->next = NULL;
    head = previous ;

    for(i=0 ; i
    {
        current = (NODE*)malloc(sizeof(NODE));
        if(current == NULL)
            exit(1);

//      scanf("%d",¤t->data);
        current->next = head;
        previous->next = current;
        previous = current ;
    }
    return head ;
}

int Show(NODE *head)
{
    NODE *current;
    current = head->next ;
    printf("List:/n");
    while(current != head)
    {
        printf("%4d",current->data);
        current = current->next;
    }
    printf("/n");
}

int read_buf(NODE *head)
{
    NODE *current;
    current = head->next;
    while(1)
    {
        printf("read number is %d/n",current->data);
        current = current->next;
        sleep(1);
    }

}

int write_buf(NODE *head)
{
    NODE *current;
    int i = 0;
    current = head->next;
    while(1)
    {
        current->data = i++;
        printf("write number is %d/n",current->data);
        current = current->next;
        sleep(1);
    }
}

int main(int argc , char **argv)
{
    int num;
    char cmd;
    NODE *head;
    printf("please input node_num /n");
    scanf("%d",&num);
    head = Create_loop_chain(num);
    printf("The ringbuf was found/n");
    Show(head);

    while(1){
        printf("please select r or w/n");
        scanf("%c",&cmd);

        if(cmd == 'r'){
            read_buf(head);
            Show(head);
        }

        if(cmd == 'w'){
            write_buf(head);
            Show(head);
        }

    }
    return 0;
}

 

 

 

    以上都是针对单进程而言。对于系统，尤其是嵌入式Linux系统中，缓冲区的保护机制就变得尤为重要了，因为我们的数据时不停的在读写，内存不停的变化，如果牵扯到多任务（多进程，多线程），我们就需要加锁对其进行保护措施。这里我在链表的实现下加了信号量加以保护。

#include
#include
#include
#include

sem_t mutex;

typedef struct signal_loop_chain
{
    int data;
    struct signal_loop_chain *next;
}NODE;

NODE *Create_loop_chain(int n)
{
    int i;
    NODE *head , *previous , *current ;
    previous = (NODE *)malloc(sizeof(NODE));
    if(previous == NULL)
        exit(1);

    previous->data =0;
    previous->next = NULL;
    head = previous ;

    for(i=0 ; i
    {
        current = (NODE*)malloc(sizeof(NODE));
        if(current == NULL)
            exit(1);

        current->next = head;
        previous->next = current;
        previous = current ;
    }
    return head ;
}

int Show(NODE *head)
{
    NODE *current;
    current = head->next ;
    printf("List:/n");
    while(current != head)
    {
        printf("%4d",current->data);
        current = current->next;
    }
    printf("/n");
}

int read_buf(NODE *head)
{
    NODE *current;
    current = head->next;
    while(1)
    {
        sem_wait(&mutex);
        printf("read number is %d/n",current->data);
        current = current->next;
        sem_post(&mutex);
        sleep(2);
    }

}

int write_buf(NODE *head)
{
    NODE *current;
    int i = 0;
    current = head->next;
    while(1)
    {
        sem_wait(&mutex);
        current->data = i++;
        printf("write number is %d/n",current->data);
        current = current->next;
        sem_post(&mutex);
        sleep(1);
    }
}

int main(int argc , char **argv)
{
    int num,ret;
    char cmd;
    NODE *head;
    pthread_t id1,id2;

    ret = sem_init(&mutex ,0,1);
    if(ret != 0){
        perror("sem_init error");
    }
    printf("please input node_num /n");
    scanf("%d",&num);
    head = Create_loop_chain(num);
    printf("The ringbuf was found/n");
    Show(head);

    ret = pthread_create(&id1,NULL,(void *)write_buf,head);
    ret = pthread_create(&id2,NULL,(void *)read_buf,head);

    pthread_join(id1,NULL);
    pthread_join(id2,NULL);


    return 0;
}

http://hi.baidu.com/zkheartboy/blog/item/edee1ff74b543321720eecbc.html

环形缓冲区的实现代码

2007-11-15 23:10

在通信程序中，经常使用环形缓冲区作为数据结构来存放通信中发送和接收的数据。环形缓冲区是一个先进先出的循环缓冲区，可以向通信程序提供对缓冲区的互斥访问。

1、环形缓冲区的实现原理

环 形缓冲区通常有一个读指针和一个写指针。读指针指向环形缓冲区中可读的数据，写指针指向环形缓冲区中可写的缓冲区。通过移动读指针和写指针就可以实现缓冲 区的数据读取和写人。在通常情况下，环形缓冲区的读用户仅仅会影响读指针，而写用户仅仅会影响写指针。如果仅仅有一个读用户和一个写用户，那么不需要添加 互斥保护机制就可以保证数据的正确性。如果有多个读写用户访问环形缓冲区，那么必须添加互斥保护机制来确保多个用户互斥访问环形缓冲区。

图1、图2和图3是一个环形缓冲区的运行示意图。图1是环形缓冲区的初始状态，可以看到读指针和写指针都指向第一个缓冲区处；图2是向环形缓冲区中添加了一个数据后的情况，可以看到写指针已经移动到数据块2的位置，而读指针没有移动；图3是环形缓冲区进行了读取和添加后的状态，可以看到环形缓冲区中已经添加了两个数据，已经读取了一个数据。

2、实例：环形缓冲区的实现

环形缓冲区是数据通信程序中使用最为广泛的数据结构之一，下面的代码，实现了一个环形缓冲区：

/*ringbuf .c*/

＃i nclude

    ＃i nclude

#define NMAX 8

int iput = 0; /* 环形缓冲区的当前放人位置 */

int iget = 0; /* 缓冲区的当前取出位置 */

int n = 0; /* 环形缓冲区中的元素总数量 */

double buffer[NMAX];

/* 环形缓冲区的地址编号计算函数，，如果到达唤醒缓冲区的尾部，将绕回到头部。

环形缓冲区的有效地址编号为：0到(NMAX-1)

*/

int addring (int i)

{

        return (i+1) == NMAX ? 0 : i+1;

}

/* 从环形缓冲区中取一个元素 */

double get{void}

{

cnt pos;

if (n>0){

           Pos = iget;

           iget = addring(iget);

           n--;

           return buffer[pos];

}

else {

printf(“Buffer is empty\n”);

return 0.0;

}

/* 向环形缓冲区中放人一个元素*/

void put(double z)

{

if (n

           buffer[iput]=z;

           iput = addring(iput);

           n++;

}

else

printf(“Buffer is full\n”);

}

int main{void)

{

chat opera[5];

double z;

do {

printf(“Please input p|g|e?”);

scanf(“%s”, &opera);

               switch(tolower(opera[0])){

               case ‘p’: /* put */

                  printf(“Please input a float number?”);

                  scanf(“%lf”, &z);

                  put(z);

                  break;

case ‘g’: /* get */

                  z = get();

printf(“%8.2f from Buffer\n”, z);

break;

case ‘e’:

                  printf(“End\n”);

                  break;

default:

                  printf(“%s - Operation command error! \n”, opera);

}/* end switch */

}while(opera[0] != ’e’);

return 0;

}

设备驱动中环形缓冲区数据存储和读写同步的实现

2007-11-15 23:06

首先通过自定义数据结构，对缓冲区做几个基本的指针和参数进行定义：

char * buffer_start, *buffer_end                  指向buffer起始端和结束端的指针

char *wp ,*rp                                                   数据的读写指针

int buffersize                                                    buffer大小

调用内存分配函数kmalloc函数，为该数据结构申请内存空间，初始化结束后，数据的读写指针都指向char *buffer_star，对于缓冲区，我们可以做一下几个rules:

1. *wp = *rp ：这个数据缓冲区是空的。对于读操作，遇到这种情况读操作应该会被阻塞，无数据可读，读进程进入睡眠等待状态；对于写操作，写睡眠将被唤醒，可写入的大小为整个buffer空间的大小

2. *wp > *rp ：缓冲区有数据可读，可读大小为wp-rp，读进程不会不会被阻塞，而wp-rp=buffersize时，写进程被阻塞进入睡眠，若wp-rp

3. *wp< *rp： 如果wp rp指向buffer_end的时候，会自动反转到buffer_start位置，可写空间为rp-wp-1

通过阻塞和睡眠机制，我们可以实现对这个buffer的读写的同步，下面还是以代码的方式讲解一下读写同步的原理：

static ssize_t scull_p_read (struct file *filp, char __user *buf, size_t count,
                 loff_t *f_pos)
{
struct scull_pipe *dev = filp->private_data;

if (down_interruptible(&dev->sem))                                               锁定信号量
   return -ERESTARTSYS;

while (dev->rp == dev->wp) { /* nothing to read */                       此时缓冲区为空，无数据可读
   up(&dev->sem); /* release the lock */                                          /*解锁信号量，注意：必须在进入阻塞睡眠之前解 锁信号量，准备进入睡眠*/
   if (filp->f_flags & O_NONBLOCK)
    return -EAGAIN;
   PDEBUG("\"%s\" reading: going to sleep\n", current->comm);
   if (wait_event_interruptible(dev->inq, (dev->rp != dev->wp)))      /* 阻塞，进入睡眠，当dev->rp != dev->wp这个条件被满足的时候，唤醒睡眠，这个睡眠应 该    在 写操作中被唤醒*/
    return -ERESTARTSYS; /* signal: tell the fs layer to handle it */
   /* otherwise loop, but first reacquire the lock */
   if (down_interruptible(&dev->sem))                                          /* 如果被唤醒，则重新锁定信号量，进行数据读取*/
    return -ERESTARTSYS;
}
/* ok, data is there, return something */
if (dev->wp > dev->rp)
   count = min(count, (size_t)(dev->wp - dev->rp));
else /* the write pointer has wrapped, return data up to dev->end */
   count = min(count, (size_t)(dev->end - dev->rp));
if (copy_to_user(buf, dev->rp, count)) {    /*i在rp>wp情况下，本次操作不能一次性读取buffer里面所有的数据*/
   up (&dev->sem);                                         /*必须分两次读取，第一次只读到end-rp,第二次读到wp-start*/
   return -EFAULT;
}
dev->rp += count;                                /*count值已经被处理过，保证dev->rp += count不会超过buffer_end*/

if (dev->rp == dev->end)
   dev->rp = dev->buffer; /* wrapped */
up (&dev->sem);

/* finally, awake any writers and return */
wake_up_interruptible(&dev->outq);               /*读取结束后完成指针的更新，唤醒写睡眠*/
PDEBUG("\"%s\" did read %li bytes\n",current->comm, (long)count);
return count;
}

static ssize_t scull_p_write(struct file *filp, const char __user *buf, size_t count,
                 loff_t *f_pos)
{
struct scull_pipe *dev = filp->private_data;
int result;

if (down_interruptible(&dev->sem))
   return -ERESTARTSYS;

/* Make sure there's space to write */
result = scull_getwritespace(dev, filp);                  /*测试是否还有可写入的空间*/
if (result)
   return result; /* scull_getwritespace called up(&dev->sem) */

/* ok, space is there, accept something */
count = min(count, (size_t)spacefree(dev));                 /*如果有，察看还有多少空间可写*/
if (dev->wp >= dev->rp)
   count = min(count, (size_t)(dev->end - dev->wp)); /* to end-of-buf */   /*似乎还有一小段空间没有写入*/
else /* the write pointer has wrapped, fill up to rp-1 */
   count = min(count, (size_t)(dev->rp - dev->wp - 1));
PDEBUG("Going to accept %li bytes to %p from %p\n", (long)count, dev->wp, buf);
if (copy_from_user(dev->wp, buf, count)) {
   up (&dev->sem);
   return -EFAULT;
}
dev->wp += count;
if (dev->wp == dev->end)
   dev->wp = dev->buffer; /* wrapped */                      /*更新写指针*/
up(&dev->sem);

/* finally, awake any reader */
wake_up_interruptible(&dev->inq);   /*写完之后必定有数据可读，唤醒读睡眠*/

/* and signal asynchronous readers, explained late in chapter 5 */
if (dev->async_queue)
   kill_fasync(&dev->async_queue, SIGIO, POLL_IN);
PDEBUG("\"%s\" did write %li bytes\n",current->comm, (long)count);
return count;
}