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

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; }

轻量级操作系统 LiteOS

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。