隊列基本概念

隊列是一種常用於任務間通信的數據結構，隊列可以在任務與任務間、中斷和任務間傳遞消息，實現了任務接收來自其他任務或中斷的不固定長度的消息，任務能夠從隊列裡面讀取消息，當隊列中的消息是空時，讀取消息的任務將被阻塞，用戶還可以指定任務等待消息的時間timeout，在這段時間中，如果隊列為空，該任務將保持阻塞狀態以等待隊列數據有效。當隊列中有新消息時，被阻塞的任務會被喚醒並處理新消息；當等待的時間超過了指定的阻塞時間，即使隊列中尚無有效數據，任務也會自動從阻塞態轉為就緒態，消息隊列是一種非同步的通信方式。

通過隊列服務，任務或中斷服務常式可以將一條或多條消息放入隊列中。同樣，一個或多個任務可以從隊列中獲得消息。當有多個消息發送到隊列時，通常是將先進入隊列的消息先傳給任務，也就是說，任務先得到的是最先進入隊列的消息，即先進先出原則（FIFO），其實TencentOS tiny暫時不支持後進先出原則LIFO操作隊列，但是支持後進先出操作消息隊列。

提示：TencentOS tiny 的隊列不等同於消息隊列，雖然隊列的底層實現是依賴消息隊列，但在TencentOS tiny中將它們分離開，這是兩個概念，畢竟操作是不一樣的。

隊列的阻塞機制

舉個簡單的例子來理解操作系統中的阻塞機制：

假設你某天去餐廳吃飯，但是餐廳沒菜了，那麼你可能會有3個選擇，你扭頭就走，既然都沒菜了，肯定換一家餐廳啊是吧。或者你會選擇等一下，說不定老闆去買菜了，一會就有菜了呢，就能吃飯。又或者，你覺得這家餐廳非常好吃，吃不到飯你就不走了，在這死等~

同樣的：假設有一個任務A對某個隊列進行讀操作的時候（出隊），發現它此時是沒有消息的，那麼此時任務A有3個選擇：第一個選擇，任務A扭頭就走，既然隊列沒有消息，那我也不等了，乾其它事情去，這樣子任務A不會進入阻塞態；第二個選擇，任務A還是在這裡等等吧，可能過一會隊列就有消息，此時任務A會進入阻塞狀態，在等待著消息的到來，而任務A的等待時間就由我們自己指定，當阻塞的這段時間中任務A等到了隊列的消息，那麼任務A就會從阻塞態變成就緒態；假如等待超時了，隊列還沒消息，那任務A就不等了，從阻塞態中喚醒；第三個選擇，任務A死等，不等到消息就不走了，這樣子任務A就會進入阻塞態，直到完成讀取隊列的消息。

隊列實現的數據結構

隊列控制塊

TencentOS tiny 通過隊列控制塊操作隊列，其數據類型為k_queue_t，隊列控制塊由多個元素組成，主要有 pend_obj_t 類型的pend_obj以及k_msg_queue_t類型的msg_queue消息列表。其實整個隊列的實現非常簡單，主要靠msg_queue中的queue_head成員變數（這其實是一個消息列表（消息鏈表）），所有的消息都會被記錄在這個消息列表中，當讀取消息的時候，會從消息列表讀取消息。

繼承自內核對象的數據結構 在 \kernel\core\include\tos_pend.h 的 35 行

typedef struct pend_object_st {
    pend_type_t     type;
    k_list_t        list;
} pend_obj_t;

消息列表的數據類型（消息隊列控制塊），在 \kernel\core\include\tos_msg.h 文件的第 13 行

typedef struct k_msg_queue_st {
#if TOS_CFG_OBJECT_VERIFY_EN > 0u
    knl_obj_t       knl_obj;
#endif

    k_list_t        queue_head;
} k_msg_queue_t;

隊列控制塊，在 \kernel\core\include\tos_queue.h 文件的第 6 行

typedef struct k_queue_st {
    pend_obj_t      pend_obj;
    k_msg_queue_t msg_queue;
} k_queue_t;

隊列控制塊示意圖如下：

消息控制塊

除了上述的隊列控制塊外，還有消息隊列控制塊，這是因為TencentOS tiny中實現隊列是依賴消息隊列的，既然隊列可以傳遞數據（消息），則必須存在一種可以存儲消息的數據結構，我稱之為消息控制塊，消息控制塊中記錄了消息的存儲地址msg_addr，以及消息的大小msg_size，此外還存在一個list成員變數，可以將消息掛載到隊列的消息列表中。

