??想了解更多內容，請訪問：??

??51CTO和華為官方合作共建的鴻蒙技術社區??

??https://ost.51cto.com??

前言

Linux的創始人Linus Torvalds在2000-08-25給linux-kernel郵件列表的一封郵件提到: Talk is cheap. Show me the code.但是，今天小編不僅僅要code，也要talk一把OpenHarmony的內核對象隊列，雖然它不是屬于特別出彩的對象，不是全宇宙流行的人工智能，也不是炫酷無比的自動化駕駛，和小編一樣普普通通，默默支撐著OpenHarmony的內部運轉，輔助著內核對象Task這個老大哥的正常運轉。

關鍵數據結構

首先，我們不得不提到隊列的關鍵數據結構LosQueueCB，它是如此的枯燥無味，但是小編不得不硬著頭皮解釋，如果沒有這個靈魂數據，那么也就無法理解隊列是如何工作：

typedef struct {
    UINT8 *queue;      /**< Pointer to a queue handle */
    UINT16 queueState; /**< Queue state */
    UINT16 queueLen;   /**< Queue length */
    UINT16 queueSize;  /**< Node size */
    UINT16 queueID;    /**< queueID */
    UINT16 queueHead;  /**< Node head */
    UINT16 queueTail;  /**< Node tail */
    UINT16 readWriteableCnt[OS_READWRITE_LEN]; /**< Count of readable or writable resources, 0:readable, 1:writable */
    LOS_DL_LIST readWriteList[OS_READWRITE_LEN]; /**< Pointer to the linked list to be read or written,                                                      0:readlist, 1:writelist */
    LOS_DL_LIST memList; /**< Pointer to the memory linked list */
}LosQueueCB;

• *queue：指向消息節點內存區域，創建隊列時按照消息節點個數乘每個節點大小從動態內存池中申請一片空間。
• queueState：隊列狀態，表明隊列控制塊是否被使用，有OS_QUEUE_INUSED和OS_QUEUE_UNUSED兩種狀態，至于中文含義，各位讀者一眼就明白。
• queueLen：消息節點個數，表示該消息隊列最大可存儲多少個消息，小編認為可以換個名字queueMsgNum也許更合適。
• queueSize：每個消息節點大小，表示隊列每個消息可存儲信息的大小，同樣queueMsgSize會形象一點。
• queueID：消息ID，通過它來操作隊列。
• 消息節點按照循環隊列的方式訪問，隊列中的每個節點以數組下標表示，下面的成員與消息節點循環隊列有關：
• queueHead：循環隊列的頭部。
• queueTail：循環隊列的尾部。
• readWriteableCnt[OS_QUEUE_WRITE]：消息節點循環隊列中可寫的消息個數，為0表示循環隊列為滿，等于queueLen表示循環隊列為空。
• readWriteableCnt[OS_QUEUE_READ]：消息節點循環隊列中可讀的消息個數，為0表示循環隊列為空，等于queueLen表示消息隊列為滿。
• readWriteList[OS_QUEUE_WRITE]：寫消息阻塞鏈表，鏈接因消息隊列滿而無法寫入時需要掛起的TASK。
• readWriteList[OS_QUEUE_READ]：讀消息阻塞鏈表，鏈接因消息隊列空而無法讀取時需要掛起的TASK。
• memList：申請內存塊阻塞鏈表，鏈接因申請某一靜態內存池中的內存塊失敗而需要掛起的TASK。

注意：在老的版本中readWriteableCnt和readWriteList是拆分為4個變量，新版本是用宏定義合并，OS_QUEUE_READ標識是讀操作，OS_QUEUE_WRITE標識為寫操作。各位讀者應該看到代碼微妙之處，0的含義和queueLen對于讀寫是統一的，內核開發者不斷使用抽象這個手段來優化內核，而我們只需要靜靜坐在電腦旁，捧起一杯熱氣騰騰的茶水，欣賞著美好的代碼。

關鍵算法

隊列的算法不得不提FIFO，另外它還有一個兄弟FILO，今天良心小編仔仔細細給大伙來嘮叨一下這個FIFO算法。

先來個百度定義：FIFO(First Input First Output)，即先進先出隊列。在超市購物之后我們會到收銀臺排隊結賬，眼睜睜地看著前面的客戶一個個離開。這就是一種先進先出機制，先排隊的客戶先行結賬離開。

那么OpenHarmony的隊列是如何實現這個算法?

一、 FIFO算法之入隊列

第一步：當然是隊列初始化

下圖表明了一個初始化后的隊列長啥樣子。

小編不僅僅會畫圖，還會解說代碼，沒有代碼支撐的圖就是“耍流氓”，由于LOS_QueueCreate函數太長，只能截取關鍵函數LOS_QueueCreate.

LITE_OS_SEC_TEXT_INIT UINT32 LOS_QueueCreate(CHAR *queueName,
                                         UINT16 len,
                                         UINT32 *queueID,
                                         UINT32 flags,
                                         UINT16 maxMsgSize)
{
    LosQueueCB *queueCB = NULL;
    UINT32 intSave;
    LOS_DL_LIST *unusedQueue = NULL;
    UINT8 *queue = NULL;
    UINT16 msgSize;
    ...
    queue = (UINT8 *)LOS_MemAlloc(m_aucSysMem0, len * msgSize);
    ...
    queueCB->queueLen = len;
    queueCB->queueSize = msgSize;
    queueCB->queue = queue;
    queueCB->queueState = OS_QUEUE_INUSED;
    queueCB->readWriteableCnt[OS_QUEUE_READ] = 0;
    queueCB->readWriteableCnt[OS_QUEUE_WRITE] = len;
    queueCB->queueHead = 0;
    queueCB->queueTail = 0;
    LOS_ListInit(&queueCB->readWriteList[OS_QUEUE_READ]);
    LOS_ListInit(&queueCB->readWriteList[OS_QUEUE_WRITE]);
    LOS_ListInit(&queueCB->memList);
    LOS_IntRestore(intSave);

    *queueID = queueCB->queueID;

    OsHookCall(LOS_HOOK_TYPE_QUEUE_CREATE, queueCB);

    return LOS_OK;
}

