环形缓冲区的设计与实现

巅峰残狼

以下内容转自网络，感谢网友：玩笑joker

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

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

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

[cpp] view plaincopyprint?

1. /* File name: ringbuf.c 
2.  * Author: wanxiao 
3.  * Function:Implement a circular buffer,  
4.              you can read and write data in the buffer zone. 
5.  */  
6.   
7. #include <stdio.h>     
8.     
9. #define MAXSIZE 8     
10.     
11. int ringbuf[MAXSIZE];     
12. int readldx=0;  
13. int writeldx=0;  
14.   
15. int next_data_handle(int addr)     
16. {     
17.     return (addr+1) == MAXSIZE ? 0addr+1) ;     
18. }     
19.     
20. int write_data(int data)  
21. {  
22.     int i;  
23.     *(ringbuf+writeldx) = data;  
24.     writeldx = next_data_handle(writeldx);  
25.     for(i=0;i<MAXSIZE;i++)  
26.     {  
27.         printf("%4d",*(ringbuf+i));  
28.         if(MAXSIZE-1 == i)  
29.             printf("/n");  
30.     }  
31. }  
32.   
33. int read_data()  
34. {  
35.     printf("read data is: %d/n",*(ringbuf+readldx));  
36.     readldx = next_data_handle(readldx);  
37. }  
38.     
39. int main(int argc , char **argv)     
40. {     
41.     int data;     
42.     char cmd;  
43.   
44.     do{     
45.         printf("select:/nw/t--write/nr/t--read/nq/t--quit/n");     
46.         scanf("%s",&cmd);     
47.     
48.         switch(cmd)     
49.         {     
50.             case 'w':     
51.                 printf("please input data:");     
52.                 scanf("%d",&data);     
53.                 write_data(data);     
54.                 break;     
55.             case 'r':     
56.                 data = read_data();     
57.                 break;     
58.             case 'q':     
59.                 printf("quit/n");     
60.                 break;     
61.             default:     
62.                 printf("Command  error/n");     
63.         }     
64.     }while(cmd != 'q');     
65.     return 0;     
66. }  

 

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

[cpp] view plaincopyprint?

1. #include <stdio.h>  
2. #include <stdlib.h>  
3.   
4.   
5. typedef struct signal_loop_chain  
6. {  
7.     int data;  
8.     struct signal_loop_chain *next;  
9. }NODE;  
10.   
11. NODE *Create_loop_chain(int n)  
12. {  
13.     int i;  
14.     NODE *head , *previous , *current ;  
15.     previous = (NODE *)malloc(sizeof(NODE));  
16.     if(previous == NULL)  
17.         exit(1);  
18.   
19.     previous->data =0;  
20.     previous->next = NULL;  
21.     head = previous ;  
22.   
23.     for(i=0 ; i<n ; i++)  
24.     {  
25.         current = (NODE*)malloc(sizeof(NODE));  
26.         if(current == NULL)  
27.             exit(1);  
28.   
29. //      scanf("%d",¤t->data);  
30.         current->next = head;  
31.         previous->next = current;  
32.         previous = current ;  
33.     }  
34.     return head ;  
35. }  
36.   
37. int Show(NODE *head)  
38. {  
39.     NODE *current;  
40.     current = head->next ;  
41.     printf("List:/n");  
42.     while(current != head)  
43.     {  
44.         printf("%4d",current->data);  
45.         current = current->next;  
46.     }  
47.     printf("/n");  
48. }  
49.   
50. int read_buf(NODE *head)  
51. {  
52.     NODE *current;  
53.     current = head->next;  
54.     while(1)  
55.     {  
56.         printf("read number is %d/n",current->data);  
57.         current = current->next;  
58.         sleep(1);  
59.     }  
60.   
61. }  
62.   
63. int write_buf(NODE *head)  
64. {  
65.     NODE *current;  
66.     int i = 0;  
67.     current = head->next;  
68.     while(1)  
69.     {  
70.         current->data = i++;  
71.         printf("write number is %d/n",current->data);  
72.         current = current->next;  
73.         sleep(1);  
74.     }  
75. }  
76.   
77. int main(int argc , char **argv)  
78. {  
79.     int num;  
80.     char cmd;  
81.     NODE *head;  
82.     printf("please input node_num /n");  
83.     scanf("%d",&num);  
84.     head = Create_loop_chain(num);  
85.     printf("The ringbuf was found/n");  
86.     Show(head);  
87.   
88.     while(1){  
89.         printf("please select r or w/n");  
90.         scanf("%c",&cmd);  
91.   
92.         if(cmd == 'r'){  
93.             read_buf(head);  
94.             Show(head);  
95.         }  
96.           
97.         if(cmd == 'w'){  
98.             write_buf(head);  
99.             Show(head);  
100.         }  
101.           
102.     }  
103.     return 0;  
104. }  

 

 

 

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

[c-sharp] view plaincopyprint?