消息控制塊數據結構， 在 \kernel\core\include\tos_msg.h 文件的第 7 行

typedef struct k_message_st {
    k_list_t        list;
    void           *msg_addr;
    size_t          msg_size;
} k_msg_t;

其實隊列的實現依賴於消息隊列，他們的關係如下：

任務控制塊中的消息成員變數

假設任務A在隊列中等待消息，而中斷或其他任務往任務A等待的隊列寫入（發送）一個消息，那麼這個消息不會被掛載到隊列的消息列表中，而是會直接被記錄在任務A的任務控制塊中，表示任務A從隊列中等待到這個消息，因此任務控制塊必須存在一些成員變數用於記錄消息相關信息（如消息地址、消息大小等）：

任務控制塊數據結構 在\kernel\core\include\tos_task.h文件的第 90 行

typedef struct k_task_st {
···
#if TOS_CFG_MSG_EN > 0u
    void               *msg_addr;           /**< 保存接收到的消息地址 */
    size_t              msg_size;           /**< 保存接收到的消息大小 */
#endif
···
} k_task_t;

與消息相關的巨集定義

在tos_config.h文件中，使能隊列組件的巨集定義TOS_CFG_QUEUE_EN，使能消息隊列組件巨集定義TOS_CFG_MSG_EN，系統支持的消息池中消息個數巨集定義TOS_CFG_MSG_POOL_SIZE。

#define TOS_CFG_QUEUE_EN                1u

#define TOS_CFG_MSG_EN                  1u

#define TOS_CFG_MSG_POOL_SIZE           3u

消息池

在TencentOS tiny中定義了一個數組k_msg_pool[TOS_CFG_MSG_POOL_SIZE]作為消息池，它的數據類型是消息控制塊類型k_msg_t，因為在使用消息隊列的時候存取消息比較頻繁，而在系統初始化的時候就將這個大數組的各個元素串初始化，並掛載到空閑消息列表中k_msg_freelist，組成我們說的消息池k_msg_pool，而池中的成員變數就是我們所說的消息。

為什麼使用池化的方式處理消息呢，因為高效，復用率高，就像我們在池塘中去一勺水，在使用完畢再將其歸還到池塘，這種操作是非常高效的，並且在有限資源的嵌入式中能將資源重覆有效地利用起來。

消息池相關的定義 在\kernel\core\tos_global.c文件 第 51 行

#if TOS_CFG_MSG_EN > 0u
TOS_LIST_DEFINE(k_msg_freelist);

k_msg_t             k_msg_pool[TOS_CFG_MSG_POOL_SIZE];

#endif

隊列創建

tos_queue_create()函數用於創建一個隊列，隊列就是一個數據結構，用於任務間的數據的傳遞。每創建一個新的隊列都需要為其分配RAM，在創建的時候我們需要自己定義一個隊列控制塊，其記憶體是由編譯器自動分配的。在創建的過程中實際上就是將隊列控制塊的內容進行初始化，將隊列控制塊的 pend_obj成員變數中的type 屬性標識為PEND_TYPE_QUEUE，表示這是一個隊列，然後調用消息隊列中的API函數tos_msg_queue_create()將隊列的消息成員變數msg_queue初始化，實際上就是初始化消息列表。

創建隊列函數，在\kernel\core\tos_queue.c 第 5 行

__API__ k_err_t tos_queue_create(k_queue_t *queue)
{
    TOS_PTR_SANITY_CHECK(queue);

    pend_object_init(&queue->pend_obj, PEND_TYPE_QUEUE);
    tos_msg_queue_create(&queue->msg_queue);
    return K_ERR_NONE;
}

銷毀隊列

tos_queue_destroy()函數用於銷毀一個隊列，當隊列不在使用是可以將其銷毀，銷毀的本質其實是將隊列控制塊的內容進行清除，首先判斷一下隊列控制塊的類型是PEND_TYPE_QUEUE，這個函數只能銷毀隊列類型的控制塊。然後判斷是否有任務在等待隊列中的消息，如果有則調用pend_wakeup_all()函數將這項任務喚醒，然後調用tos_msg_queue_flush()函數將隊列的消息列表的消息全部“清空”，“清空”的意思是將掛載到隊列上的消息釋放回消息池（如果隊列的消息列表存在消息，使用msgpool_free()函數釋放消息），knl_object_deinit()函數是為了確保隊列已經被銷毀，此時隊列控制塊的pend_obj成員變數中的type 屬性標識為KNL_OBJ_TYPE_NONE。最後在銷毀隊列後進行一次任務調度，以切換任務（畢竟剛剛很可能喚醒了任務）。

