??想了解更多內(nèi)容，請(qǐng)?jiān)L問(wèn)：??

??51CTO和華為官方合作共建的鴻蒙技術(shù)社區(qū)??

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

前言

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

關(guān)鍵數(shù)據(jù)結(jié)構(gòu)

首先，我們不得不提到隊(duì)列的關(guān)鍵數(shù)據(jù)結(jié)構(gòu)LosQueueCB，它是如此的枯燥無(wú)味，但是小編不得不硬著頭皮解釋，如果沒(méi)有這個(gè)靈魂數(shù)據(jù)，那么也就無(wú)法理解隊(duì)列是如何工作：

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：指向消息節(jié)點(diǎn)內(nèi)存區(qū)域，創(chuàng)建隊(duì)列時(shí)按照消息節(jié)點(diǎn)個(gè)數(shù)乘每個(gè)節(jié)點(diǎn)大小從動(dòng)態(tài)內(nèi)存池中申請(qǐng)一片空間。
• queueState：隊(duì)列狀態(tài)，表明隊(duì)列控制塊是否被使用，有OS_QUEUE_INUSED和OS_QUEUE_UNUSED兩種狀態(tài)，至于中文含義，各位讀者一眼就明白。
• queueLen：消息節(jié)點(diǎn)個(gè)數(shù)，表示該消息隊(duì)列最大可存儲(chǔ)多少個(gè)消息，小編認(rèn)為可以換個(gè)名字queueMsgNum也許更合適。
• queueSize：每個(gè)消息節(jié)點(diǎn)大小，表示隊(duì)列每個(gè)消息可存儲(chǔ)信息的大小，同樣queueMsgSize會(huì)形象一點(diǎn)。
• queueID：消息ID，通過(guò)它來(lái)操作隊(duì)列。
• 消息節(jié)點(diǎn)按照循環(huán)隊(duì)列的方式訪問(wèn)，隊(duì)列中的每個(gè)節(jié)點(diǎn)以數(shù)組下標(biāo)表示，下面的成員與消息節(jié)點(diǎn)循環(huán)隊(duì)列有關(guān)：
• queueHead：循環(huán)隊(duì)列的頭部。
• queueTail：循環(huán)隊(duì)列的尾部。
• readWriteableCnt[OS_QUEUE_WRITE]：消息節(jié)點(diǎn)循環(huán)隊(duì)列中可寫(xiě)的消息個(gè)數(shù)，為0表示循環(huán)隊(duì)列為滿，等于queueLen表示循環(huán)隊(duì)列為空。
• readWriteableCnt[OS_QUEUE_READ]：消息節(jié)點(diǎn)循環(huán)隊(duì)列中可讀的消息個(gè)數(shù)，為0表示循環(huán)隊(duì)列為空，等于queueLen表示消息隊(duì)列為滿。
• readWriteList[OS_QUEUE_WRITE]：寫(xiě)消息阻塞鏈表，鏈接因消息隊(duì)列滿而無(wú)法寫(xiě)入時(shí)需要掛起的TASK。
• readWriteList[OS_QUEUE_READ]：讀消息阻塞鏈表，鏈接因消息隊(duì)列空而無(wú)法讀取時(shí)需要掛起的TASK。
• memList：申請(qǐng)內(nèi)存塊阻塞鏈表，鏈接因申請(qǐng)某一靜態(tài)內(nèi)存池中的內(nèi)存塊失敗而需要掛起的TASK。

注意：在老的版本中readWriteableCnt和readWriteList是拆分為4個(gè)變量，新版本是用宏定義合并，OS_QUEUE_READ標(biāo)識(shí)是讀操作，OS_QUEUE_WRITE標(biāo)識(shí)為寫(xiě)操作。各位讀者應(yīng)該看到代碼微妙之處，0的含義和queueLen對(duì)于讀寫(xiě)是統(tǒng)一的，內(nèi)核開(kāi)發(fā)者不斷使用抽象這個(gè)手段來(lái)優(yōu)化內(nèi)核，而我們只需要靜靜坐在電腦旁，捧起一杯熱氣騰騰的茶水，欣賞著美好的代碼。

關(guān)鍵算法

隊(duì)列的算法不得不提FIFO，另外它還有一個(gè)兄弟FILO，今天良心小編仔仔細(xì)細(xì)給大伙來(lái)嘮叨一下這個(gè)FIFO算法。

先來(lái)個(gè)百度定義：FIFO(First Input First Output)，即先進(jìn)先出隊(duì)列。在超市購(gòu)物之后我們會(huì)到收銀臺(tái)排隊(duì)結(jié)賬，眼睜睜地看著前面的客戶一個(gè)個(gè)離開(kāi)。這就是一種先進(jìn)先出機(jī)制，先排隊(duì)的客戶先行結(jié)賬離開(kāi)。

