嵌入式環(huán)形隊(duì)列和消息隊(duì)列的實(shí)現(xiàn)

說明

嵌入式環(huán)形隊(duì)列和消息隊(duì)列是實(shí)現(xiàn)數(shù)據(jù)緩存和通信的常見數(shù)據(jù)結(jié)構(gòu)，廣泛應(yīng)用于嵌入式系統(tǒng)中的通信協(xié)議和領(lǐng)域。

環(huán)形隊(duì)列是一種先進(jìn)先出（FIFO）的數(shù)據(jù)結(jié)構(gòu)，其中數(shù)據(jù)被存儲(chǔ)在一個(gè)環(huán)形緩沖區(qū)中。 它使用兩個(gè)指針，分別指向隊(duì)列的頭和尾，以便在讀寫操作時(shí)追蹤隊(duì)列的狀態(tài)。 當(dāng)隊(duì)列滿時(shí)，新數(shù)據(jù)將覆蓋舊數(shù)據(jù)，以確保隊(duì)列的長度保持不變。 環(huán)形隊(duì)列在實(shí)現(xiàn)嵌入式通信協(xié)議時(shí)特別有用，例如UART，CAN等。

消息隊(duì)列是一種多個(gè)發(fā)送者和接收者之間共享數(shù)據(jù)的通信機(jī)制。 它允許多個(gè)任務(wù)或線程向隊(duì)列發(fā)送消息，并允許多個(gè)任務(wù)或線程從隊(duì)列中接收消息。 每個(gè)消息都有一個(gè)固定的大小和格式，并可以根據(jù)需要進(jìn)行排隊(duì)和檢索。 在嵌入式系統(tǒng)中，消息隊(duì)列廣泛用于處理異步事件，例如中斷處理和任務(wù)之間的通信。

主要應(yīng)用于：

1. 網(wǎng)絡(luò)通信協(xié)議（例如TCP/IP，UDP等）中的數(shù)據(jù)緩存和隊(duì)列管理。
2. 嵌入式操作系統(tǒng)（例如FreeRTOS，uC/OS等）中的任務(wù)通信和事件處理。
3. 汽車電子領(lǐng)域中的CAN和LIN通信協(xié)議。
4. 工業(yè)自動(dòng)化領(lǐng)域中的Modbus，Profibus等通信協(xié)議。
5. 無線通信領(lǐng)域中的藍(lán)牙，Zigbee，LoRa等通信協(xié)議。

大致應(yīng)用

1. 串口通信中，可以使用環(huán)形隊(duì)列來接收和發(fā)送數(shù)據(jù)。 當(dāng)接收到新的數(shù)據(jù)時(shí)，將其存儲(chǔ)到環(huán)形隊(duì)列中，并在需要發(fā)送數(shù)據(jù)時(shí)從隊(duì)列中取出數(shù)據(jù)發(fā)送。 這種方式可以減少中斷處理的時(shí)間，提高系統(tǒng)的響應(yīng)速度。
2. 多任務(wù)系統(tǒng)中，消息隊(duì)列用于任務(wù)之間的通信。 每個(gè)任務(wù)都可以向消息隊(duì)列中發(fā)送消息，其他任務(wù)可以從隊(duì)列中獲取消息并進(jìn)行相應(yīng)的處理。 這種方式可以實(shí)現(xiàn)任務(wù)之間的解耦，提高系統(tǒng)的可擴(kuò)展性和可維護(hù)性。
3. 實(shí)時(shí)控制系統(tǒng)中，環(huán)形隊(duì)列可以用于緩存傳感器數(shù)據(jù)或控制命令。 當(dāng)傳感器或其他設(shè)備向系統(tǒng)發(fā)送數(shù)據(jù)時(shí)，可以將其存儲(chǔ)到環(huán)形隊(duì)列中，然后由控制任務(wù)從隊(duì)列中獲取數(shù)據(jù)并進(jìn)行相應(yīng)的處理。 這種方式可以減少系統(tǒng)對硬件的依賴性，提高系統(tǒng)的靈活性和可靠性。
4. 音頻處理中，環(huán)形隊(duì)列可以用于實(shí)現(xiàn)音頻數(shù)據(jù)的緩存。 當(dāng)音頻數(shù)據(jù)輸入時(shí)，將其存儲(chǔ)到環(huán)形隊(duì)列中，然后由音頻處理任務(wù)從隊(duì)列中獲取數(shù)據(jù)并進(jìn)行處理。 這種方式可以實(shí)現(xiàn)音頻數(shù)據(jù)的流式處理，提高系統(tǒng)的處理效率和響應(yīng)速度。