但是有一點要註意，因為隊列控制塊的RAM是由編譯器靜態分配的，所以即使是銷毀了隊列，這個記憶體也是沒辦法釋放的~

銷毀隊列函數，在\kernel\core\tos_queue.c 第 14 行

__API__ k_err_t tos_queue_destroy(k_queue_t *queue)
{
    TOS_CPU_CPSR_ALLOC();

    TOS_PTR_SANITY_CHECK(queue);

#if TOS_CFG_OBJECT_VERIFY_EN > 0u
    if (!pend_object_verify(&queue->pend_obj, PEND_TYPE_QUEUE)) {
        return K_ERR_OBJ_INVALID;
    }
#endif

    TOS_CPU_INT_DISABLE();

    if (!pend_is_nopending(&queue->pend_obj)) {
        pend_wakeup_all(&queue->pend_obj, PEND_STATE_DESTROY);
    }

    pend_object_deinit(&queue->pend_obj);
    tos_msg_queue_flush(&queue->msg_queue);

    TOS_CPU_INT_ENABLE();
    knl_sched();

    return K_ERR_NONE;
}

清空隊列

清空隊列實際上就是將消息釋放回消息池中，本質上還是調用tos_msg_queue_flush()函數。它是依賴於消息隊列實現的。

清空隊列函數，在\kernel\core\tos_queue.c 第 41 行

__API__ k_err_t tos_queue_flush(k_queue_t *queue)
{
    TOS_CPU_CPSR_ALLOC();

    TOS_PTR_SANITY_CHECK(queue);

#if TOS_CFG_OBJECT_VERIFY_EN > 0u
    if (!pend_object_verify(&queue->pend_obj, PEND_TYPE_QUEUE)) {
        return K_ERR_OBJ_INVALID;
    }
#endif

    TOS_CPU_INT_DISABLE();
    tos_msg_queue_flush(&queue->msg_queue);
    TOS_CPU_INT_ENABLE();

    return K_ERR_NONE;
}

等待隊列（消息）

當任務試圖從隊列中的獲取消息時，用戶可以指定一個等待時間，當且僅當隊列存在消息的時候，任務才能獲取到消息。在等待的這段時間中，如果隊列為空，該任務將保持阻塞狀態以等待隊列消息有效。當其他任務或中斷服務程式往其等待的隊列中寫入了數據，該任務將自動由阻塞態轉為就緒態。當任務等待發生超時，即使隊列中尚無有效消息，任務也會自動從阻塞態轉為就緒態。
等待隊列的過程也是非常簡單的，先來看看參數吧（其中msg_addr與msg_size參數是用於保存函數返回的內容，即輸出）：
| 參數 | 說明 |
|--|--|
| queue | 隊列控制塊指針 |
| msg_addr| 用於保存獲取到的消息（這是輸出的） |
| msg_size| 用於保存獲取到消息的大小（這是輸出的） |
| timeout| 等待時間（以k_tick_t為單位） |

等待隊列消息的過程如下：

1. 首先檢測傳入的參數是否正確

2. 嘗試調用tos_msg_queue_get()函數獲取消息，如果隊列存在消息則會獲取成功（返回K_ERR_NONE），否則獲取失敗。（關於該函數在下一章講解）

3. 當獲取成功則可以直接退出函數，而當獲取消息失敗的時候，則可以根據指定的等待時間timeout進行阻塞，如果不等待（timeout =TOS_TIME_NOWAIT），則直接返回錯誤代碼K_ERR_PEND_NOWAIT。

4. 如果調度器被鎖了knl_is_sched_locked()，則無法進行等待操作，返回錯誤代碼K_ERR_PEND_SCHED_LOCKED，畢竟需要切換任務，調度器被鎖則無法切換任務。

