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