更多内容请访问：与华为官方共建的Harmonyos技术社区https://harmonyos.51cto.com鸿蒙LightKernel源码解析上一个系列，我们分析了双向链表的源码。本文将继续为读者介绍源码中的重要数据结构，以及基于优先级的就绪队列PriorityQueue。讲解时会结合数据结构相关的图解，培养读者对数据结构的平面想象能力，帮助读者更好地学习和理解这些数据结构的用法。1任务就绪队列在任务调度模块中，就绪队列是一个重要的数据结构。任务创建后，进入就绪状态，放入就绪队列。在鸿蒙轻内核中，就绪队列是一个双向循环链表数组，每个数组元素是一个链表，优先级相同的任务放入同一个链表。任务就绪队列PriorityQueue主要供内部使用，用户不参与业务开发，所以不对外提供接口。双向链表数组可以更方便地支持基于优先级的任务调度。任务就绪队列的核心代码在kernel\src\los_task.c文件中。1.1任务准备好的定义与任务准备好队列相关的主要变量定义在内核\src\los_task.cfile。defineos_priority_queue_prioritynum32其中其中任务就绪队，是是个个双向双向链表链表数，后文后文链表数链表初初始化始化始化该该该该数组数组数组时时会会会会将将将将数数数组(2)表示优先级位图，标识挂载就绪任务在任务就绪队列中的优先级；(3)表示优先级为0的位；(4)表示任务就绪队列支持的优先级数为32，因此鸿蒙轻内核优先级的取值范围为0-31，数值越小优先级越高。优先级位图g_priqueueBitmap的位与优先级的关系是bit=31-priority，优先级数组g_losPriorityQueueList[priority]包含OS_PRIORITY_QUEUE_PRIORITYNUM数组元素，每个数组元素是一个双向链表，相同优先级的就绪中的所有任务state会被挂载到相应优先级的双向链表中。示意图如下：2任务就绪队列操作2.1初始化任务就绪队列:LOS_KernelInit()-->kernel\src\los_task.c:OsTaskInit()-->OsPriqueueInit()。源码如下：STATICUINT32OsPriqueueInit(VOID){uint32priority;⑴Uint32Size=os_priority_queue_prioritynum*sizeOf（los_dl_list）;g_lospriorityqueuelist=（los_dl_list*）los_memememem_prientiitypriptitiityitityitityitityintiritiity;ewresliorinf（glospriorenullityque）{⑵LOS_ListInit(&g_losPriorityQueueList[priority]);}returnLOS_OK;}⑴计算就绪队列数组所需内存大小，然后为任务就绪队列申请内存，占用OS_PRIORITY_QUEUE_PRIORITYNUM双向链表所需内存大小，内存将运行时不会被释放，是系统的常驻内存。(2)此处的代码将每个数组元素初始化为一个双向循环链表。2.2任务就绪队列插入任务就绪队列插入函数为OsPriqueueEnqueue()，将就绪状态的任务插入到任务就绪队列的尾部。在任务就绪队列中，先调用队头任务，最后调用队尾任务。])){⑵g_priqueueBitmap|=(PRIQUEUE_PRIOR0_BIT>>priority);}⑶LOS_ListTailInsert(&g_losPriorityQueueList[priority],priqueueItem);}⑴处理先判断指定priority的任务就绪队列是否为空，为空则更新priority(2)处的位图，将第31位优先位设置为1。(3)将处于就绪状态的任务插入到任务就绪队列的尾部进行排队。2.3从任务就绪队列中删除从任务就绪队列中删除的函数是OsPriqueueDequeue()。在任务被删除、进入suspend阻塞状态、调整优先级等场景下，需要调用该函数将任务从任务就绪队列中删除。源码如下：STATICVOIDOsPriqueueDequeue(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_PRIOR10_BIT>});(PRIQUEUE_PRIOR1_BIT>})从任务就绪队列中删除任务。(2)获取被删除任务的任务控制块信息，获取任务的优先级。任务删除后，队列可能变成空队列，所以(3)处的代码判断任务就绪队列是否为空。如果为空，则需要执行（4）处的代码，更新优先级位图，将31-prioritybit设置为0。2.4获取队列中优先级最高的节点获取任务就绪队列中优先级最高的链表节点的函数是OsPriQueueTop()。源码如下：STATICLOS_DL_LIST*OsPriqueueTop(VOID){UINT32priority;⑴if(g_priqueueBitmap!=0){⑵priority=CLZ(g_priqueueBitmap);⑶returnLOS_DL_LIST_FIRST(&g_losPriorityQueueList[priority]);}return(LOS_DL;LIST*)NULL查看g_priqueueBitmap是否为0，如果为0则直接返回NULL，说明任务就绪队列中没有就绪任务。(2)计算g_priqueueBitmap用二进制表示时高位为0的位数，其值为任务的优先级。该方法得到的优先级是任务就绪队列中所有优先级中最高的。然后(3)从优先级队列&g_losPriorityQueueList[priority]中获取第一个链表节点，获取任务就绪队列中优先级最高的任务。2.5获取指定优先级就绪任务数获取任务就绪队列中指定优先级任务数的函数是OsPriqueueSize()。Thesourcecodeisasfollows:STATICUINT32OsPriqueueSize(UINT32priority){UINT32itemCnt=0;LOS_DL_LIST*curPQNode=(LOS_DL_LIST*)NULL;⑴LOS_DL_LIST_FOR_EACH(curPQNode,&g_losPriorityQueueList[priority]){⑵++forDL_LIST_ST_ST_CODEdefinitionusingmacro⑴OS_DL_LIST_ST_OS}}Loopthroughthedoubly指定优先级的链表。如果获取到新节点，则说明该优先级下有就绪任务，然后执行（2）处的代码，将计数加1。返回结果为指定优先级Ready任务下有多少任务。小结掌握了鸿蒙LightKernel的PriorityQueue这个重要的数据结构，将为进一步学习和分析鸿蒙LightKernel的源码打下基础，让后续的学习更加轻松。后续会陆续推出更多分享文章，敬请期待。更多信息请访问：Harmonyos.51cto.com，与华为官方合作打造的鸿蒙技术社区