5. 調用pend_task_block()函數將任務阻塞，該函數實際上就是將任務從就緒列表中移除k_rdyq.task_list_head[task_prio]，並且插入到等待列表中object->list，如果等待的時間不是永久等待TOS_TIME_FOREVER，還會將任務插入時間列表中k_tick_list，阻塞時間為timeout，然後進行一次任務調度knl_sched()。

6. 當程式能執行到pend_state2errno()時，則表示任務等待到消息，又或者發生超時，那麼就調用pend_state2errno()函數獲取一下任務的等待狀態，看一下是哪種情況導致任務恢復運行。

7. 如果是正常情況（等待獲取到消息），則將消息從任務控制塊的k_curr_task->msg_addr讀取出來，並且寫入msg_addr 中用於返回。同樣的消息的大小也是會通過msg_size返回。

獲取（等待）隊列消息函數，在\kernel\core\tos_queue.c 第 60 行

__API__ k_err_t tos_queue_pend(k_queue_t *queue, void **msg_addr, size_t *msg_size, k_tick_t timeout)
{
    TOS_CPU_CPSR_ALLOC();
    k_err_t err;

    TOS_PTR_SANITY_CHECK(queue);
    TOS_PTR_SANITY_CHECK(msg_addr);
    TOS_PTR_SANITY_CHECK(msg_size);

#if TOS_CFG_OBJECT_VERIFY_EN > 0u
    if (!pend_object_verify(&queue->pend_obj, PEND_TYPE_QUEUE)) {
        return K_ERR_OBJ_INVALID;
    }
#endif

    TOS_CPU_INT_DISABLE();

    if (tos_msg_queue_get(&queue->msg_queue, msg_addr, msg_size) == K_ERR_NONE) {
        TOS_CPU_INT_ENABLE();
        return K_ERR_NONE;
    }

    if (timeout == TOS_TIME_NOWAIT) {
        *msg_addr = K_NULL;
        *msg_size = 0;
        TOS_CPU_INT_ENABLE();
        return K_ERR_PEND_NOWAIT;
    }

    if (knl_is_sched_locked()) {
        TOS_CPU_INT_ENABLE();
        return K_ERR_PEND_SCHED_LOCKED;
    }

    pend_task_block(k_curr_task, &queue->pend_obj, timeout);

    TOS_CPU_INT_ENABLE();
    knl_sched();

    err = pend_state2errno(k_curr_task->pend_state);

    if (err == K_ERR_NONE) {
        *msg_addr = k_curr_task->msg_addr;
        *msg_size = k_curr_task->msg_size;
        k_curr_task->msg_addr = K_NULL;
        k_curr_task->msg_size = 0;
    }

    return err;
}

將等待消息的任務添加到對應等待列表函數，在\kernel\core\tos_pend.c文件的 第 106 行

__KERNEL__ void pend_task_block(k_task_t *task, pend_obj_t *object, k_tick_t timeout)
{
    readyqueue_remove(task);
    pend_list_add(task, object);

    if (timeout != TOS_TIME_FOREVER) {
        tick_list_add(task, timeout);
    }
}

獲取任務等待狀態的函數，在\kernel\core\tos_pend.c文件的 第 72 行

__KERNEL__ k_err_t pend_state2errno(pend_state_t state)
{
    if (state == PEND_STATE_POST) {
        return K_ERR_NONE;
    } else if (state == PEND_STATE_TIMEOUT) {
        return K_ERR_PEND_TIMEOUT;
    } else if (state == PEND_STATE_DESTROY) {
        return K_ERR_PEND_DESTROY;
    } else if (state == PEND_STATE_OWNER_DIE) {
        return K_ERR_PEND_OWNER_DIE;
    } else {
        return K_ERR_PEND_ABNORMAL;
    }
}

（消息）寫入隊列

任務或者中斷服務程式都可以給消息隊列發送消息，當發送消息時，TencentOS tiny會從消息池中取出一個消息，掛載到隊列的消息列表末尾（FIFO發送方式）。tos_queue_post()是喚醒一個等待隊列消息任務，tos_queue_post_all()則會喚醒所有等待隊列消息的任務，無論何種情況，都是調用queue_do_post將消息寫入隊列中。
消息的寫入隊列過程：

1. 首先檢測傳入的參數是否正確

2. 判斷一下是否有任務在等待消息，如果有則根據opt參數決定喚醒一個任務或者所有等待任務，否則直接將消息寫入隊列中。

