环形缓冲区的实现原理(ring buffer)(小寿转载 )-凯发app官方网站

凯发app官方网站-凯发k8官网下载客户端中心 | | 凯发app官方网站-凯发k8官网下载客户端中心
  • 博客访问: 72176
  • 博文数量: 7
  • 博客积分: 0
  • 博客等级: 民兵
  • 技术积分: 40
  • 用 户 组: 普通用户
  • 注册时间: 2014-01-08 11:24
文章分类

全部博文(7)

文章存档

2014年(7)

相关博文
  • ·
  • ·
  • ·
  • ·
  • ·
  • ·
  • ·
  • ·
  • ·
  • ·

分类: linux

2014-01-28 16:41:51

原文地址: 作者:

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

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

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

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

 

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

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

/*ringbuf .c*/

include

    include

#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 getvoid

{

int 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;

}

 


can通信卡设备驱动程序中,为了增强can通信卡的通信能力、提高通信效率,根据can的特点,使用两级缓冲区结构,即直接面向can通信卡的收发缓冲区和直接面向系统调用的接收帧缓冲区。通讯中的收发缓冲区一般采用环形队列(或称为fifo队列),使用环形的缓冲区可以使得读写并发执行,读进程和写进程可以采用生产者和消费者的模型来访问缓冲区,从而方便了缓存的使用和管理。然而,环形缓冲区的执行效率并不高,每读一个字节之前,需要判断缓冲区是否为空,并且移动尾指针时需要进行折行处理(即当指针指到缓冲区内存的末尾时,需要新将其定向到缓冲区的首地址);每写一个字节之前,需要判断缓区是否为,并且移动尾指针时同样需要进行折行处理。程序大部分的执行过程都是在处理个别极端的情况。只有小部分在进行实际有效的操作。这就是软件工程中所谓的“82”关系。结合can通讯实际情况,在本设计中对环形队列进行了改进,可以较大地提高数据的收发效率。由于can通信卡上接收和发送缓冲器每次只接收一帧can数据,而且根据can的通讯协议,can控制器的发送数据由1个字节的标识符、一个字节的rtr dlc位及8个字节的数据区组成,共10个字节;接收缓冲器与之类似,也有10个字节的寄存器。所以can控制器收的数据是短小的定长帧(数据可以不满 8字节)。于是,采用度为10字节的数据块业分配内存比较方便,即每次需要内存缓冲区时,直接分配10个字节,由于这10个字节的地址是线性的,故不需要进行折行处理。更重要的是,在向缓冲区中写数据时,只需要判断一次是否有空闲块并获取其块首指针就可以了,从而减少了重复性的条件判断,大大提高了程序的执行效率;同样在从缓冲队列中读取数据时,也是一次读取10字节的数据块,同样减少了重复性的条件判断。can卡驱动程序中采用如下所示的称为“block_ring_t”的数据结构作为收发数据的缓冲区:

 

 

typedef struct {

long signature;

unsigned char *head_p;

unsigned char *tail_p;

unsigned char *begin_p;

unsigned char *end_p;

unsigned char buffer [block_ring_buffer_size];

int usedbytes;

}block_ring_t;

 

 

该数据结构在通用的环形队列上增加了一个数据成员usedbytes,它表示当前缓冲区中有多少字节的空间被占用了。使用usedbytes,可以比较方便地进行缓冲区满或空的判断。当usedbytes=0时,缓冲区空;当usedbytes=block_ring_buffer_size时,缓冲区满。本驱动程序除了收发缓冲区外,还有一个接收帧缓冲区,接收帧队列负责管理经hilon a协议解包后得到的数据帧。由于有可能要同接收多个数据帧,而根据can总线遥通信协议,高优先级的报文将抢占总线,则有可能在接收一个低优先级且被分为好几段发送的数据帧时,被一个优先级高的数据帧打断。这样会出现同时接收到多个数据帧中的数据包,因而需要有个接收队列对同时接收的数据帧进行管理。当有新的数据包到来时,应根据addr(通讯地址)mode(通讯方式),index(数据包的序号)来判断是否是新的数据帧。如果是,则开辟新的 frame_node;否则如果已有相应的帧节点存地,则将数据附加到该帧的末尾;在插入数据的同时,应该检查接收包的序号是否正确,如不正确将丢弃这包数据。每次建立新的frame_node时,需要向frame_queue申请内存空间;当frame_queue已满时,释放掉队首的节点(最早接收的但未完成的帧)并返回该节点的指针。当系统调用读取了接收帧后,释放该节点空间,使设备驱动程序可以重新使用该节点。

 


形缓冲区:环形缓冲队列学习

来源: 发布时间:星期四, 2008925日 浏览:117次 评论:0

项目中需要线程之间共享一个缓冲fifo队列,一个线程往队列中添数据,另一个线程取数据(经典的生产者-消费者问题)。开始考虑用stlvector 容器, 但不需要随机访问,频繁的删除最前的元素引起内存移动,降低了效率。使用linklist做队列的话,也需要频繁分配和释放结点内存。于是自己实现一个有 限大小的fifo队列,直接采用数组进行环形读取。

队列的读写需要在外部进程线程同步(另外写了一个rwguard, 见另一文)

到项目的针对性简单性,实现了一个简单的环形缓冲队列,比stlvector简单

ps: 第一次使用模板,原来类模板的定义要放在.h 文件中, 不然会出现连接错误。

template
class csharequeue
{
public:
csharequeue();
csharequeue(unsigned int bufsize);
virtual ~csharequeue();

_type pop_front();
bool push_back( _type item);
//
返回容量
unsigned int capacity() { //warning:
需要外部数据一致性
return m_capacity;
}
//
返回当前个数
unsigned int size() { //warning:
需要外部数据一致性
return m_size;
}
//
是否满//warning: 需要外部控制数据一致性
bool isfull() {
return (m_size >= m_capacity);
}

bool isempty() {
return (m_size == 0);
}


protected:
uint m_head;
uint m_tail;
uint m_size;
uint m_capacity;
_type *pbuf;


};

template
csharequeue<_type>::csharequeue() : m_head(0), m_tail(0), m_size(0)
{
pbuf = new _type[512];//
默认512
m_capacity = 512;
}

template
csharequeue<_type>::csharequeue(unsigned int bufsize) : m_head(0), m_tail(0)
{
if( bufsize > 512 || bufsize < 1)
{
pbuf = new _type[512];
m_capacity = 512;
}
else
{
pbuf = new _type[bufsize];
m_capacity = bufsize;
}
}

template
csharequeue<_type>::~csharequeue()
{
delete[] pbuf;
pbuf = null;
m_head = m_tail = m_size = m_capacity = 0;
}

//前面弹出一个元素
template
_type csharequeue<_type>::pop_front()
{
if( isempty() )
{
return null;
}
_type itemtmp;
itemtmp = pbuf[m_head];
m_head = (m_head 1) % m_capacity;
--m_size;
return itemtmp;

}

//从尾部加入队列
template
bool csharequeue<_type>::push_back( _type item)
{
if ( isfull() )
{
return false;
}
pbuf[m_tail] = item;
m_tail = (m_tail 1) % m_capacity;
m_size;
return true;
}


#endif // !defined(_daly_csharequeue_h_)

 

阅读(3483) | 评论(0) | 转发(0) |
0

上一篇:

下一篇:内核同步---要保护些什么

给主人留下些什么吧!~~
")); function link(t){ var href= $(t).attr('href'); href ="?url=" encodeuricomponent(location.href); $(t).attr('href',href); //setcookie("returnouturl", location.href, 60, "/"); }
网站地图