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

举报
zhushy 发表于 2021/02/22 14:47:21 2021/02/22
【摘要】 在学习Huawei LiteOS源代码的时候,常常会遇到一些数据结构的使用。如果没有掌握这它们的用法,阅读LiteOS源代码的时候会很费解、很吃力。本文会给读者介绍下LiteOS源码中常用的几个数据结构,包括: 双向循环链表LOS_DL_LIST,优先级队列Priority Queue,排序链表SortLinkList等。在讲解时,会结合相关的绘图,培养数据结构的平面想象能力,帮助更好的学习和理解

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]优先级数组内容为双向链表,挂载各个优先级的处于就绪状态的任务。


LOS_PRIQUEUE.png

源码如下:

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

【版权声明】本文为华为云社区用户原创内容,转载时必须标注文章的来源(华为云社区)、文章链接、文章作者等基本信息, 否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

举报
请填写举报理由
0/200