嵌入式環(huán)形隊(duì)列

嵌入式環(huán)形隊(duì)列是一種先進(jìn)先出（FIFO）的隊(duì)列，其實(shí)現(xiàn)基于環(huán)形緩沖區(qū)。 隊(duì)列的頭尾指針分別指向隊(duì)列的第一個(gè)元素和最后一個(gè)元素，當(dāng)隊(duì)列滿時(shí)，新加入的元素將覆蓋隊(duì)列頭的元素。 嵌入式環(huán)形隊(duì)列的實(shí)現(xiàn)過程如下：

1. 隊(duì)列初始化：初始化頭尾指針為0，表示隊(duì)列為空。
2. 入隊(duì)操作：將元素插入隊(duì)列尾部，尾指針加1，如果隊(duì)列滿了，則尾指針回到隊(duì)列開頭，覆蓋頭指針?biāo)赶虻脑亍?/li>
3. 出隊(duì)操作：將隊(duì)列頭部元素出隊(duì)，并將頭指針加1，如果隊(duì)列已經(jīng)空了，則頭指針回到隊(duì)列開頭。

嵌入式環(huán)形隊(duì)列的實(shí)現(xiàn)可以使用數(shù)組或鏈表來實(shí)現(xiàn)。 使用數(shù)組時(shí)，需要考慮隊(duì)列滿時(shí)需要覆蓋隊(duì)列頭的元素，所以需要額外的邏輯來保證正確性。

嵌入式環(huán)形隊(duì)列操作步驟（大致如此）

1）定義一個(gè)固定大小的數(shù)組

1#define QUEUE_SIZE 10
2int queue[QUEUE_SIZE];

2）定義兩個(gè)指針，分別指向隊(duì)列的起始位置和末尾位置

1int head = 0;  // 隊(duì)列起始位置
2int tail = 0;  // 隊(duì)列末尾位置

3）實(shí)現(xiàn)入隊(duì)操作，即將元素添加到隊(duì)列末尾。 如果隊(duì)列已滿，則不能再添加元素

1void enqueue(int data) {
2    if ((tail + 1) % QUEUE_SIZE == head) {
3        // 隊(duì)列已滿
4        return;
5    }
6    queue[tail] = data;
7    tail = (tail + 1) % QUEUE_SIZE;
8}

4）實(shí)現(xiàn)出隊(duì)操作，即將隊(duì)列中的元素刪除并返回。 如果隊(duì)列為空，則不能執(zhí)行出隊(duì)操作。

1int dequeue() {
2    if (head == tail) {
3        // 隊(duì)列為空
4        return -1;
5    }
6    int data = queue[head];
7    head = (head + 1) % QUEUE_SIZE;
8    return data;
9}

5）實(shí)現(xiàn)查詢隊(duì)列大小的函數(shù)

1int queue_size() {
2    return (tail - head + QUEUE_SIZE) % QUEUE_SIZE;
3}

完整代碼實(shí)現(xiàn)

1#define QUEUE_SIZE 10
 2int queue[QUEUE_SIZE];
 3int head = 0;
 4int tail = 0;
 5
 6void enqueue(int data) {
 7    if ((tail + 1) % QUEUE_SIZE == head) {
 8        // 隊(duì)列已滿
 9        return;
10    }
11    queue[tail] = data;
12    tail = (tail + 1) % QUEUE_SIZE;
13}
14
15int dequeue() {
16    if (head == tail) {
17        // 隊(duì)列為空
18        return -1;
19    }
20    int data = queue[head];
21    head = (head + 1) % QUEUE_SIZE;
22    return data;
23}
24
25int queue_size() {
26    return (tail - head + QUEUE_SIZE) % QUEUE_SIZE;
27}

嵌入式消息隊(duì)列

嵌入式消息隊(duì)列的實(shí)現(xiàn)原理

嵌入式消息隊(duì)列通常采用循環(huán)緩沖區(qū)實(shí)現(xiàn)，即使用一個(gè)數(shù)組作為緩沖區(qū)，通過頭指針和尾指針來管理隊(duì)列。 消息隊(duì)列的基本操作包括入隊(duì)和出隊(duì)

入隊(duì)操作

入隊(duì)操作將一個(gè)消息寫入隊(duì)列中，實(shí)現(xiàn)方法如下：

1void queue_push(queue_t *queue, void *data, size_t size)
 2{
 3    uint32_t next = (queue->tail + 1) % queue->capacity;
 4
 5    if (next == queue->head) {
 6        // 隊(duì)列已滿，不再添加數(shù)據(jù)
 7        return;
 8    }
 9
10    queue_item_t *item = &queue->items[queue->tail];
11    item->size = size;
12    item->data = malloc(size);
13    memcpy(item->data, data, size);
14
15    queue->tail = next;
16}

