OpenHarmony-内核对象队列之算法详解

​​想了解更多内容，请访问：​​

​​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​​