在通信程序中，經常使用環形緩沖區作為數據結構來存放通信中發送和接收的數據。環形緩沖區是一個先進先出的循環緩沖區，可以向通信程序提供對緩沖區的互斥訪問。
1、環形緩沖區的實現原理
環形緩沖區通常有一個讀指針和一個寫指針。讀指針指向環形緩沖區中可讀的數據，寫指針指向環形緩沖區中可寫的緩沖區。通過移動讀指針和寫指針就可以實現緩沖區的數據讀取和寫入。在通常情況下，環形緩沖區的讀用戶僅僅會影響讀指針，而寫用戶僅僅會影響寫指針。如果僅僅有一個讀用戶和一個寫用戶，那么不需要添加互斥保護機制就可以保證數據的正確性。如果有多個讀寫用戶訪問環形緩沖區，那么必須添加互斥保護機制來確保多個用戶互斥訪問環形緩沖區。
圖1、圖2和圖3是一個環形緩沖區的運行示意圖。圖1是環形緩沖區的初始狀態，可以看到讀指針和寫指針都指向第一個緩沖區處；圖2是向環形緩沖區中添加了一個數據后的情況，可以看到寫指針已經移動到數據塊2的位置，而讀指針沒有移動；圖3是環形緩沖區進行了讀取和添加后的狀態，可以看到環形緩沖區中已經添加了兩個數據，已經讀取了一個數據。
個數據。
2、實例：環形緩沖區的實現
環形緩沖區是數據通信程序中使用最為廣泛的數據結構之一，下面的代碼，實現了一個環形緩沖區：
/*ringbuf .c*/
＃include<stdio. h>
＃include<ctype. h>
#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）
{
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<NMAX){
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隊列），使用環形的緩沖區可以使得讀寫并發執行，讀進程和寫進程可以采用“生產者和消費者”的模型來 訪問緩沖區，從而方便了緩存的使用和管理。然而，環形緩沖區的執行效率并不高，每讀一個字節之前，需要判斷緩沖區是否為空，并且移動尾指針時需要進行“折行處理”（即當指針指到緩沖區內存的末尾時，需要新將其定向到緩沖區的首地址）；每寫一個字節之前，需要判斷緩區是否為，并且移動尾指針時同樣需要進行“ 折行處理”。程序大部分的執行過程都是在處理個別極端的情況。只有小部分在進行實際有效的操作。這就是軟件工程中所謂的“8比2”關系。結合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已滿時，釋放掉隊首的節點（最早接收的但未完 成的幀）并返回該節點的指針。 當系統調用讀取了接收幀后，釋放該節點空間，使設備驅動程序可以重新使用該節點。
形緩沖區:環形緩沖隊列學習
來源: 發布時間:星期四, 2008年9月25日 瀏覽:117次 評論:0
項目中需要線程之間共享一個緩沖FIFO隊列，一個線程往隊列中添數據，另一個線程取數據（經典的生產者-消費者問題）。開始考慮用STL的vector 容器, 但不需要隨機訪問，頻繁的刪除最前的元素引起內存移動，降低了效率。使用LinkList做隊列的話，也需要頻繁分配和釋放結點內存。于是自己實現一個有 限大小的FIFO隊列，直接采用數組進行環形讀取。
隊列的讀寫需要在外部進程線程同步（另外寫了一個RWGuard類, 見另一文）
到項目的針對性簡單性，實現了一個簡單的環形緩沖隊列，比STL的vector簡單
PS: 第一次使用模板，原來類模板的定義要放在.h 文件中， 不然會出現連接錯誤。
template <class _Type>
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 <class _Type>
CShareQueue<_Type>::CShareQueue() : m_head(0), m_tail(0), m_size(0)
{
pBuf = new _Type[512];//默認512
m_capacity = 512;
}
template <class _Type>
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 <class _Type>
CShareQueue<_Type>::~CShareQueue()
{
delete[] pBuf;
pBuf = NULL;
m_head = m_tail = m_size = m_capacity = 0;
}
//前面彈出一個元素
template <class _Type>
_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 <class _Type>
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
|
|
QQ好友和群
QQ空間
騰訊微博
騰訊朋友
收藏
淘帖
頂
踩