1. #include <stdio.h>  
2. #include <stdlib.h>  
3. #include <pthread.h>  
4. #include <semaphore.h>  
5.   
6. sem_t mutex;  
7.   
8. typedef struct signal_loop_chain  
9. {  
10.     int data;  
11.     struct signal_loop_chain *next;  
12. }NODE;  
13.   
14. NODE *Create_loop_chain(int n)  
15. {  
16.     int i;  
17.     NODE *head , *previous , *current ;  
18.     previous = (NODE *)malloc(sizeof(NODE));  
19.     if(previous == NULL)  
20.         exit(1);  
21.   
22.     previous->data =0;  
23.     previous->next = NULL;  
24.     head = previous ;  
25.   
26.     for(i=0 ; i<n ; i++)  
27.     {  
28.         current = (NODE*)malloc(sizeof(NODE));  
29.         if(current == NULL)  
30.             exit(1);  
31.   
32.         current->next = head;  
33.         previous->next = current;  
34.         previous = current ;  
35.     }  
36.     return head ;  
37. }  
38.   
39. int Show(NODE *head)  
40. {  
41.     NODE *current;  
42.     current = head->next ;  
43.     printf("List:/n");  
44.     while(current != head)  
45.     {  
46.         printf("%4d",current->data);  
47.         current = current->next;  
48.     }  
49.     printf("/n");  
50. }  
51.   
52. int read_buf(NODE *head)  
53. {  
54.     NODE *current;  
55.     current = head->next;  
56.     while(1)  
57.     {  
58.         sem_wait(&mutex);  
59.         printf("read number is %d/n",current->data);  
60.         current = current->next;  
61.         sem_post(&mutex);  
62.         sleep(2);  
63.     }  
64.   
65. }  
66.   
67. int write_buf(NODE *head)  
68. {  
69.     NODE *current;  
70.     int i = 0;  
71.     current = head->next;  
72.     while(1)  
73.     {  
74.         sem_wait(&mutex);  
75.         current->data = i++;  
76.         printf("write number is %d/n",current->data);  
77.         current = current->next;  
78.         sem_post(&mutex);  
79.         sleep(1);  
80.     }  
81. }  
82.   
83. int main(int argc , char **argv)  
84. {  
85.     int num,ret;  
86.     char cmd;  
87.     NODE *head;  
88.     pthread_t id1,id2;  
89.   
90.     ret = sem_init(&mutex ,0,1);  
91.     if(ret != 0){  
92.         perror("sem_init error");  
93.     }  
94.     printf("please input node_num /n");  
95.     scanf("%d",&num);  
96.     head = Create_loop_chain(num);  
97.     printf("The ringbuf was found/n");  
98.     Show(head);  
99.   
100.     ret = pthread_create(&id1,NULL,(void *)write_buf,head);  
101.     ret = pthread_create(&id2,NULL,(void *)read_buf,head);  
102.   
103.     pthread_join(id1,NULL);  
104.     pthread_join(id2,NULL);  
105.       
106.   
107.     return 0;  
108. }  

zuozhongkai

好东西啊，谢谢分享

正点原子

不错，谢谢分享。。。

sdwhupk

在数组实现的时候我们使用
int next_data_handle(int addr)     
{  addr++;   
    addr%= MAXSIZE  ;     
}     
如果是通信的接收一组数据，数据未接收完成但到了数组的末尾，余下的数据要从数组的起始处存储；
这个时候有没有好的办法来判断数组接收完成。

sdwhupk

我们在判断的时候使用的结构体。

巅峰残狼

回复【4楼】sdwhupk:
---------------------------------
我的理解是，当接收一组数据的时候，把需要接收的数据包加包头和包尾，然后接收判断即可知道什么时候接收完成。

sdwhupk

回复【6楼】巅峰残狼:
---------------------------------
正常的判断是没有问题的，但是如果出现一包的数据接收一部分，缓冲区到了末尾，其他的数据就会放到缓冲区的头部了，这个时候用结构体来判断的话就容易出现。

w0rmis20

为什么要判断数组是否完成？只要不溢出不就好了么

巅峰残狼

回复【7楼】sdwhupk:
---------------------------------
放在包头也无所谓啊，本来就是个环形缓冲区，环状的，收尾相连。。。。。

巅峰残狼

回复【8楼】w0rmis20:
---------------------------------
定义的时候会定义缓冲区大小，一般数据包不超过这个缓冲区大小都不会溢出，所以必须判断数据包是否接收完成

w0rmis20

这个是协议层考虑的事，也不是在环形缓冲区里判断的啊

巅峰残狼

回复【11楼】w0rmis20:
---------------------------------
数据包是协议层定义的，但是定义归定义，在发送的时候是有包头和包尾的，此时我串口接收这个数据包，将这个数据包存储在缓冲区里，如果我不想把包头和包尾存在缓冲区的话我是不是需要判断呢

sdwhupk

通信是需要发送一些数据的，根据协议需要判断数据是否接受完成。

巅峰残狼

回复【13楼】sdwhupk:
---------------------------------
所以才会有包尾的存在，便于判断接收完成。。。。

sdwhupk

我提出的问题有好的解决方法吗？

shihantu

回复【15楼】sdwhupk:
---------------------------------
你的应用不适合使用FIFO .

要使用也可以 , 增加一个函数 , 实现 char GetData ( void* pAddr, int nOffset ) , 里面实现地址回滚 , 和返回数据操作 . 剩下的就是协议层如何判断的问题了 .

sdwhupk

谢谢。
那关于这个问题有什么好的解决方法吗？