正文

“環形隊列”和“消息隊列”在嵌入式領域有應用非常廣泛，相信有經驗的嵌入式軟件工程師對它們都不陌生。 但經常看到一些初學者問一些相關的問題，今天就來分享一下關于“環形隊列”和“消息隊列”的內容。

1

環形隊列

環形隊列是在實際編程極為有用的數據結構，它是一個首尾相連的FIFO的數據結構，采用數組的線性空間，數據組織簡單，能很快知道隊列是否滿為空，能以很快速度的來存取數據。

環形隊列通常用于通信領域，比如UART、USB、CAN、網絡等。

1.環形隊列實現原理

內存上沒有環形的結構，因此環形隊列實上是數組的線性空間來實現。當數據到了尾部它將轉回到0位置來處理。 因此環列隊列的邏輯：將數組元素q[0]與q[MAXN-1]連接，形成一個存放隊列的環形空間。

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

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

a.附加一個標志位tag

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

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

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

隊列空： head==tail

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

2.附加標志實現原理 a.采用第一個環形隊列有如下結構:

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 ;

出隊操作，如果隊列不空，則從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;


/* 
  第一種設計方法:
     當head == tail 時，tag = 0 為空，等于 = 1 為滿。
*/


extern int ringq_init(RINGQ * p_queue);


extern int ringq_free(RINGQ * p_queue);




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


/* 從隊列取數據 */
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.消息隊列的基本概念

消息隊列是一種常用于任務間通信的數據結構，隊列可以在任務與任務間、中斷和任務間傳遞信息，實現了任務接收來自其他任務或中斷的不固定長度的消息。

通過消息隊列服務，任務或中斷服務程序可以將一條或多條消息放入消息隊列中。同樣，一個或多個任務可以從消息隊列中獲得消息。 使用消息隊列數據結構可以實現任務異步通信工作。

2.消息隊列的特性

RTOS

消息隊列，常見特性：

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

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

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

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

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

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

當隊列使用結束后，可以通過刪除隊列函數進行刪除。

3.消息隊列的原理

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

比如創建消息隊列：

xQueue = xQueueCreate(QUEUE_LEN, QUEUE_SIZE);

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

當其它任務從其等待的隊列中讀取入了數據（隊列未滿），該任務將自動由阻塞態轉移為就緒態。

當等待的時間超過了指定的阻塞時間，即使隊列中還不允許入隊，任務也會自動從阻塞態轉移為就緒態，此時發送消息的任務或者中斷程序會收到一個錯誤碼 errQUEUE_FULL。

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

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

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

當等待的時間超過了指定的阻塞時間，即使隊列中尚無有效數據，任務也會自動從阻塞態轉移為就緒態。

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

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

4.消息隊列的阻塞機制

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

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

3

環形隊列與消息隊列的異同

通過以上分析，你會發現“環形隊列”和“消息隊列”之間有很多共同點：

1.他們都是一種數據結構，結構中都包含頭、尾、標志等信息；

2.它們都是分配一塊連續的內存空間，且都可以分配多個隊列。

3.應用場景類似，有大量吞吐數據的情況下，比如通信領域。

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

1.“環形隊列”可以獨立使用，也可以結合操作系統使用。而消息隊列依賴RTOS（有些RTOS的參數信息）。

2.“環形隊列”占用資源更小，更適合于資源較小的系統中。

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

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

審核編輯：劉清