正文

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

1

環(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)絡等。

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

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

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

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

a.附加一個標志位tag

當head趕上tail，隊列空，則令tag=0

當tail趕上head，隊列滿，則令tag=1

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

隊列空： head==tail

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

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

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

初始化狀態(tài)：

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 ;

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

下一個可讀的位置在：

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; /* 頭部，出隊列方向*/
   int tail; /* 尾部，入隊列方向*/ 
   int tag ; /* 為空還是為滿的標志位*/
    int size ; /* 隊列總尺寸 */
   int space[QUEUE_MAX]; /* 隊列空間 */
}RINGQ;


/* 
  第一種設(shè)計方法:
     當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__ */

源代碼 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 ;


   /* 這個時候一定隊列滿了*/
   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，或者其他一些標志的方法，這里就不進一步展開講述了，感興趣的讀者可以自行研究一下。

2

消息隊列

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

1.消息隊列的基本概念

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

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

2.消息隊列的特性

RTOS

消息隊列，常見特性：

消息支持先進先出方式排隊，支持異步讀寫工作方式。

讀寫隊列均支持超時機制。

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

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

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

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

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

3.消息隊列的原理

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

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

xQueue = xQueueCreate(QUEUE_LEN, QUEUE_SIZE);

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

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

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

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

當某個任務試圖讀一個隊列時，其可以指定一個阻塞超時時間。

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

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

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

消息隊列的運作過程具體見下圖：

4.消息隊列的阻塞機制

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

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

3

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

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

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

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

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

... 當然，他們也有一些不同點：

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

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

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

... 最后，這兩種隊列應用都比較廣，建議抽空都研究一下。

審核編輯：劉清