正文

“環(huán)形隊(duì)列”和“消息隊(duì)列”在嵌入式領(lǐng)域有應(yīng)用非常廣泛，相信有經(jīng)驗(yàn)的嵌入式軟件工程師對(duì)它們都不陌生。 但經(jīng)常看到一些初學(xué)者問一些相關(guān)的問題，今天就來分享一下關(guān)于“環(huán)形隊(duì)列”和“消息隊(duì)列”的內(nèi)容。

1

環(huán)形隊(duì)列

環(huán)形隊(duì)列是在實(shí)際編程極為有用的數(shù)據(jù)結(jié)構(gòu)，它是一個(gè)首尾相連的FIFO的數(shù)據(jù)結(jié)構(gòu)，采用數(shù)組的線性空間，數(shù)據(jù)組織簡(jiǎn)單，能很快知道隊(duì)列是否滿為空，能以很快速度的來存取數(shù)據(jù)。

環(huán)形隊(duì)列通常用于通信領(lǐng)域，比如UART、USB、CAN、網(wǎng)絡(luò)等。

1.環(huán)形隊(duì)列實(shí)現(xiàn)原理

內(nèi)存上沒有環(huán)形的結(jié)構(gòu)，因此環(huán)形隊(duì)列實(shí)上是數(shù)組的線性空間來實(shí)現(xiàn)。當(dāng)數(shù)據(jù)到了尾部它將轉(zhuǎn)回到0位置來處理。 因此環(huán)列隊(duì)列的邏輯：將數(shù)組元素q[0]與q[MAXN-1]連接，形成一個(gè)存放隊(duì)列的環(huán)形空間。

為了方便讀寫，還要用數(shù)組下標(biāo)來指明隊(duì)列的讀寫位置。head/tail.其中head指向可以讀的位置，tail指向可以寫的位置。

環(huán)形隊(duì)列的關(guān)鍵是判斷隊(duì)列為空，還是為滿。當(dāng)tail追上head時(shí)，隊(duì)列為滿時(shí)；當(dāng)head追上tail時(shí)，隊(duì)列為空。但如何知道誰追上誰，還需要一些輔助的手段來判斷. 如何判斷環(huán)形隊(duì)列為空，為滿有兩種判斷方法：

a.附加一個(gè)標(biāo)志位tag

當(dāng)head趕上tail，隊(duì)列空，則令tag=0

當(dāng)tail趕上head，隊(duì)列滿，則令tag=1

b.限制tail趕上head，即隊(duì)尾結(jié)點(diǎn)與隊(duì)首結(jié)點(diǎn)之間至少留有一個(gè)元素的空間。

隊(duì)列空： head==tail

隊(duì)列滿： (tail+1)% MAXN ==head

2.附加標(biāo)志實(shí)現(xiàn)原理 a.采用第一個(gè)環(huán)形隊(duì)列有如下結(jié)構(gòu):

typedef struct ringq{
   int head; /* 頭部，出隊(duì)列方向*/
   int tail; /* 尾部，入隊(duì)列方向*/ 
   int tag ;
   int size ; /* 隊(duì)列總尺寸 */
   int space[RINGQ_MAX]; /* 隊(duì)列空間 */
}RINGQ;

初始化狀態(tài)：

q->head = q->tail = q->tag = 0;

隊(duì)列為空：

( q->head == q->tail) && (q->tag == 0)

隊(duì)列為滿 ：

 ((q->head == q->tail) && (q->tag == 1))

入隊(duì)操作，如隊(duì)列不滿，則寫入：

q->tail =  (q->tail + 1) % q->size ;

出隊(duì)操作，如果隊(duì)列不空，則從head處讀出。

下一個(gè)可讀的位置在：

q->head =  (q->head + 1) % q->size

b.完整代碼 頭文件ringq.h:

#ifndef __RINGQ_H__
#define __RINGQ_H__


#ifdef __cplusplus
extern "C" {
#endif 


#define QUEUE_MAX 20


typedef struct ringq{
   int head; /* 頭部，出隊(duì)列方向*/
   int tail; /* 尾部，入隊(duì)列方向*/ 
   int tag ; /* 為空還是為滿的標(biāo)志位*/
    int size ; /* 隊(duì)列總尺寸 */
   int space[QUEUE_MAX]; /* 隊(duì)列空間 */
}RINGQ;


/* 
  第一種設(shè)計(jì)方法:
     當(dāng)head == tail 時(shí)，tag = 0 為空，等于 = 1 為滿。
*/


extern int ringq_init(RINGQ * p_queue);


extern int ringq_free(RINGQ * p_queue);




/* 加入數(shù)據(jù)到隊(duì)列 */
extern int ringq_push(RINGQ * p_queue,int data);


/* 從隊(duì)列取數(shù)據(jù) */
extern int ringq_poll(RINGQ * p_queue,int *p_data);




#define ringq_is_empty(q) ( (q->head == q->tail) && (q->tag == 0))


#define ringq_is_full(q) ( (q->head == q->tail) && (q->tag == 1))


#define print_ringq(q) printf("ring head %d,tail %d,tag %d
", q->head,q->tail,q->tag);
#ifdef __cplusplus
}
#endif 