上文所講，數據結構是支撐算法的靈魂，內核對象的隊列控制結構LosQueueCB通過queue指針來指向具體隊列的內容，隊列分配了queueLen個消息，每個消息的大小為queueSize。與此同時頭指針和尾指針不約而同初始化為0。

第二步：第一個消息入隊列

生產者通過隊列來傳遞信息，這個生產者可以是形形色色的各個任務，產生一個隊列后，任務就迫不及待的需要放置消息，究竟是選擇FIFO or FILO?任務這個老大哥面臨著嚴峻的選擇，這一次我們選擇了FIFO。

下圖是FIFO插入第一個數據后的內存形態。

OpenHarmony作為一個開源系統，在下面的代碼中很好的體現了這個操作：

static INLINE VOID OsQueueBufferOperate(LosQueueCB *queueCB, UINT32 operateType,
                                                            VOID *bufferAddr, UINT32 *bufferSize)
{
    UINT8 *queueNode = NULL;
    UINT32 msgDataSize;
    UINT16 queuePosition;
    errno_t rc;

    /* get the queue position */
    switch (OS_QUEUE_OPERATE_GET(operateType)) {
        case OS_QUEUE_READ_HEAD:
            queuePosition = queueCB->queueHead;
            ((queueCB->queueHead + 1) == queueCB->queueLen) ? (queueCB->queueHead = 0) : (queueCB->queueHead++);
            break;

        case OS_QUEUE_WRITE_HEAD:
            (queueCB->queueHead == 0) ? (queueCB->queueHead = (queueCB->queueLen - 1)) : (--queueCB->queueHead);
            queuePosition = queueCB->queueHead;
            break;

        case OS_QUEUE_WRITE_TAIL:
            queuePosition = queueCB->queueTail;
            ((queueCB->queueTail + 1) == queueCB->queueLen) ? (queueCB->queueTail = 0) : (queueCB->queueTail++);
            break;
    ...
}

OsQueueBufferOperate是隊列內存的核心操作函數，FIFO算法本質是往隊列的尾處添加數據，代碼抽象為OS_QUEUE_WRITE_TAIL操作，請注意隊列是個循環隊列，插入數據后移動tail這個“尾巴”指針要特別小心，在最后一個物理空間用完成后需要移到隊列頭部，這就是傳說中環形隊列的循環大法。

讀者要產生一個疑問：如何判斷最后一個物理空間已經用完?(queueCB->queueTail + 1) == queueCB->queueLen)這個C語言語句很好的解釋了這個疑問，在這里小編不得不贊美C語言，有了C語言，就有小編喜歡的linux內核，更有了我們的OpenHarmony。queueLen是隊列物理空間的邊界值，如果下一個消息已經指到這個邊界值，那么內核必須讓它乖乖回到原位，即queueCB->queueTail = 0，不然可要出大問題-內存越界，這個時候機毀物亡那也是有可能的。因為我們的OpenHarmony應用在各個領域，如果是自動化駕駛領域那么后果是非常嚴重的，當然聰明的程序員是不會讓這種情況發生的。

第三步：繼續生產數據

好吧，上面操作重復再重復，但是OpenHarmony忠實的執行了這種行為：代碼小編就不一一細說了，此處是否可以來一些music? 哦no，是picture。

第四步：生產數據結束

生產者生產了四個消息后感覺已經enough了，于是偷懶不再干活了。

二、 FIFO算法之出隊列

第一步：當然是隊列第一個消息，因為我們是FIFO，先來的消息先拉出槍斃!

如上圖所示我們回顧下入隊列的步驟，知道了每個消息的入隊順序，于是第一個消息被消費后:

在生產消息過程中我們已經提到OsQueueBufferOperate這個函數，我們回顧關鍵代碼：

/* get the queue position */
switch (OS_QUEUE_OPERATE_GET(operateType)) {
    case OS_QUEUE_READ_HEAD:
        queuePosition = queueCB->queueHead;
        ((queueCB->queueHead + 1) == queueCB->queueLen) ? (queueCB->queueHead = 0) : (queueCB->queueHead++);
        break;

queueHead就是我們的頭指針，它的移動也面臨著生產過程相同的問題，在最后一個物理空間用完成后需要移到隊列的頭部。方法是如此的相似，以至于小編都懶得解釋。OS_QUEUE_READ_HEAD是出隊列的關鍵處理，解決了queueHead頭指針如何移動的問題。

第二步：繼續消費

直接上圖

第三步：消費完畢

最后一個消息也被我們干掉了，于是head指針和tail指針均移動到下圖的位置。此時隊列為空，活干完了，消費者也散了。

總結

本文主要介紹了OpenHarmony內核對象隊列的算法之FIFO。

??想了解更多內容，請訪問：??

??51CTO和華為官方合作共建的鴻蒙技術社區??

??https://ost.51cto.com??