1、環(huán)形緩沖區(qū)的實現(xiàn)原理
環(huán)形緩沖區(qū)通常有一個讀指針和一個寫指針。讀指針指向環(huán)形緩沖區(qū)中可讀的數(shù)據(jù)，寫指針指向環(huán)形緩沖區(qū)中可寫的緩沖區(qū)。通過移動讀指針和寫指針就可以實現(xiàn)緩沖區(qū)的數(shù)據(jù)讀取和寫入。在通常情況下，環(huán)形緩沖區(qū)的讀用戶僅僅會影響讀指針，而寫用戶僅僅會影響寫指針。如果僅僅有一個讀用戶和一個寫用戶，那么不需要添加互斥保護機制就可以保證數(shù)據(jù)的正確性。如果有多個讀寫用戶訪問環(huán)形緩沖區(qū)，那么必須添加互斥保護機制來確保多個用戶互斥訪問環(huán)形緩沖區(qū)。
圖1、圖2和圖3是一個環(huán)形緩沖區(qū)的運行示意圖。圖1是環(huán)形緩沖區(qū)的初始狀態(tài)，可以看到讀指針和寫指針都指向第一個緩沖區(qū)處；圖2是向環(huán)形緩沖區(qū)中添加了一個數(shù)據(jù)后的情況，可以看到寫指針已經移動到數(shù)據(jù)塊2的位置，而讀指針沒有移動；圖3是環(huán)形緩沖區(qū)進行了讀取和添加后的狀態(tài)，可以看到環(huán)形緩沖區(qū)中已經添加了兩個數(shù)據(jù)，已經讀取了一個數(shù)據(jù)。
個數(shù)據(jù)。
2、實例：環(huán)形緩沖區(qū)的實現(xiàn)
環(huán)形緩沖區(qū)是數(shù)據(jù)通信程序中使用最為廣泛的數(shù)據(jù)結構之一，下面的代碼，實現(xiàn)了一個環(huán)形緩沖區(qū)：
/*ringbuf .c*/
＃include<stdio. h>
＃include<ctype. h>
#define NMAX 8
int iput = 0; /* 環(huán)形緩沖區(qū)的當前放入位置 */
int iget = 0; /* 緩沖區(qū)的當前取出位置 */
int n = 0; /* 環(huán)形緩沖區(qū)中的元素總數(shù)量 */
double buffer[NMAX];
/* 環(huán)形緩沖區(qū)的地址編號計算函數(shù)，如果到達喚醒緩沖區(qū)的尾部，將繞回到頭部。
環(huán)形緩沖區(qū)的有效地址編號為：0到(NMAX-1)
*/
int addring (int i)
{
return (i+1) == NMAX ? 0 : i+1;
}
/* 從環(huán)形緩沖區(qū)中取一個元素 */
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;
}
/* 向環(huán)形緩沖區(qū)中放入一個元素*/
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通信卡的通信能力、提高通信效率，根據(jù)CAN的特點，使用兩級緩沖區(qū)結構，即直接面向CAN通信卡的收發(fā)緩 沖區(qū)和直接面向系統(tǒng)調用的接收幀緩沖區(qū)。 通訊中的收發(fā)緩沖區(qū)一般采用環(huán)形隊列（或稱為FIFO隊列），使用環(huán)形的緩沖區(qū)可以使得讀寫并發(fā)執(zhí)行，讀進程和寫進程可以采用“生產者和消費者”的模型來 訪問緩沖區(qū)，從而方便了緩存的使用和管理。然而，環(huán)形緩沖區(qū)的執(zhí)行效率并不高，每讀一個字節(jié)之前，需要判斷緩沖區(qū)是否為空，并且移動尾指針時需要進行“折行處理”（即當指針指到緩沖區(qū)內存的末尾時，需要新將其定向到緩沖區(qū)的首地址）；每寫一個字節(jié)之前，需要判斷緩區(qū)是否為，并且移動尾指針時同樣需要進行“ 折行處理”。程序大部分的執(zhí)行過程都是在處理個別極端的情況。只有小部分在進行實際有效的操作。這就是軟件工程中所謂的“8比2”關系。結合CAN通訊實際情況，在本設計中對環(huán)形隊列進行了改進，可以較大地提高數(shù)據(jù)的收發(fā)效率。 由于CAN通信卡上接收和發(fā)送緩沖器每次只接收一幀CAN數(shù)據(jù)，而且根據(jù)CAN的通訊協(xié)議，CAN控制器的發(fā)送數(shù)據(jù)由1個字節(jié)的標識符、一個字節(jié)的RTR 和DLC位及8個字節(jié)的數(shù)據(jù)區(qū)組成，共10個字節(jié)；接收緩沖器與之類似，也有10個字節(jié)的寄存器。所以CAN控制器收的數(shù)據(jù)是短小的定長幀（數(shù)據(jù)可以不滿 8字節(jié)）。 于是，采用度為10字節(jié)的數(shù)據(jù)塊業(yè)分配內存比較方便，即每次需要內存緩沖區(qū)時，直接分配10個字節(jié)，由于這10個字節(jié)的地址是線性的，故不需要進行“折行”處理。更重要的是，在向緩沖區(qū)中寫數(shù)據(jù)時，只需要判斷一次是否有空閑塊并獲取其塊首指針就可以了，從而減少了重復性的條件判斷，大大提高了程序的執(zhí)行效率；同樣在從緩沖隊列中讀取數(shù)據(jù)時，也是一次讀取10字節(jié)的數(shù)據(jù)塊，同樣減少了重復性的條件判斷。 在CAN卡驅動程序中采用如下所示的稱為“Block_Ring_t”的數(shù)據(jù)結構作為收發(fā)數(shù)據(jù)的緩沖區(qū)：
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;
該數(shù)據(jù)結構在通用的環(huán)形隊列上增加了一個數(shù)據(jù)成員usedbytes，它表示當前緩沖區(qū)中有多少字節(jié)的空間被占用了。使用usedbytes，可以比較方 便地進行緩沖區(qū)滿或空的判斷。當usedbytes=0時，緩沖區(qū)空；當usedbytes=BLOCK_RING_BUFFER_SIZE時，緩沖區(qū) 滿。 本驅動程序除了收發(fā)緩沖區(qū)外，還有一個接收幀緩沖區(qū)，接收幀隊列負責管理經Hilon A協(xié)議解包后得到的數(shù)據(jù)幀。由于有可能要同接收多個數(shù)據(jù)幀，而根據(jù)CAN總線遙通信協(xié)議，高優(yōu)先級的報文將搶占總線，則有可能在接收一個低優(yōu)先級且被分為 好幾段發(fā)送的數(shù)據(jù)幀時，被一個優(yōu)先級高的數(shù)據(jù)幀打斷。這樣會出現(xiàn)同時接收到多個數(shù)據(jù)幀中的數(shù)據(jù)包，因而需要有個接收隊列對同時接收的數(shù)據(jù)幀進行管理。 當有新的數(shù)據(jù)包到來時，應根據(jù)addr(通訊地址)，mode（通訊方式），index（數(shù)據(jù)包的序號）來判斷是否是新的數(shù)據(jù)幀。如果是，則開辟新的 frame_node；否則如果已有相應的幀節(jié)點存地，則將數(shù)據(jù)附加到該幀的末尾；在插入數(shù)據(jù)的同時，應該檢查接收包的序號是否正確，如不正確將丟棄這包 數(shù)據(jù)。 每次建立新的frame_node時，需要向frame_queue申請內存空間；當frame_queue已滿時，釋放掉隊首的節(jié)點（最早接收的但未完 成的幀）并返回該節(jié)點的指針。 當系統(tǒng)調用讀取了接收幀后，釋放該節(jié)點空間，使設備驅動程序可以重新使用該節(jié)點。
形緩沖區(qū):環(huán)形緩沖隊列學習
來源: 發(fā)布時間:星期四, 2008年9月25日 瀏覽:117次 評論:0
項目中需要線程之間共享一個緩沖FIFO隊列，一個線程往隊列中添數(shù)據(jù)，另一個線程取數(shù)據(jù)（經典的生產者-消費者問題）。開始考慮用STL的vector 容器, 但不需要隨機訪問，頻繁的刪除最前的元素引起內存移動，降低了效率。使用LinkList做隊列的話，也需要頻繁分配和釋放結點內存。于是自己實現(xiàn)一個有 限大小的FIFO隊列，直接采用數(shù)組進行環(huán)形讀取。
隊列的讀寫需要在外部進程線程同步（另外寫了一個RWGuard類, 見另一文）
到項目的針對性簡單性，實現(xiàn)了一個簡單的環(huán)形緩沖隊列，比STL的vector簡單
PS: 第一次使用模板，原來類模板的定義要放在.h 文件中， 不然會出現(xiàn)連接錯誤。
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:需要外部數(shù)據(jù)一致性
return m_capacity;
}
//返回當前個數(shù)
unsigned int size() { //warning:需要外部數(shù)據(jù)一致性
return m_size;
}
//是否滿//warning: 需要外部控制數(shù)據(jù)一致性
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