摘要：本文会给读者介绍鸿蒙轻内核M核源码中重要的数据结构，任务基于优先级的就绪队列Priority Queue。
本文分享自华为云社区《鸿蒙轻内核M核源码分析系列三 数据结构-任务就绪队列》，原文作者：zhushy 。
本文会给读者介绍鸿蒙轻内核M核源码中重要的数据结构，任务基于优先级的就绪队列Priority Queue。
在讲解时，会结合数据结构相关绘图，培养读者们的数据结构的平面想象能力，帮助更好的学习和理解这些数据结构的用法。本文中所涉及的源码，以OpenHarmony LiteOS-M内核为例，均可以在开源站点https://gitee.com/openharmony/kernel_liteos_m 获取。
1 任务就绪队列
在任务调度模块，就绪队列是个重要的数据结构。任务创建后即进入就绪态，并放入就绪队列。在鸿蒙轻内核中，就绪队列是一个双向循环链表数组，每个数组元素就是一个链表，相同优先级的任务放入同一个链表。
任务就绪队列Priority Queue主要供内部使用，用户进行业务开发时不涉及，所以并未对外提供接口。双向循环链表数组能够更加方便的支持任务基于优先级进行调度。任务就绪队列的核心代码在kernel\src\los_task.c文件中。
1.1 任务就绪队列的定义
在kernel\src\los_task.c文件中定义了和任务就绪队列相关的主要变量。
源码如下：
⑴ LITE_OS_SEC_BSS LOS_DL_LIST *g_losPriorityQueueList = NULL; ⑵ static LITE_OS_SEC_BSS UINT32 g_priqueueBitmap = 0; ⑶ #define PRIQUEUE_PRIOR0_BIT (UINT32)0x80000000 ⑷ #define OS_PRIORITY_QUEUE_PRIORITYNUM 32
其中⑴表示任务就绪队列，是一个双向链表数组，后文初始化该数组时会将数组长度设置为⑷处定义的OS_PRIORITY_QUEUE_PRIORITYNUM；⑵表示优先级位图，标识了任务就绪队列中已挂载的就绪任务所在的优先级；⑶表示优先级为0的比特位；⑷表示任务就绪队列支持的优先级个数32，所以鸿蒙轻内核优先级的取值范围为0-31，数值越小优先级越大。
优先级位图g_priqueueBitmap的bit位和优先级的关系为bit=31-priority，优先级数组g_losPriorityQueueList[priority]包含了OS_PRIORITY_QUEUE_PRIORITYNUM个数组元素，每个数组元素都是一个双向链表，同一优先级的处于就绪状态的所有任务都会挂载到对应优先级的双向链表中。
示意图如下：
2 任务就绪队列操作
2.1 初始化任务就绪队列
任务就绪队列初始化函数为OsPriQueueInit()，系统初始化阶段被调用，调用路径为：main.c:main() --> kernel\src\los_init.c:LOS_KernelInit() --> kernel\src\los_task.c:OsTaskInit() --> OsPriqueueInit()。
源码如下：
STATIC UINT32 OsPriqueueInit(VOID)
{
UINT32 priority;
⑴ UINT32 size = OS_PRIORITY_QUEUE_PRIORITYNUM * sizeof(LOS_DL_LIST);
g_losPriorityQueueList = (LOS_DL_LIST *)LOS_MemAlloc(m_aucSysMem0, size);
if (g_losPriorityQueueList == NULL) {
return LOS_NOK;
}
for (priority = 0; priority < OS_PRIORITY_QUEUE_PRIORITYNUM; ++priority) {
⑵ LOS_ListInit(&g_losPriorityQueueList[priority]);
}
return LOS_OK;
}
⑴处计算就绪队列数组需要的内存大小，然后为任务就绪队列申请内存，占用内存为OS_PRIORITY_QUEUE_PRIORITYNUM个双向链表所需要的内存大小，运行期间该内存不会释放，为系统常驻内存。⑵处代码将每一个数组元素都初始化为双向循环链表。
2.2 任务就绪队列插入
任务就绪队列插入函数为OsPriqueueEnqueue()，该函数把就绪状态的任务插入任务就绪队列的尾部。在任务就绪队列中，先调用队列头部的任务，最后调用队列尾部的任务。
源码如下：
STATIC VOID OsPriqueueEnqueue(LOS_DL_LIST *priqueueItem, UINT32 priority)
{
⑴ if (LOS_ListEmpty(&g_losPriorityQueueList[priority])) {
⑵ g_priqueueBitmap |= (PRIQUEUE_PRIOR0_BIT >> priority);
}
⑶ LOS_ListTailInsert(&g_losPriorityQueueList[priority], priqueueItem);
}
⑴处先判断指定优先级priority的任务就绪队列是否为空，如果为空，则在⑵处更新优先级位图，将第31-prioritybit位设置为1。⑶处把就绪状态的任务插入任务就绪队列的尾部，进行排队。
2.3 从任务就绪队列中删除
从任务就绪队列中删除的函数为OsPriqueueDequeue()。任务被删除、进入suspend阻塞状态、优先级调整等场景中，都需要调用该函数把任务从任务就绪队列中删除。
源码如下：
STATIC VOID OsPriqueueDequeue(LOS_DL_LIST *priqueueItem)
{
LosTaskCB *runningTask = NULL;
⑴ LOS_ListDelete(priqueueItem);
⑵ runningTask = LOS_DL_LIST_ENTRY(priqueueItem, LosTaskCB, pendList);
⑶ if (LOS_ListEmpty(&g_losPriorityQueueList[runningTask->priority])) {
⑷ g_priqueueBitmap &= ~(PRIQUEUE_PRIOR0_BIT >> runningTask->priority);
}
}
⑴把任务从任务就绪队列中删除。⑵获取被删除任务的任务控制块信息，以获取任务的优先级。删除完任务后队列可能成为空队列，所以⑶处代码判断任务就绪队列是否为空，如果为空，则需要执行⑷处代码，更新优先级位图，将第31-prioritybit位设置为0。
2.4 获取队列中的最高优先级节点
获取任务就绪队列中优先级最高的链表节点的函数为OsPriQueueTop()。
源码如下：
STATIC LOS_DL_LIST *OsPriqueueTop(VOID)
{
UINT32 priority;
⑴ if (g_priqueueBitmap != 0) {
⑵ priority = CLZ(g_priqueueBitmap);
⑶ return LOS_DL_LIST_FIRST(&g_losPriorityQueueList[priority]);
}
return (LOS_DL_LIST *)NULL;
}
⑴处判断优先级位图g_priqueueBitmap是否为0，如果为0则直接返回NULL，说明任务就绪队列中没有任何就绪状态的任务。 ⑵处计算g_priqueueBitmap以二进制表示时高位为0的位数，其值就是任务的优先级priority，以此方法得到的优先级就是任务就绪队列中所有优先级里最高的。然后⑶处从该优先级的队列&g_losPriorityQueueList[priority]中获取第一个链表节点，获取的就是任务就绪队列中优先级最高的任务。
2.5 获取指定优先级的就绪任务的数量
获取任务就绪队列中指定优先级的任务数量的函数为OsPriqueueSize()。
源码如下：
STATIC UINT32 OsPriqueueSize(UINT32 priority)
{
UINT32 itemCnt = 0;
LOS_DL_LIST *curPQNode = (LOS_DL_LIST *)NULL;
⑴ LOS_DL_LIST_FOR_EACH(curPQNode, &g_losPriorityQueueList[priority]) {
⑵ ++itemCnt;
}
return itemCnt;
}
⑴处代码使用宏LOS_DL_LIST_FOR_EACH定义的for循环遍历指定优先级priority的双向链表，如果获取到新节点则表示该优先级下有一个就绪任务，然后执行⑵处代码，对计数进行加1操作，返回的结果就是指定优先级下有多少个就绪任务。
小结
掌握鸿蒙轻内核的优先级就绪队列Priority Queue这一重要的数据结构，会给进一步学习、分析鸿蒙轻内核源代码打下了基础，让后续的学习更加容易。后续也会陆续推出更多的分享文章，敬请期待，也欢迎大家分享学习、使用鸿蒙轻内核的心得，有任何问题、建议，都可以留言给我们： https://gitee.com/openharmony/kernel_liteos_m/issues 。为了更容易找到鸿蒙轻内核代码仓，建议访问 https://gitee.com/openharmony/kernel_liteos_m ，关注Watch、点赞Star、并Fork到自己账户下，谢谢。