那么OpenHarmony的隊(duì)列是如何實(shí)現(xiàn)這個(gè)算法?

一、 FIFO算法之入隊(duì)列

第一步：當(dāng)然是隊(duì)列初始化

下圖表明了一個(gè)初始化后的隊(duì)列長(zhǎng)啥樣子。

小編不僅僅會(huì)畫(huà)圖，還會(huì)解說(shuō)代碼，沒(méi)有代碼支撐的圖就是“耍流氓”，由于LOS_QueueCreate函數(shù)太長(zhǎng)，只能截取關(guān)鍵函數(shù)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;
}

上文所講，數(shù)據(jù)結(jié)構(gòu)是支撐算法的靈魂，內(nèi)核對(duì)象的隊(duì)列控制結(jié)構(gòu)LosQueueCB通過(guò)queue指針來(lái)指向具體隊(duì)列的內(nèi)容，隊(duì)列分配了queueLen個(gè)消息，每個(gè)消息的大小為queueSize。與此同時(shí)頭指針和尾指針不約而同初始化為0。

第二步：第一個(gè)消息入隊(duì)列

生產(chǎn)者通過(guò)隊(duì)列來(lái)傳遞信息，這個(gè)生產(chǎn)者可以是形形色色的各個(gè)任務(wù)，產(chǎn)生一個(gè)隊(duì)列后，任務(wù)就迫不及待的需要放置消息，究竟是選擇FIFO or FILO?任務(wù)這個(gè)老大哥面臨著嚴(yán)峻的選擇，這一次我們選擇了FIFO。

下圖是FIFO插入第一個(gè)數(shù)據(jù)后的內(nèi)存形態(tài)。

OpenHarmony作為一個(gè)開(kāi)源系統(tǒng)，在下面的代碼中很好的體現(xiàn)了這個(gè)操作：

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是隊(duì)列內(nèi)存的核心操作函數(shù)，F(xiàn)IFO算法本質(zhì)是往隊(duì)列的尾處添加數(shù)據(jù)，代碼抽象為OS_QUEUE_WRITE_TAIL操作，請(qǐng)注意隊(duì)列是個(gè)循環(huán)隊(duì)列，插入數(shù)據(jù)后移動(dòng)tail這個(gè)“尾巴”指針要特別小心，在最后一個(gè)物理空間用完成后需要移到隊(duì)列頭部，這就是傳說(shuō)中環(huán)形隊(duì)列的循環(huán)大法。

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

第三步：繼續(xù)生產(chǎn)數(shù)據(jù)

好吧，上面操作重復(fù)再重復(fù)，但是OpenHarmony忠實(shí)的執(zhí)行了這種行為：代碼小編就不一一細(xì)說(shuō)了，此處是否可以來(lái)一些music? 哦no，是picture。

第四步：生產(chǎn)數(shù)據(jù)結(jié)束

生產(chǎn)者生產(chǎn)了四個(gè)消息后感覺(jué)已經(jīng)enough了，于是偷懶不再干活了。

二、 FIFO算法之出隊(duì)列

第一步：當(dāng)然是隊(duì)列第一個(gè)消息，因?yàn)槲覀兪荈IFO，先來(lái)的消息先拉出槍斃!

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

在生產(chǎn)消息過(guò)程中我們已經(jīng)提到OsQueueBufferOperate這個(gè)函數(shù)，我們回顧關(guān)鍵代碼：

/* 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就是我們的頭指針，它的移動(dòng)也面臨著生產(chǎn)過(guò)程相同的問(wèn)題，在最后一個(gè)物理空間用完成后需要移到隊(duì)列的頭部。方法是如此的相似，以至于小編都懶得解釋。OS_QUEUE_READ_HEAD是出隊(duì)列的關(guān)鍵處理，解決了queueHead頭指針如何移動(dòng)的問(wèn)題。

第二步：繼續(xù)消費(fèi)

直接上圖

第三步：消費(fèi)完畢

最后一個(gè)消息也被我們干掉了，于是head指針和tail指針均移動(dòng)到下圖的位置。此時(shí)隊(duì)列為空，活干完了，消費(fèi)者也散了。

總結(jié)

本文主要介紹了OpenHarmony內(nèi)核對(duì)象隊(duì)列的算法之FIFO。

??想了解更多內(nèi)容，請(qǐng)?jiān)L問(wèn)：??

??51CTO和華為官方合作共建的鴻蒙技術(shù)社區(qū)??

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