#endif /* __RINGQ_H__ */

源代碼 ringq.c：

#include 
#include "ringq.h"


int ringq_init(RINGQ * p_queue)
{
   p_queue->size = QUEUE_MAX ;


   p_queue->head = 0;
   p_queue->tail = 0;


   p_queue->tag = 0;


   return 0;
}


int ringq_free(RINGQ * p_queue)
{
  return 0;
}




int ringq_push(RINGQ * p_queue,int data)
{
  print_ringq(p_queue);


  if(ringq_is_full(p_queue))
   {


     printf("ringq is full
");
     return -1;
   }


   p_queue->space[p_queue->tail] = data;


   p_queue->tail = (p_queue->tail + 1) % p_queue->size ;


   /* 這個(gè)時(shí)候一定隊(duì)列滿了*/
   if(p_queue->tail == p_queue->head)
    {
       p_queue->tag = 1;
    }


    return p_queue->tag ;  
}


int ringq_poll(RINGQ * p_queue,int * p_data)
{
   print_ringq(p_queue);
  if(ringq_is_empty(p_queue))
   {


      printf("ringq is empty
");
     return -1;
   }


   *p_data = p_queue->space[p_queue->head];


   p_queue->head = (p_queue->head + 1) % p_queue->size ;


    /* 這個(gè)時(shí)候一定隊(duì)列空了*/
   if(p_queue->tail == p_queue->head)
    {
       p_queue->tag = 0;
    }    
    return p_queue->tag ;
}

看到源代碼，相信大家就明白其中原理了。其實(shí)還有不采用tag，或者其他一些標(biāo)志的方法，這里就不進(jìn)一步展開講述了，感興趣的讀者可以自行研究一下。

2

消息隊(duì)列

在RTOS中基本都有消息隊(duì)列這個(gè)組件，也是使用最常見的組件之一。

1.消息隊(duì)列的基本概念

消息隊(duì)列是一種常用于任務(wù)間通信的數(shù)據(jù)結(jié)構(gòu)，隊(duì)列可以在任務(wù)與任務(wù)間、中斷和任務(wù)間傳遞信息，實(shí)現(xiàn)了任務(wù)接收來自其他任務(wù)或中斷的不固定長(zhǎng)度的消息。

通過消息隊(duì)列服務(wù)，任務(wù)或中斷服務(wù)程序可以將一條或多條消息放入消息隊(duì)列中。同樣，一個(gè)或多個(gè)任務(wù)可以從消息隊(duì)列中獲得消息。 使用消息隊(duì)列數(shù)據(jù)結(jié)構(gòu)可以實(shí)現(xiàn)任務(wù)異步通信工作。

2.消息隊(duì)列的特性

RTOS

消息隊(duì)列，常見特性：

消息支持先進(jìn)先出方式排隊(duì)，支持異步讀寫工作方式。

讀寫隊(duì)列均支持超時(shí)機(jī)制。

消息支持后進(jìn)先出方式排隊(duì)，往隊(duì)首發(fā)送消息（LIFO）。

可以允許不同長(zhǎng)度（不超過隊(duì)列節(jié)點(diǎn)最大值）的任意類型消息。

一個(gè)任務(wù)能夠從任意一個(gè)消息隊(duì)列接收和發(fā)送消息。

多個(gè)任務(wù)能夠從同一個(gè)消息隊(duì)列接收和發(fā)送消息。

當(dāng)隊(duì)列使用結(jié)束后，可以通過刪除隊(duì)列函數(shù)進(jìn)行刪除。

3.消息隊(duì)列的原理

這里以 FreeRTOS 為例進(jìn)行說明。FreeRTOS 的消息隊(duì)列控制塊由多個(gè)元素組成，當(dāng)消息隊(duì)列被創(chuàng)建時(shí)，系統(tǒng)會(huì)為控制塊分配對(duì)應(yīng)的內(nèi)存空間，用于保存消息隊(duì)列的一些信息如消息的存儲(chǔ)位置，頭指針 pcHead、尾指針 pcTail、消息大小 uxItemSize 以及隊(duì)列長(zhǎng)度 uxLength 等。

比如創(chuàng)建消息隊(duì)列：

xQueue = xQueueCreate(QUEUE_LEN, QUEUE_SIZE);

任務(wù)或者中斷服務(wù)程序都可以給消息隊(duì)列發(fā)送消息，當(dāng)發(fā)送消息時(shí)，如果隊(duì)列未滿或者允許覆蓋入隊(duì)，F(xiàn)reeRTOS 會(huì)將消息拷貝到消息隊(duì)列隊(duì)尾，否則，會(huì)根據(jù)用戶指定的阻塞超時(shí)時(shí)間進(jìn)行阻塞，在這段時(shí)間中，如果隊(duì)列一直不允許入隊(duì)，該任務(wù)將保持阻塞狀態(tài)以等待隊(duì)列允許入隊(duì)。

當(dāng)其它任務(wù)從其等待的隊(duì)列中讀取入了數(shù)據(jù)（隊(duì)列未滿），該任務(wù)將自動(dòng)由阻塞態(tài)轉(zhuǎn)移為就緒態(tài)。

當(dāng)?shù)却臅r(shí)間超過了指定的阻塞時(shí)間，即使隊(duì)列中還不允許入隊(duì)，任務(wù)也會(huì)自動(dòng)從阻塞態(tài)轉(zhuǎn)移為就緒態(tài)，此時(shí)發(fā)送消息的任務(wù)或者中斷程序會(huì)收到一個(gè)錯(cuò)誤碼 errQUEUE_FULL。

發(fā)送緊急消息的過程與發(fā)送消息幾乎一樣，唯一的不同是，當(dāng)發(fā)送緊急消息時(shí)， 發(fā)送的位置是消息隊(duì)列隊(duì)頭而非隊(duì)尾，這樣，接收者就能夠優(yōu)先接收到緊急消息，從而及時(shí)進(jìn)行消息處理。

當(dāng)某個(gè)任務(wù)試圖讀一個(gè)隊(duì)列時(shí)，其可以指定一個(gè)阻塞超時(shí)時(shí)間。

在這段時(shí)間中，如果隊(duì)列為空，該任務(wù)將保持阻塞狀態(tài)以等待隊(duì)列數(shù)據(jù)有效。當(dāng)其它任務(wù)或中斷服務(wù)程序往其等待的隊(duì)列中寫入了數(shù)據(jù)，該任務(wù)將自動(dòng)由阻塞態(tài)轉(zhuǎn)移為就緒態(tài)。

當(dāng)?shù)却臅r(shí)間超過了指定的阻塞時(shí)間，即使隊(duì)列中尚無有效數(shù)據(jù)，任務(wù)也會(huì)自動(dòng)從阻塞態(tài)轉(zhuǎn)移為就緒態(tài)。