在入隊(duì)操作中，我們首先檢查隊(duì)列是否已滿。 如果隊(duì)列已滿，就直接返回，不再添加數(shù)據(jù)。 如果隊(duì)列未滿，則使用尾指針指向的空間來存儲(chǔ)新的數(shù)據(jù)。 為了避免新的數(shù)據(jù)覆蓋舊的數(shù)據(jù)，我們需要?jiǎng)討B(tài)分配一個(gè)新的內(nèi)存空間，將數(shù)據(jù)復(fù)制到該空間中，并將其地址存儲(chǔ)到隊(duì)列的元素中。 最后，我們將尾指針往后移動(dòng)一個(gè)位置。

出隊(duì)操作

出隊(duì)操作將一個(gè)消息從隊(duì)列中讀取出來，并將其從隊(duì)列中刪除，實(shí)現(xiàn)方法如下

1void queue_pop(queue_t *queue, void *data, size_t *size)
 2{
 3    if (queue->head == queue->tail) {
 4        // 隊(duì)列為空，無法讀取數(shù)據(jù)
 5        return;
 6    }
 7
 8    queue_item_t *item = &queue->items[queue->head];
 9    *size = item->size;
10    memcpy(data, item->data, *size);
11
12    free(item->data);
13    queue->head = (queue->head + 1) % queue->capacity;
14}

在出隊(duì)操作中，我們首先檢查隊(duì)列是否為空。 如果隊(duì)列為空，就直接返回，無法讀取數(shù)據(jù)。 如果隊(duì)列非空，則使用頭指針指向的空間來讀取數(shù)據(jù)。 我們將元素中存儲(chǔ)的數(shù)據(jù)復(fù)制到指定的地址中，并返回?cái)?shù)據(jù)的大小。 最后，我們釋放元素中分配的內(nèi)存空間，并將頭指針往后移動(dòng)一個(gè)位置。

消息示例：

1#include 
  2#include 
  3#include 
  4
  5// 消息隊(duì)列結(jié)構(gòu)體
  6typedef struct {
  7    uint8_t *buf;    // 指向隊(duì)列緩存區(qū)的指針
  8    uint32_t head;   // 隊(duì)頭指針
  9    uint32_t tail;   // 隊(duì)尾指針
 10    uint32_t size;   // 隊(duì)列容量
 11    uint32_t count;  // 當(dāng)前隊(duì)列中的消息數(shù)量
 12} message_queue_t;
 13
 14// 創(chuàng)建一個(gè)消息隊(duì)列
 15message_queue_t *message_queue_create(uint32_t size) {
 16    message_queue_t *mq = (message_queue_t *)malloc(sizeof(message_queue_t));
 17    if (mq == NULL) {
 18        return NULL;
 19    }
 20
 21    mq->buf = (uint8_t *)malloc(size);
 22    if (mq->buf == NULL) {
 23        free(mq);
 24        return NULL;
 25    }
 26
 27    mq->head = 0;
 28    mq->tail = 0;
 29    mq->size = size;
 30    mq->count = 0;
 31
 32    return mq;
 33}
 34
 35// 銷毀一個(gè)消息隊(duì)列
 36void message_queue_destroy(message_queue_t *mq) {
 37    if (mq == NULL) {
 38        return;
 39    }
 40
 41    if (mq->buf != NULL) {
 42        free(mq->buf);
 43    }
 44
 45    free(mq);
 46}
 47
 48// 向消息隊(duì)列中發(fā)送一條消息
 49uint32_t message_queue_send(message_queue_t *mq, uint8_t *buf, uint32_t len) {
 50    if (mq == NULL || buf == NULL || len == 0) {
 51        return 0;
 52    }
 53
 54    // 如果隊(duì)列已滿，則無法發(fā)送消息
 55    if (mq->count >= mq->size) {
 56        return 0;
 57    }
 58
 59    // 將消息寫入隊(duì)列緩存區(qū)
 60    uint32_t i;
 61    for (i = 0; i < len; i++) {
 62        mq->buf[mq->tail] = buf[i];
 63        mq->tail = (mq->tail + 1) % mq->size;
 64    }
 65
 66    // 更新隊(duì)列狀態(tài)
 67    mq->count += len;
 68
 69    return len;
 70}
 71
 72// 從消息隊(duì)列中接收一條消息
 73uint32_t message_queue_recv(message_queue_t *mq, uint8_t *buf, uint32_t len) {
 74    if (mq == NULL || buf == NULL || len == 0) {
 75        return 0;
 76    }
 77
 78    // 如果隊(duì)列為空，則無法接收消息
 79    if (mq->count == 0) {
 80        return 0;
 81    }
 82
 83    // 讀取隊(duì)列緩存區(qū)中的消息
 84    uint32_t i;
 85    for (i = 0; i < len && i < mq->count; i++) {
 86        buf[i] = mq->buf[mq->head];
 87        mq->head = (mq->head + 1) % mq->size;
 88    }
 89
 90    // 更新隊(duì)列狀態(tài)
 91    mq->count -= i;
 92
 93    return i;
 94}
 95
 96// 獲取消息隊(duì)列中的消息數(shù)量
 97uint32_t message_queue_count(message_queue_t *mq) {
 98    if (mq == NULL) {
 99        return 0;
100    }
101
102    return mq->count;
103}

