LiteOS内核源码分析系列一 盘点那些重要的数据结构 -- PQ

在学习Huawei LiteOS源代码的时候，常常会遇到一些数据结构的使用。如果没有掌握这它们的用法，阅读LiteOS源代码的时候会很费解、很吃力。本文会给读者介绍下LiteOS源码中常用的几个数据结构，包括: 双向循环链表LOS_DL_LIST，优先级队列Priority Queue，排序链表SortLinkList等。在讲解时，会结合相关的绘图，培养数据结构的平面想象能力，帮助更好的学习和理解这些数据结构用法。

本文中所涉及的LiteOS源码，均可以在LiteOS开源站点https://gitee.com/LiteOS/LiteOS 获取。

这是第二部分，我们来看看使用最多的Priority Queue优先级队列。

2、Priority Queue 优先级队列

在任务调度模块，就绪队列是个重要的数据结构，就绪队列需要支持初始化，出入队列，从队列获取最高优先级任务等操作。LiteOS调度模块支持单一就绪队列（Single Ready Queue）和多就绪队列（Multiple Ready Queue），我们这里主要讲述一下单一就绪队列。

优先级队列Priority Queue接口主要内部使用，用户业务开发时不涉及，不对外提供接口。优先级队列其实就是个双向循环链表数组，提供更加方便的接口支持任务基于优先级进行调度。
优先级队列核心的代码都在kernel\base\include\los_priqueue_pri.h头文件和kernel\base\sched\sched_sq\los_priqueue.c实现文件中。

我们来看看优先级队列支持的操作。

2.1 Priority Queue 优先级队列变量定义

LiteOS支持32个优先级，取值范围0-31，优先级数值越小优先级越大。优先级队列在kernel\base\sched\sched_sq\los_priqueue.c文件中定义的几个变量如下，
其中⑴表示优先级为0的位，⑵处表示优先级队列的双向链表数组，后文会初始化为数组的长度为32，⑶表示优先级位图，标志哪些优先级就绪队列里有挂载的任务。

示意图如下：
优先级位图g_priQueueBitmap的bit位和优先级的关系是bits=31-priority，g_priQueueList[priority]优先级数组内容为双向链表，挂载各个优先级的处于就绪状态的任务。

源码如下：

   #define OS_PRIORITY_QUEUE_NUM 32
⑴ #define PRIQUEUE_PRIOR0_BIT   0x80000000U
⑵ LITE_OS_SEC_BSS LOS_DL_LIST *g_priQueueList = NULL;
⑶ STATIC LITE_OS_SEC_BSS UINT32 g_priQueueBitmap;

下面我们来学习下优先级队列支持的那些操作。

2.2 Priority Queue 优先级队列接口

2.2.1 OsPriQueueInit(VOID)初始化

优先级队列初始化在系统初始化的时候调用：main.c:main(void)k-->kernel\init\los_init.c:OsMain(VOID)-->kernel\base\los_task.c:OsTaskInit(VOID)-->OsPriQueueInit()。

从下面的代码可以看出，⑴处申请长度为32的双向链表数值申请常驻内存，运行期间不会调用Free()接口释放。⑴处代码为数组的每一个双向链表元素都初始化为双向循环链表。

源码如下：

UINT32 OsPriQueueInit(VOID)
{
    UINT32 priority;
    /* 系统常驻内存，运行期间不会Free释放 */
⑴  g_priQueueList = (LOS_DL_LIST *)LOS_MemAlloc(m_aucSysMem0, (OS_PRIORITY_QUEUE_NUM * sizeof(LOS_DL_LIST)));
    if (g_priQueueList == NULL) {
        return LOS_NOK;
    }
    for (priority = 0; priority < OS_PRIORITY_QUEUE_NUM; ++priority) {
⑵      LOS_ListInit(&g_priQueueList[priority]);
    }
    return LOS_OK;
}

2.2.2 OsPriQueueEnqueueHead()插入就绪队列头部

OsPriQueueEnqueueHead()从就绪队列的头部进行插入，插入得晚，但在同等优先级的任务中，会第一个调度。一起看下代码，⑴处先判断指定优先级priority的就绪队列是否为空，如果为空，则在⑵处更新优先级位图。⑶处把就绪状态的任务插入就绪队列的头部，以便优先调度。

源码如下：

VOID OsPriQueueEnqueueHead(LOS_DL_LIST *priqueueItem, UINT32 priority)
{
    LOS_ASSERT(priqueueItem->pstNext == NULL);
⑴  if (LOS_ListEmpty(&g_priQueueList[priority])) {
⑵      g_priQueueBitmap |= PRIQUEUE_PRIOR0_BIT >> priority;
    }
⑶  LOS_ListHeadInsert(&g_priQueueList[priority], priqueueItem);
}

2.2.3 OsPriQueueEnqueue()插入就绪队列尾部

和OsPriQueueEnqueueHead()的区别是，把就绪状态的任务插入就绪队列的尾部，同等优先级的任务中，后插入的后调度。

2.2.4 OsPriQueueDequeue()就绪队列中删除

在任务被删除、进入suspend状态，优先级调整等场景时，都需要调用接口OsPriQueueEnqueue()把任务从优先级队列中删除。