3. 當沒有任務在等待消息時，調用tos_msg_queue_put()函數將消息寫入隊列，寫入隊列的方式遵循FIFO原則（TOS_OPT_MSG_PUT_FIFO），寫入成功返回K_ERR_NONE。而如果消息池已經沒有消息了（消息最大個數由TOS_CFG_MSG_POOL_SIZE巨集定義決定），則寫入失敗，返回K_ERR_QUEUE_FULL錯誤代碼。（關於該函數將在下一章講解）

4. 如果有任務在等待消息，則調用queue_task_msg_recv()函數將消息內容與大小寫入任務控制塊的msg_addr與msg_size成員變數中，此外還需要喚醒任務，就通過調用pend_task_wakeup()函數將對應的等待任務喚醒，核心處理思想就是通過TOS_LIST_FIRST_ENTRY獲取到等待在隊列上的任務，然後喚醒它。

5. 對於喚醒所有等待任務的處理其實也是一樣的，只不過是多了個迴圈處理，把等待列表中的所有任務依次喚醒，僅此而已~

寫入隊列消息函數，在\kernel\core\tos_queue.c 第 159 、164 行

__API__ k_err_t tos_queue_post(k_queue_t *queue, void *msg_addr, size_t msg_size)
{
    TOS_PTR_SANITY_CHECK(queue);
    TOS_PTR_SANITY_CHECK(msg_addr);

    return queue_do_post(queue, msg_addr, msg_size, OPT_POST_ONE);
}

__API__ k_err_t tos_queue_post_all(k_queue_t *queue, void *msg_addr, size_t msg_size)
{
    TOS_PTR_SANITY_CHECK(queue);
    TOS_PTR_SANITY_CHECK(msg_addr);

    return queue_do_post(queue, msg_addr, msg_size, OPT_POST_ALL);
}

寫入隊列消息函數實際調用的函數，通過opt參數進行不一樣的處理，在\kernel\core\tos_queue.c 第 118 行

__STATIC__ k_err_t queue_do_post(k_queue_t *queue, void *msg_addr, size_t msg_size, opt_post_t opt)
{
    TOS_CPU_CPSR_ALLOC();
    k_list_t *curr, *next;

    TOS_PTR_SANITY_CHECK(queue);

#if TOS_CFG_OBJECT_VERIFY_EN > 0u
    if (!pend_object_verify(&queue->pend_obj, PEND_TYPE_QUEUE)) {
        return K_ERR_OBJ_INVALID;
    }
#endif

    TOS_CPU_INT_DISABLE();

    if (pend_is_nopending(&queue->pend_obj)) {
        if (tos_msg_queue_put(&queue->msg_queue, msg_addr, msg_size, TOS_OPT_MSG_PUT_FIFO) != K_ERR_NONE) {
            TOS_CPU_INT_ENABLE();
            return K_ERR_QUEUE_FULL;
        }
        TOS_CPU_INT_ENABLE();
        return K_ERR_NONE;
    }

    if (opt == OPT_POST_ONE) {
        queue_task_msg_recv(TOS_LIST_FIRST_ENTRY(&queue->pend_obj.list, k_task_t, pend_list),
                                msg_addr, msg_size);
    } else { // OPT_QUEUE_POST_ALL
        TOS_LIST_FOR_EACH_SAFE(curr, next, &queue->pend_obj.list) {
            queue_task_msg_recv(TOS_LIST_ENTRY(curr, k_task_t, pend_list),
                                msg_addr, msg_size);
        }
    }

    TOS_CPU_INT_ENABLE();
    knl_sched();

    return K_ERR_NONE;
}

喚醒等待的任務函數，在\kernel\core\tos_pend.c文件 的第 87 行

喚醒等待任務的思想就是將任務從對應的等待列表移除，然後添加到就緒列表中。

__KERNEL__ void pend_task_wakeup(k_task_t *task, pend_state_t state)
{
    if (task_state_is_pending(task)) {
        // mark why we wakeup
        task->pend_state = state;
        pend_list_remove(task);
    }

    if (task_state_is_sleeping(task)) {
        tick_list_remove(task);
    }

    if (task_state_is_suspended(task)) {
        return;
    }

    readyqueue_add(task);
}

總結

代碼精悍短小，思想清晰，非常建議深入學習~

喜歡就關註我吧！

更多資料歡迎關註“物聯網IoT開發”公眾號！