單片機(jī)開發(fā)過程中通常會用到“消息隊列”，一般實現(xiàn)的方法有多種。 本文給大家分享一下隊列實現(xiàn)的原理和機(jī)制。

環(huán)形隊列

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

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

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

內(nèi)存上沒有環(huán)形的結(jié)構(gòu)，因此環(huán)形隊列實上是數(shù)組的線性空間來實現(xiàn)。 當(dāng)數(shù)據(jù)到了尾部它將轉(zhuǎn)回到0位置來處理。

因此環(huán)列隊列的邏輯：將數(shù)組元素q[0]與q[MAXN-1]連接，形成一個存放隊列的環(huán)形空間。

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

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

如何判斷環(huán)形隊列為空，為滿有兩種判斷方法：

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

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

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

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

隊列空： head==tail

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

2.附加標(biāo)志實現(xiàn)原理

a.采用第一個環(huán)形隊列有如下結(jié)構(gòu):

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

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

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

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

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

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

#ifndef __RINGQ_H__
#define __RINGQ_H__


#ifdef __cplusplus
extern "C" {
#endif 


#define QUEUE_MAX 20


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


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


extern int ringq_init(RINGQ * p_queue);


extern int ringq_free(RINGQ * p_queue);




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


/* 從隊列取數(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__ */

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


   /* 這個時候一定隊列滿了*/
   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 ;


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

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

消息隊列

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

1.消息隊列的基本概念

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

通過消息隊列服務(wù)，任務(wù)或中斷服務(wù)程序可以將一條或多條消息放入消息隊列中。同樣，一個或多個任務(wù)可以從消息隊列中獲得消息。

使用消息隊列數(shù)據(jù)結(jié)構(gòu)可以實現(xiàn)任務(wù)異步通信工作。

2.消息隊列的特性

RTOS消息隊列，常見特性：

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

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

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

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

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

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

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

3.消息隊列的原理

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

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

xQueue = xQueueCreate(QUEUE_LEN, QUEUE_SIZE);

任務(wù)或者中斷服務(wù)程序都可以給消息隊列發(fā)送消息，當(dāng)發(fā)送消息時，如果隊列未滿或者允許覆蓋入隊，F(xiàn)reeRTOS 會將消息拷貝到消息隊列隊尾，否則，會根據(jù)用戶指定的阻塞超時時間進(jìn)行阻塞，在這段時間中，如果隊列一直不允許入隊，該任務(wù)將保持阻塞狀態(tài)以等待隊列允許入隊。 當(dāng)其它任務(wù)從其等待的隊列中讀取入了數(shù)據(jù)（隊列未滿），該任務(wù)將自動由阻塞態(tài)轉(zhuǎn)移為就緒態(tài)。 當(dāng)?shù)却臅r間超過了指定的阻塞時間，即使隊列中還不允許入隊，任務(wù)也會自動從阻塞態(tài)轉(zhuǎn)移為就緒態(tài)，此時發(fā)送消息的任務(wù)或者中斷程序會收到一個錯誤碼 errQUEUE_FULL。

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

當(dāng)某個任務(wù)試圖讀一個隊列時，其可以指定一個阻塞超時時間。 在這段時間中，如果隊列為空，該任務(wù)將保持阻塞狀態(tài)以等待隊列數(shù)據(jù)有效。 當(dāng)其它任務(wù)或中斷服務(wù)程序往其等待的隊列中寫入了數(shù)據(jù)，該任務(wù)將自動由阻塞態(tài)轉(zhuǎn)移為就緒態(tài)。 當(dāng)?shù)却臅r間超過了指定的阻塞時間，即使隊列中尚無有效數(shù)據(jù)，任務(wù)也會自動從阻塞態(tài)轉(zhuǎn)移為就緒態(tài)。

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

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

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

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

入隊阻塞：當(dāng)且僅當(dāng)隊列允許入隊的時候，發(fā)送者才能成功發(fā)送消息； 隊列中無可用消息空間時，說明消息隊列已滿，此時，系統(tǒng)會根據(jù)用戶指定的阻塞超時時間將任務(wù)阻塞。

假如有多個任務(wù)阻塞在一個消息隊列中，那么這些阻塞的任務(wù)將按照任務(wù)優(yōu)先級進(jìn)行排序，優(yōu)先級高的任務(wù)將優(yōu)先獲得隊列的訪問權(quán)。

“環(huán)形隊列”和“消息隊列”的異同

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

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

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

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

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

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

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

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

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

審核編輯：湯梓紅