更多内容请访问：鸿蒙LightKernel源码解析系列1中的Harmonyos技术社区https://harmonyos.51cto.com2、我们分析了双向链表和优先就绪队列的源码。本文将继续向读者介绍鸿蒙LightKernel源码中的一个重要数据结构：任务排序列表TaskSortLinkAttr。鸿蒙轻内核的任务排序列表用于任务延迟到期/超时唤醒等业务场景，是一个非常重要的基础数据结构。1任务排序链表先来看一下任务排序链表的数据结构。任务排序链表是一个循环双向链表数组。任务排序链表属性结构体TaskSortLinkAttr作为双向链表的头节点，指向双向链表数组的第一个元素，维护游标信息记录当前位置信息。我们先看一下排序链表属性结构体的定义。1.1任务排序链表属性结构体定义排序链表属性结构体TaskSortLinkAttr定义在kernel\include\los_task.h头文件中。该结构体定义了排序链表的头节点LOS_DL_LIST*sortLink，游标UINT16游标，以及一个保留字段，暂时不用。源码如下：typedefstruct{LOS_DL_LIST*sortLink;UINT16cursor;UINT16reserved;}TaskSortLinkAttr;在文件kernel\src\los_task.c中，定义了排序链表属性结构体TaskSortLinkAttr类型的全局变量g_taskSortLink，该全局变量的成员变量sortLink作为排序链表的头节点，指向一个长度为32的循环双向链表数组，成员变量cursor作为游标记录循环数组当前游标位置。源代码如下。LITE_OS_SEC_BSSTaskSortLinkAttrg_taskSortLink；下面我们用示意图来讲述一下。任务排序链表是一个循环双向链表数组，长度为32，每个元素都是一个双向链表，挂载任务LosTaskCB的链表节点timerList。任务LosTaskCB的成员变量idxRollNum记录了数组的索引和滚动数。全局变量g_taskSortLink的成员变量cursor记录了当前光标位置。每经过一个Tick，光标指向下一个位置，转一圈需要32个tick。当运行到数组位置且双向链表不为空时，将第一个节点维护的滚动数减1。这样的数据结构类似于钟面，也称为时间轮。下面举例说明基于时间轮实现的任务排序列表是如何管理任务延迟超时的。如果当前游标为1，当一个任务需要延迟72个ticks时，72=2*32+8，表示排序索引sortIndex为8，滚动数rollNum为2，任务会插入到数组索引为sortIndex+cursor=9的双向链表位置，要求位置9的双向链表维护节点的滚动次数为2。随着Tick时间的推进，从当前游标位置运行到数组索引位置9，持续8个刻度。运行到9时，如果滚动数大于0，则滚动数减1。再运行2轮后，一共需要72个tick，任务会延迟过期，可以移除从排序列表中。每个数组元素对应的双向链表的第一个链表节点的滚动数表示节点任务到期前需要转多少轮。第二个链表节点的滚动数需要加上第一个节点的滚动数，表示第二个节点需要转的圈数。等等。示意图如下：1.2任务排序列表宏定义OS_TSK_SORTLINK_LEN头文件中定义了一些与任务排序列表相关的宏定义。延迟任务双向链表数组长度定义为32，高位个数为5，低位个数为27。对于任务的超时时间，使用高27位作为滚动数，低5位作为数组索引。Thesourcecodeisasfollows:/***Thenumberofdelayedtaskdoublylinkedlistarrays(numberofbuckets):32*/#defineOS_TSK_SORTLINK_LEN32/***Thenumberofhigh-orderbits:5*/#defineOS_TSK_HIGH_BITS5U/***Thenumberoflow-orderbits:27*/#defineOS_TSK_LOW_BITS(32U-OS_TSK_HIGH_BITS)/***滚动数最大值：0xFFFFFFDF，11110111111111111111111111011111*/#defineOS_TSK_MAX_ROLLNUM(0xFFFFFFFFU-OS_TSK_SORTLINK_LEN)/***任务延迟时间数的位宽：5*/#defineOS_TSK_SORTLINK_LOGLEN5/***延迟任务的桶编号的掩码:31、00011111*/#defineOS_TSK_SORTLINK_MASK(OS_TSK_SORTLINK_LEN-1U)/***滚动数的高阶掩码:11111000000000000000000000000000*/#defineOS_TSK_HIGH_BITS_MASK(OS_TSK_SORTLINK_MASK<kernel\src\los_init.c:LOS_KernelInit()-->kernel\src\los_task.c:OsTaskInit().初始化排序列表函数源代码如下：;⑵if(listObject==NULL){(VOID)LOS_MemFree(m_aucSysMem0,g_taskCBArray);returnLOS_ERRNO_TSK_NO_MEMORY;}⑶(VOID)memset_s((VOID*)listObject,size,0,size);⑷g_taskSortLink.sortLink=listObject;g_taskSortLink.cursor=0;for(index=0;index>OS_TSK_SORTLINK_LOGLEN);⑵(sortIndex>0)?0:(rollNum--);⑶EVALUATE_L(taskCB->idxRollNum,rollNum);⑷sortIndex=(sortIndex+g_taskSortLink.cursor);sortIndex=sortIndex&OS_TSK_SORTLINK_MASK;⑦EVALUATE_H(taskCB->idxRollNum,sortIndex);⑷listObject=g_taskSortLink.sortLink+ifsortIndex(listObject->pstNext==listObject){LOS_ListTailInsert(listObject,&taskCB->timerList);}else{⑻taskDelay=LOS_DL_LIST_ENTRY((listObject)->pstNext,LosTaskCB,timerList);do{⑼if(UWROLLNUM(taskDelay->idxRollNum)<=UWROLLNUM(taskCB->idxRollNum)){UWROLLNUMSUB(taskCB->idxRollNum,taskDelay->idxRollNum);}else{⑽UWROLLNUMSUB(taskDelay->idxRollNum,taskCB->idxRollNum);中断;}⑾taskDelay=LOS_DL_LIST_ENTRY(taskDelay->timerList.pstNext,LosTaskCB,timerList);}while(&taskDelay->timerList!=(listObject));⑿LOS_ListTailInsert(&taskDelay->timerList,&taskCB->timerList);}}⑴等待时间timeout的低5位计算为数组index，高27位作为滚动数rollNum。这两行代码的数学意义是将等待时间为32时得到的商作为滚动数，余数作为数组索引。(2)代码中，如果余数为0，当可以整除时，rollingnumber会减1。设计负1的原因是在函数VOIDOsTaskScan(VOID)中，当每次tick到达，如果滚动数大于0，则滚动数减1，继续滚动一圈。后面会分析函数VOIDOsTaskScan(VOID)。(3)处的代码将滚动数分配给任务taskCB->idxRollNum的低27位。⑷给游标加上数组索引，然后执行⑷给任务taskCB->idxRollNum的高5位赋值。⑴根据数组索引得到双向链表的头节点，⑺如果这里的双向链表为空，则直接插入到链表中。如果链表不为空，则执行(8)获取第一个链表节点对应的任务taskDelay，然后遍历循环双向链表将任务插入到合适的位置。⑼时，如果要插入的taskCB的滚动数大于等于当前链表节点对应的任务的滚动数，则滚动数减去当前链表节点对应的任务的滚动数待插入的taskCB，然后执行⑾得到下一个节点继续遍历。如果待插入taskCB的滚动数小于当前链表节点对应的task滚动数，则将当前链表节点对应的task滚动数减去待插入taskCB的滚动数，然后跳出循环。执行⑿完成任务插入。插入过程可以结合上面的示意图来理解。2.3从排序链表中删除从排序链表中删除的函数是VOIDOsTimerListDelete(LosTaskCB*taskCB)。在任务恢复/删除等场景下，需要调用该函数将任务从任务排序列表中删除。该函数包含一个参数LosTaskCB*taskCB，用于指定要从排序列表中删除的任务。源码如下：LITE_OS_SEC_TEXTVOIDOsTimerListDelete(LosTaskCB*taskCB){LOS_DL_LIST*listObject=NULL;LosTaskCB*nextTask=NULL;UINT32sortIndex;⑴sortIndex=UWSORTINDEX(taskCB->idxRollNum);⑵listObject=g_taskCdeskSortLink.sort⑶timer.sortLink!){⑷nextTask=LOS_DL_LIST_ENTRY(taskCB->timerList.pstNext,LosTaskCB,timerList);UWROLLNUMADD(nextTask->idxRollNum,taskCB->idxRollNum);}⑸LOS_ListDelete(&taskCB->timerList);}⑴从数值索引中获取代码对应排序列表中删除的任务。(2)此处代码获取排序后链表的头节点listObject。⑶处的代码判断要删除的节点是否为最后一个节点。如果不是最后一个节点，则执行⑷处的代码，获取待删除节点的下一个节点对应的任务nextTask，将待删除节点的滚动数加到下一个节点号的滚动数上，然后执行（5）处的代码执行删除操作。如果是最后一个节点，只需要执行（5）处的代码，删除该节点即可。2.4获取下一次超时过期时间获取下一次超时过期时间的函数是OsTaskNextSwitchTimeGet()，我们来分析一下它的代码。源码如下：UINT32OsTaskNextSwitchTimeGet(VOID){LosTaskCB*taskCB=NULL;UINT32taskSortLinkTick=LOS_WAIT_FOREVER;LOS_DL_LIST*listObject=NULL;UINT32tempTicks;UINT32index;⑴for(index=0;indexpstNext,LosTaskCB,timerList);⑸tempTicks=(index==0)?OS_TSK_SORTLINK_LEN:index;⑹tempTicks+=(UINT32)(UWROLLNUM((UINT32)taskCB->idxRollNum)*OS_TSK_SORTLINK_LEN);⑺if(taskSortLinkTick>tempTicks){taskSortLinkTick=tempTicks;}}}returntaskSortLinkTick;}⑴处的代码循环遍历双向链表数组，⑵处的代码从当前光标位置开始获取排序后的链表的头节点listObject。(3)处的代码判断排序后的链表是否为空，如果排序后的链表为空则继续遍历下一个数组。如果链表不为空，则(4)处的代码获取排序后链表的第一个链表节点对应的任务。(5)如果遍历的numberindex为0，则tick数使用32，否则使用具体的numberindex。⑴获取滚动任务数，计算需要等待的时间，将⑷计算的时间加到一圈以内。(7)计算最小等待时间，即下一个最快的过期时间。3排序链表与Tick时间的关系任务加入排序链表后，时间一滴一滴的过去，如何更新排序链表中的滚动条数？时间每经过一个tick，系统就会调用Tick中断的处理函数OsTickHandler()，该函数在kernel\src\los_tick.c文件中实现。以下是该函数的代码片段，其中（1）处的代码在每个任务达到超时时到期。LITE_OS_SEC_TEXTVOIDOsTickHandler(VOID){#if(LOSCFG_BASE_CORE_TICK_HW_TIME==1)platform_tick_handler();#endifg_ullTickCount++;#if(LOSCFG_BASE_CORE_TIMESLICE==1)OsTimesliceCheck();#endif⑴OsTaskWTScan();//tasktimeoutscan_SCAN_if(IDLOSCF))OsSwtmrScan();#endif}详细分析OsTaskScan()函数，了解排序后的链表与tick时间的关系。函数函数内核\base\los_task.c文件中中，代码：lite_os_os_sec_sec_sec_textvoidostasksaskscan（void）{taskcb*taskcb*taskcb*taskcb=null;booolneedschedschedschedschedule=falsion;cursor=(g_taskSortLink.cursor+1)%OS_TSK_SORTLINK_LEN;listObject=g_taskSortLink.sortLink+g_taskSortLink.cursor;⑵if(listObject->pstNext==listObject){LOS_IntRestore(intSave);return;}⑶for(taskCB=LOS_DL_LIST_ENTRY((listObject)->pstNext,LosTaskCB,timerList);&taskCB->timerList!=(listObject);){tempStatus=taskCB->taskStatus;⑷if(UWROLLNUM(taskCB->idxRollNum)>0){UWROLLNUMDEC(taskCB->idxRollNum);break;}⑸LOS_ListDelete(&taskCB->timerList);⑹if(tempStatus&OS_TASK_STATUS_PEND){taskCB->taskStatus&=~(OS_TASK_STATUS_PEND);LOS_ListDelete(&taskCB->pendList);taskCB->taskSem=NULL;taskCB->taskMux=NULL;}⑺elseif(tempStatus&OS_TASK_STATUS_EVENT){taskCB->taskStatus&=~(OS_TASK_STATUS_EVENT);}⑻elseif(tempStatus&OS_TASK_STATUS_PEND_QUEUE){LOS_ListDelete(&taskCB->pendList);taskCB->taskStatus&=~(OS_TASK_STATUS_PEND_QUEUE);}else{taskCB->taskStatus&=~(OS_TASK_STATUS_DELAY);}⑼if(!(tempStatus&OS_TASK_task)->{taskCB|STATUS_SUSPStatus=OS_TASK_STATUS_READY;OsHookCall(LOS_HOOK_TYPE_MOVEDTASKTOREADYSTATE,taskCB);OsPriqueueEnqueue(&taskCB->pendList,taskCB->priority);needSchedule=TRUE;}if(listObject->pstNext==listObject){break;}taskNext=LOS_DL_LIST_ENTY,LostimerTaskCB);}LOS_IntRestore(intSave);⑽if(needSchedule){LOS_Schedule();}}⑴该处代码更新全局变量g_taskSortLink的游标，指向双向链表数组的下一个位置，进而获取双向链表那个位置的header指向listObject(2)如果链表为空，则返回。如果双向链表不为空，则执行（3）循环遍历每个链表节点。(4)如果链表节点的滚动数大于0，则滚动数减1，表示任务还需要等待下一轮。如果链表节点的滚动数等于0，则表示任务超时，执行（5）从排序好的链表中删除。接下来需要根据任务状态分别进行处理。如果代码在⑩处处于阻塞状态，则取消阻塞状态，将其从阻塞列表中删除。(7)如果任务在事件中被阻塞，则取消阻塞状态。⑻如果任务在队列中被阻塞，则将其从阻塞链表中删除，取消阻塞状态。如果不是以上状态，取消延迟状态OS_TASK_STATUS_DELAY。⑼如果代码处于挂起状态，则将任务设置为就绪状态，加入任务就绪队列，并设置需要重新调度标志。⑽如果设置需要重新调度，调用调度函数触发任务调度。总结掌握了鸿蒙LightKernel的排序表TaskSortLinkAttr的重要数据结构，将为进一步学习和分析鸿蒙LightKernel的源码打下基础，让后续的学习更加轻松。更多信息请访问：Harmonyos.51cto.com，与华为官方合作打造的鸿蒙技术社区