消息隊(duì)列示例說明

上面的示例是一個(gè)基于循環(huán)隊(duì)列實(shí)現(xiàn)的簡單嵌入式消息隊(duì)列的代碼實(shí)現(xiàn)，下面詳細(xì)說明其實(shí)現(xiàn)原理：

消息隊(duì)列結(jié)構(gòu)體

定義一個(gè)消息隊(duì)列結(jié)構(gòu)體，包含隊(duì)列緩存區(qū)指針、隊(duì)頭指針、隊(duì)尾指針、隊(duì)列容量和當(dāng)前隊(duì)列中的消息數(shù)量等信息

1typedef struct {
2    uint8_t *buf;    // 指向隊(duì)列緩存區(qū)的指針
3    uint32_t head;   // 隊(duì)頭指針
4    uint32_t tail;   // 隊(duì)尾指針
5    uint32_t size;   // 隊(duì)列容量
6    uint32_t count;  // 當(dāng)前隊(duì)列中的消息數(shù)量
7} message_queue_t;

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

使用 message_queue_create 函數(shù)創(chuàng)建一個(gè)消息隊(duì)列，該函數(shù)會(huì)動(dòng)態(tài)分配一塊內(nèi)存用于存儲(chǔ)消息隊(duì)列結(jié)構(gòu)體和隊(duì)列緩存區(qū)，初始化消息隊(duì)列的各個(gè)參數(shù)，并返回一個(gè)指向消息隊(duì)列結(jié)構(gòu)體的指針。

1message_queue_t *message_queue_create(uint32_t size) {
 2    message_queue_t *mq = (message_queue_t *)malloc(sizeof(message_queue_t));
 3    if (mq == NULL) {
 4        return NULL;
 5    }
 6
 7    mq->buf = (uint8_t *)malloc(size);
 8    if (mq->buf == NULL) {
 9        free(mq);
10        return NULL;
11    }
12
13    mq->head = 0;
14    mq->tail = 0;
15    mq->size = size;
16    mq->count = 0;
17
18    return mq;
19}

銷毀消息隊(duì)列

使用 message_queue_destroy 函數(shù)銷毀一個(gè)消息隊(duì)列，該函數(shù)會(huì)釋放消息隊(duì)列結(jié)構(gòu)體和隊(duì)列緩存區(qū)所占用的內(nèi)存。

1void message_queue_destroy(message_queue_t *mq) {
 2    if (mq == NULL) {
 3        return;
 4    }
 5
 6    if (mq->buf != NULL) {
 7        free(mq->buf);
 8    }
 9
10    free(mq);
11}

發(fā)送消息

使用 message_queue_send 函數(shù)向消息隊(duì)列中發(fā)送一條消息，該函數(shù)會(huì)將消息寫入隊(duì)列緩存區(qū)，并更新隊(duì)列的狀態(tài)，返回實(shí)際寫入隊(duì)列緩存區(qū)的消息長度。

1uint32_t message_queue_send(message_queue_t *mq, uint8_t *buf, uint32_t len) {
 2    if (mq == NULL || buf == NULL || len == 0) {
 3        return 0;
 4    }
 5
 6    // 如果隊(duì)列已滿，則無法發(fā)送消息
 7    if (mq->count >= mq->size) {
 8        return 0;
 9    }
10
11    // 將消息寫入隊(duì)列緩存區(qū)
12    uint32_t i;
13    for (i = 0; i < len; i++) {
14        mq->buf[mq->tail] = buf[i];
15        mq->tail = (mq->tail + 1) % mq->size;
16    }
17
18    // 更新隊(duì)列狀態(tài)
19    mq->count += len;
20
21    return len;
22}