共计 3880 个字符，预计需要花费 10 分钟才能阅读完成。
摘要： 本文会给读者介绍鸿蒙轻内核 M 核源码中重要的数据结构，工作基于优先级的就绪队列 Priority Queue。
本文分享自华为云社区《鸿蒙轻内核 M 核源码剖析系列三 数据结构 - 工作就绪队列》，原文作者：zhushy。
本文会给读者介绍鸿蒙轻内核 M 核源码中重要的数据结构，工作基于优先级的就绪队列 Priority Queue。
在解说时，会联合数据结构相干绘图，造就读者们的数据结构的立体设想能力，帮忙更好的学习和了解这些数据结构的用法。本文中所波及的源码，以 OpenHarmony LiteOS- M 内核为例，均能够在开源站点 https://gitee.com/openharmony… 获取。
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…。为了更容易找到鸿蒙轻内核代码仓，倡议拜访 https://gitee.com/openharmony…，关注 Watch、点赞 Star、并 Fork 到本人账户下，谢谢。
点击关注，第一工夫理解华为云陈腐技术~