當(dāng)消息隊(duì)列不再被使用時(shí)，應(yīng)該刪除它以釋放系統(tǒng)資源，一旦操作完成， 消息隊(duì)列將被永久性的刪除。

消息隊(duì)列的運(yùn)作過程具體見下圖：

4.消息隊(duì)列的阻塞機(jī)制

出隊(duì)阻塞：當(dāng)且僅當(dāng)消息隊(duì)列有數(shù)據(jù)的時(shí)候，任務(wù)才能讀取到數(shù)據(jù)，可以指定等待數(shù)據(jù)的阻塞時(shí)間。

入隊(duì)阻塞：當(dāng)且僅當(dāng)隊(duì)列允許入隊(duì)的時(shí)候，發(fā)送者才能成功發(fā)送消息；隊(duì)列中無可用消息空間時(shí)，說明消息隊(duì)列已滿，此時(shí)，系統(tǒng)會(huì)根據(jù)用戶指定的阻塞超時(shí)時(shí)間將任務(wù)阻塞。 假如有多個(gè)任務(wù)阻塞在一個(gè)消息隊(duì)列中，那么這些阻塞的任務(wù)將按照任務(wù)優(yōu)先級(jí)進(jìn)行排序，優(yōu)先級(jí)高的任務(wù)將優(yōu)先獲得隊(duì)列的訪問權(quán)。

3

環(huán)形隊(duì)列與消息隊(duì)列的異同

通過以上分析，你會(huì)發(fā)現(xiàn)“環(huán)形隊(duì)列”和“消息隊(duì)列”之間有很多共同點(diǎn)：

1.他們都是一種數(shù)據(jù)結(jié)構(gòu)，結(jié)構(gòu)中都包含頭、尾、標(biāo)志等信息；

2.它們都是分配一塊連續(xù)的內(nèi)存空間，且都可以分配多個(gè)隊(duì)列。

3.應(yīng)用場(chǎng)景類似，有大量吞吐數(shù)據(jù)的情況下，比如通信領(lǐng)域。

... 當(dāng)然，他們也有一些不同點(diǎn)：

1.“環(huán)形隊(duì)列”可以獨(dú)立使用，也可以結(jié)合操作系統(tǒng)使用。而消息隊(duì)列依賴RTOS（有些RTOS的參數(shù)信息）。

2.“環(huán)形隊(duì)列”占用資源更小，更適合于資源較小的系統(tǒng)中。

3.“消息隊(duì)列”結(jié)合RTOS應(yīng)用更加靈活，比如延時(shí)、中斷傳輸數(shù)據(jù)等。

... 最后，這兩種隊(duì)列應(yīng)用都比較廣，建議抽空都研究一下。

審核編輯：劉清