我们来看下代码，⑴把任务从优先级就绪队列中删除。⑵获取删除的任务TCB信息，用来获取任务的优先级。刚从优先级队列中删除了一个任务，⑶处代码判断优先级队列是否为空，
如果为空，则需要执行⑷处代码，把优先级位图中对应的优先级bit位置为0。

源码如下：

VOID OsPriQueueDequeue(LOS_DL_LIST *priqueueItem)
{
    LosTaskCB *runTask = NULL;
⑴  LOS_ListDelete(priqueueItem);
⑵  runTask = LOS_DL_LIST_ENTRY(priqueueItem, LosTaskCB, pendList);
⑶  if (LOS_ListEmpty(&g_priQueueList[runTask->priority])) {
⑷      g_priQueueBitmap &= ~(PRIQUEUE_PRIOR0_BIT >> runTask->priority);
    }
}

2.2.5 LOS_DL_LIST *OsPriQueueTop(VOID)获取就绪的优先级最高的链表节点

这个接口可以获取优先级就绪队列中优先级最高的链表节点。⑴处判断优先级位图g_priQueueBitmap是否为0，如果为0，说明没有任何就绪状态的任务，返回NULL。 ⑵处计算g_priQueueBitmap二进制时开头的0的数目，这个数目对应于
任务的优先级priority，然后⑶处从&g_priQueueList[priority]优先级队列链表中获取第一个链表节点。

源码如下：

LOS_DL_LIST *OsPriQueueTop(VOID)
{
    UINT32 priority;
⑴  if (g_priQueueBitmap != 0) {
⑵      priority = CLZ(g_priQueueBitmap);
⑶      return LOS_DL_LIST_FIRST(&g_priQueueList[priority]);
    }
    return NULL;
}

2.2.6 UINT32 OsPriQueueSize(UINT32 priority)获取指定优先级的就绪任务的数量

这个接口可以获取指定优先级的就绪队列中任务的数量。⑴、⑶处代码表示，在SMP多核模式下，根据获取的当前CPU编号的cpuId，判断任务是否属于当前CPU核，如果不属于，则不计数。⑵处代码使用for循环遍历指定优先级就绪队列中的链表节点，对遍历到新节点则执行⑷处代码，对计数进行进行加1操作。

源码如下：

    UINT32 OsPriQueueSize(UINT32 priority)
    {
        UINT32 itemCnt = 0;
        LOS_DL_LIST *curNode = NULL;
    #ifdef LOSCFG_KERNEL_SMP
        LosTaskCB *task = NULL;
⑴      UINT32 cpuId = ArchCurrCpuid();
    #endif
        LOS_ASSERT(ArchIntLocked());
        LOS_ASSERT(LOS_SpinHeld(&g_taskSpin));
⑵      LOS_DL_LIST_FOR_EACH(curNode, &g_priQueueList[priority]) {
    #ifdef LOSCFG_KERNEL_SMP
            task = OS_TCB_FROM_PENDLIST(curNode);
⑶          if (!(task->cpuAffiMask & (1U << cpuId))) {
                continue;
            }
    #endif
⑷          ++itemCnt;
        }
        return itemCnt;
    }

2.2.7 LosTaskCB *OsGetTopTask(VOID)获取就绪的优先级最高的任务

这个接口或者就绪任务队列中优先级最高的任务。一起看下代码，⑴、⑷处对SMP多核做特殊处理，如果是多核，只获取指定在当前CPU核运行的优先级最高的任务。⑵处获取g_priQueueBitmap优先级位图的值，赋值给UINT32 bitmap;。不直接操作优先级位图的原因是什么呢？在SMP多核时，在高优先级任务就绪队列里没有找到指定在当前CPU核运行的任务，需要执行⑹处的代码，清零临时优先级位图的bit位，去低一级的优先级就绪队列里去查找。只能改动临时优先级位图，不能改变g_priQueueBitmap。⑶处代码对优先级最高的就绪队列进行遍历，如果遍历到则执行⑸处代码从优先级就绪队列里出队，函数返回对应的LosTaskCB *newTask。

源码如下：

    {
        UINT32 priority;
        UINT32 bitmap;
        LosTaskCB *newTask = NULL;
    #ifdef LOSCFG_KERNEL_SMP
⑴      UINT32 cpuid = ArchCurrCpuid();
    #endif
⑵      bitmap = g_priQueueBitmap;
        while (bitmap) {
            priority = CLZ(bitmap);
⑶          LOS_DL_LIST_FOR_EACH_ENTRY(newTask, &g_priQueueList[priority], LosTaskCB, pendList) {
    #ifdef LOSCFG_KERNEL_SMP
⑷              if (newTask->cpuAffiMask & (1U << cpuid)) {
    #endif
⑸                  OsPriQueueDequeue(&newTask->pendList);
                    goto OUT;
    #ifdef LOSCFG_KERNEL_SMP
                }
    #endif
            }
⑹          bitmap &= ~(1U << (OS_PRIORITY_QUEUE_NUM - priority - 1));
        }
    OUT:
        return newTask;
    }