單片機消息隊列的實現原理和機制

來源：strongerHuang

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

環形隊列

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

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

1. 環形隊列實現原理

內存上沒有環形的結構，因此環形隊列實上是數組的線性空間來實現。當數據到了尾部它將轉回到 0 位置來處理。

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

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

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

如何判斷環形隊列爲空，爲滿有兩種判斷方法：

a. 附加一個標誌位 tag

b. 限制 tail 趕上 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\n", q->head,q->tail,q->tag);
#ifdef __cplusplus
}
#endif 
#endif /* __RINGQ_H__ */

源代碼 ringq.c：

#include <stdio.h>
#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\n");
     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\n");
     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，或者其他一些標誌的方法，這裏就不進一步展開講述了，感興趣的讀者可以自行研究一下。

消息隊列

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

1. 消息隊列的基本概念

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

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

使用消息隊列數據結構可以實現任務異步通信工作。

2. 消息隊列的特性

RTOS 消息隊列，常見特性：

3. 消息隊列的原理

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

比如創建消息隊列：

xQueue = xQueueCreate(QUEUE_LEN, QUEUE_SIZE);

任務或者中斷服務程序都可以給消息隊列發送消息，當發送消息時，如果隊列未滿或者允許覆蓋入隊，FreeRTOS 會將消息拷貝到消息隊列隊尾，否則，會根據用戶指定的阻塞超時時間進行阻塞，在這段時間中，如果隊列一直不允許入隊，該任務將保持阻塞狀態以等待隊列允許入隊。當其它任務從其等待的隊列中讀取入了數據（隊列未滿），該任務將自動由阻塞態轉移爲就緒態。當等待的時間超過了指定的阻塞時間，即使隊列中還不允許入隊，任務也會自動從阻塞態轉移爲就緒態，此時發送消息的任務或者中斷程序會收到一個錯誤碼 errQUEUE_FULL。

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

當某個任務試圖讀一個隊列時，其可以指定一個阻塞超時時間。在這段時間中，如果隊列爲空，該任務將保持阻塞狀態以等待隊列數據有效。當其它任務或中斷服務程序往其等待的隊列中寫入了數據，該任務將自動由阻塞態轉移爲就緒態。當等待的時間超過了指定的阻塞時間，即使隊列中尚無有效數據，任務也會自動從阻塞態轉移爲就緒態。

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

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

4. 消息隊列的阻塞機制

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

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

假如有多個任務阻塞在一個消息隊列中，那麼這些阻塞的任務將按照任務優先級進行排序，優先級高的任務將優先獲得隊列的訪問權。

“環形隊列”和 “消息隊列” 的異同

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

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

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

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

...

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

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

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

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

...

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

本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/qMmcQS6-7jt5FhJ52xqjLw

猜你喜歡