v06.03 鸿蒙内核源码分析(调度队列篇) | 内核有多少个调度队列 | 百篇博客分析HarmonyOS源码

原创
2020/09/19 00:50
阅读数 1.7W

子曰:“君子食无求饱,居无求安,敏于事而慎于言,就有道而正焉,可谓好学也已。”《论语》:学而篇

在这里插入图片描述

百篇博客系列篇.本篇为:

v06.xx 鸿蒙内核源码分析(调度队列篇) | 内核有多少个调度队列

任务管理相关篇为:

为何单独讲调度队列?

鸿蒙内核代码中有两个源文件是关于队列的,一个是用于调度的队列,另一个是用于线程间通讯的IPC队列。

IPC队列后续有专门的博文讲述,这两个队列的数据结构实现采用的都是双向循环链表,再说一遍LOS_DL_LIST实在是太重要了,是理解鸿蒙内核的关键,说是最重要的代码一点也不为过,源码出现在 sched_sq模块,说明是用于任务的调度的,sched_sq模块只有两个文件,另一个los_sched.c就是调度代码。

涉及函数

鸿蒙内核进程和线程各有32个就绪队列,进程队列用全局变量存放, 创建进程时入队, 任务队列放在进程的threadPriQueueList中。

映射张大爷的故事:就绪队列就是在外面排队的32个通道,按优先级0-31依次排好,张大爷的办公室有个牌子,类似打篮球的记分牌,一共32个,一字排开,队列里有人时对应的牌就是1,没有就是0 ,这样张大爷每次从0位开始看,看到的第一个1那就是最高优先级的那个人。办公室里的记分牌就是位图调度器。

位图调度器

//* 0x80000000U = 10000000000000000000000000000000(32位,1是用于移位的,设计之精妙,点赞) 
#define PRIQUEUE_PRIOR0_BIT   0x80000000U 
LITE_OS_SEC_BSS LOS_DL_LIST *g_priQueueList = NULL; //所有的队列 原始指针
LITE_OS_SEC_BSS UINT32 g_priQueueBitmap; // 位图调度

整个los_priqueue.c就只有两个全部变量,一个是 LOS_DL_LIST *g_priQueueList 是32个进程就绪队列的头指针,在就绪队列中会讲另一个UINT32 g_priQueueBitmap  估计很多人会陌生,是一个32位的变量,叫位图调度器。怎么理解它呢?

鸿蒙系统的调度是抢占式的,task分成32个优先级,如何快速的知道哪个队列是空的,哪个队列里有任务需要一个标识,而且要极高效的实现?答案是:位图调度器。 系列篇已有专门讲位图管理的文章,自行翻看.简单说就是一个变量的位来标记对应队列中是否有任务,在位图调度下,任务优先级的值越小则代表具有越高的优先级,每当需要进行调度时,从最低位向最高位查找出第一个置 1 的位的所在位置,即为当前最高优先级,然后从对应优先级就绪队列获得相应的任务控制块,整个调度器的实现复杂度是 O(1),即无论任务多少,其调度时间是固定的。

进程就绪队列机制

CPU执行速度是很快的,其运算速度和内存的读写速度是数量级的差异,与硬盘的读写更是指数级。 鸿蒙内核默认一个时间片是 10ms,  资源很宝贵,它不断在众多任务中来回的切换,所以绝不能让CPU等待任务,CPU时间很宝贵,没准备好的任务不要放进来。这就是进程和线程就绪队列的机制,一共有32个任务就绪队列,因为线程的优先级是默认32个, 每个队列中放同等优先级的task. 队列初始化做了哪些工作?详细看代码

#define OS_PRIORITY_QUEUE_NUM 32

//内部队列初始化
UINT32 OsPriQueueInit(VOID)
{
    UINT32 priority;

    /* system resident resource *///常驻内存
    g_priQueueList = (LOS_DL_LIST *)LOS_MemAlloc(m_aucSysMem0, (OS_PRIORITY_QUEUE_NUM * sizeof(LOS_DL_LIST)));//分配32个队列头节点
    if (g_priQueueList == NULL) {
        return LOS_NOK;
    }

    for (priority = 0; priority < OS_PRIORITY_QUEUE_NUM; ++priority) {
        LOS_ListInit(&g_priQueueList[priority]);//队列初始化,前后指针指向自己
    }
    return LOS_OK;
}

因TASK 有32个优先级,在初始化时内核一次性创建了32个双向循环链表,每种优先级都有一个队列来记录就绪状态的tasks的位置,g_priQueueList分配的是一个连续的内存块,存放了32个双向链表

几个常用函数

还是看入队和出队的源码吧,注意bitmap的变化!

从代码中可以知道,调用了LOS_ListTailInsert,注意是从循环链表的尾部插入的,也就是同等优先级的TASK被排在了最后一个执行,只要每次都是从尾部插入,就形成了一个按顺序执行的队列。鸿蒙内核的设计可谓非常巧妙,用极少的代码,极高的效率实现了队列功能。

VOID OsPriQueueEnqueue(LOS_DL_LIST *priQueueList, UINT32 *bitMap, LOS_DL_LIST *priqueueItem, UINT32 priority)
{
    /*
     * Task control blocks are inited as zero. And when task is deleted,
     * and at the same time would be deleted from priority queue or
     * other lists, task pend node will restored as zero.
     */
    LOS_ASSERT(priqueueItem->pstNext == NULL);

    if (LOS_ListEmpty(&priQueueList[priority])) {
        *bitMap |= PRIQUEUE_PRIOR0_BIT >> priority;//对应优先级位 置1
    }

    LOS_ListTailInsert(&priQueueList[priority], priqueueItem);
}

VOID OsPriQueueEnqueueHead(LOS_DL_LIST *priQueueList, UINT32 *bitMap, LOS_DL_LIST *priqueueItem, UINT32 priority)
{
    /*
     * Task control blocks are inited as zero. And when task is deleted,
     * and at the same time would be deleted from priority queue or
     * other lists, task pend node will restored as zero.
     */
    LOS_ASSERT(priqueueItem->pstNext == NULL);

    if (LOS_ListEmpty(&priQueueList[priority])) {
        *bitMap |= PRIQUEUE_PRIOR0_BIT >> priority;//对应优先级位 置1
    }

    LOS_ListHeadInsert(&priQueueList[priority], priqueueItem);
}

VOID OsPriQueueDequeue(LOS_DL_LIST *priQueueList, UINT32 *bitMap, LOS_DL_LIST *priqueueItem)
{
    LosTaskCB *task = NULL;
    LOS_ListDelete(priqueueItem);

    task = LOS_DL_LIST_ENTRY(priqueueItem, LosTaskCB, pendList);
    if (LOS_ListEmpty(&priQueueList[task->priority])) {
        *bitMap &= ~(PRIQUEUE_PRIOR0_BIT >> task->priority);//队列空了,对应优先级位 置0
    }
}

同一个进程下的线程的优先级可以不一样吗?

请先想一下这个问题。

进程和线程是一对多的父子关系,内核调度的单元是任务(线程),鸿蒙内核中任务和线程是一个东西,只是不同的身份。一个进程可以有多个线程,线程又有各自独立的状态,那进程状态该怎么界定?例如:ProcessA 有 TaskA(阻塞状态) ,TaskB(就绪状态) 两个线程,ProcessA是属于阻塞状态还是就绪状态呢?

先看官方文档的说明后再看源码。

进程状态迁移说明:

  • Init→Ready:

    进程创建或fork时,拿到该进程控制块后进入Init状态,处于进程初始化阶段,当进程初始化完成将进程插入调度队列,此时进程进入就绪状态。

  • Ready→Running:

    进程创建后进入就绪态,发生进程切换时,就绪列表中最高优先级的进程被执行,从而进入运行态。若此时该进程中已无其它线程处于就绪态,则该进程从就绪列表删除,只处于运行态;若此时该进程中还有其它线程处于就绪态,则该进程依旧在就绪队列,此时进程的就绪态和运行态共存。

  • Running→Pend:

    进程内所有的线程均处于阻塞态时,进程在最后一个线程转为阻塞态时,同步进入阻塞态,然后发生进程切换。

  • Pend→Ready / Pend→Running:

    阻塞进程内的任意线程恢复就绪态时,进程被加入到就绪队列,同步转为就绪态,若此时发生进程切换,则进程状态由就绪态转为运行态。

  • Ready→Pend:

    进程内的最后一个就绪态线程处于阻塞态时,进程从就绪列表中删除,进程由就绪态转为阻塞态。

  • Running→Ready:

    进程由运行态转为就绪态的情况有以下两种:

    1. 有更高优先级的进程创建或者恢复后,会发生进程调度,此刻就绪列表中最高优先级进程变为运行态,那么原先运行的进程由运行态变为就绪态。
    2. 若进程的调度策略为SCHED_RR,且存在同一优先级的另一个进程处于就绪态,则该进程的时间片消耗光之后,该进程由运行态转为就绪态,另一个同优先级的进程由就绪态转为运行态。
  • Running→Zombies:

    当进程的主线程或所有线程运行结束后,进程由运行态转为僵尸态,等待父进程回收资源。

从文档中可知,一个进程是可以两种状态共存的.

    UINT16               processStatus;                /**< [15:4] process Status; [3:0] The number of threads currently
                                                            running in the process */

    processCB->processStatus &= ~(status | OS_PROCESS_STATUS_PEND);//取反后的与位运算
    processCB->processStatus |= OS_PROCESS_STATUS_READY;//或位运算

一个变量存两种状态,怎么做到的?答案还是 按位保存啊。还记得上面的位图调度 g_priQueueBitmap吗,那可是存了32种状态的。其实这在任何一个系统的内核源码中都很常见,类似的还有 左移 <<,右移 >>等等

继续说进程和线程的关系,线程的优先级必须和进程一样吗?他们可以不一样吗?答案是:当然不一样,否则怎么会有设置task优先级的函数。其实task有专门的bitmap来记录它曾经有过的优先级记录, 比如在调度过程中如果遇到阻塞,内核往往会提高持有锁的task的优先级,让它能以最大概率被下一轮调度选中而快速释放锁资源.

task调度器

真正让CPU工作的是task,进程只是个装task的容器,task有任务栈空间,进程结构体LosProcessCB 有一个这样的定义。看名字就知道了,那是跟调度相关的。

    UINT32               threadScheduleMap;            /**< The scheduling bitmap table for the thread group of the
                                                            process */
    LOS_DL_LIST          threadPriQueueList[OS_PRIORITY_QUEUE_NUM]; /**< The process's thread group schedules the
                                                                         priority hash table */

咋一看怎么进程的结构体里也有32个队列,其实这就是task的就绪状态队列。threadScheduleMap就是进程自己的位图调度器。具体看进程入队和出队的源码。调度过程是先去进程就绪队列里找最高优先级的进程,然后去该进程找最高优先级的线程来调度。具体看笔者认为的内核最美函数OsGetTopTask,能欣赏到他的美就读懂了就绪队列是怎么管理的。

LITE_OS_SEC_TEXT_MINOR LosTaskCB *OsGetTopTask(VOID)
{
    UINT32 priority, processPriority;
    UINT32 bitmap;
    UINT32 processBitmap;
    LosTaskCB *newTask = NULL;
#if (LOSCFG_KERNEL_SMP == YES)
    UINT32 cpuid = ArchCurrCpuid();
#endif
    LosProcessCB *processCB = NULL;
    processBitmap = g_priQueueBitmap;
    while (processBitmap) {
        processPriority = CLZ(processBitmap);
        LOS_DL_LIST_FOR_EACH_ENTRY(processCB, &g_priQueueList[processPriority], LosProcessCB, pendList) {
            bitmap = processCB->threadScheduleMap;
            while (bitmap) {
                priority = CLZ(bitmap);
                LOS_DL_LIST_FOR_EACH_ENTRY(newTask, &processCB->threadPriQueueList[priority], LosTaskCB, pendList) {
#if (LOSCFG_KERNEL_SMP == YES)
                    if (newTask->cpuAffiMask & (1U << cpuid)) {
#endif
                        newTask->taskStatus &= ~OS_TASK_STATUS_READY;
                        OsPriQueueDequeue(processCB->threadPriQueueList,
                                          &processCB->threadScheduleMap,
                                          &newTask->pendList);
                        OsDequeEmptySchedMap(processCB);
                        goto OUT;
#if (LOSCFG_KERNEL_SMP == YES)
                    }
#endif
                }
                bitmap &= ~(1U << (OS_PRIORITY_QUEUE_NUM - priority - 1));
            }
        }
        processBitmap &= ~(1U << (OS_PRIORITY_QUEUE_NUM - processPriority - 1));
    }

OUT:
    return newTask;
}

映射张大爷的故事:张大爷喊到张全蛋时进场时表演时,张全蛋要决定自己的哪个节目先表演,也要查下他的清单上优先级,它同样也有个张大爷同款记分牌,就这么简单。

百篇博客分析.深挖内核地基

  • 给鸿蒙内核源码加注释过程中,整理出以下文章。内容立足源码,常以生活场景打比方尽可能多的将内核知识点置入某种场景,具有画面感,容易理解记忆。说别人能听得懂的话很重要! 百篇博客绝不是百度教条式的在说一堆诘屈聱牙的概念,那没什么意思。更希望让内核变得栩栩如生,倍感亲切.确实有难度,自不量力,但已经出发,回头已是不可能的了。 😛
  • 与代码有bug需不断debug一样,文章和注解内容会存在不少错漏之处,请多包涵,但会反复修正,持续更新,v**.xx 代表文章序号和修改的次数,精雕细琢,言简意赅,力求打造精品内容。

按功能模块:

基础工具 加载运行 进程管理 编译构建
双向链表 位图管理 用栈方式 定时器 原子操作 时间管理 ELF格式 ELF解析 静态链接 重定位 进程映像 进程管理 进程概念 Fork 特殊进程 进程回收 信号生产 信号消费 Shell编辑 Shell解析 编译环境 编译过程 环境脚本 构建工具 gn应用 忍者ninja
进程通讯 内存管理 前因后果 任务管理
自旋锁 互斥锁 进程通讯 信号量 事件控制 消息队列 内存分配 内存管理 内存汇编 内存映射 内存规则 物理内存 总目录 调度故事 内存主奴 源码注释 源码结构 静态站点 时钟任务 任务调度 任务管理 调度队列 调度机制 线程概念 并发并行 CPU 系统调用 任务切换
文件系统 硬件架构
文件概念 文件系统 索引节点 挂载目录 根文件系统 字符设备 VFS 文件句柄 管道文件 汇编基础 汇编传参 工作模式 寄存器 异常接管 汇编汇总 中断切换 中断概念 中断管理

百万汉字注解.精读内核源码

WeHarmony/kernel_liteos_a_note

鸿蒙研究站 | 每天死磕一点点,原创不易,欢迎转载,但请注明出处。

展开阅读全文
加载中
点击加入讨论🔥(1) 发布并加入讨论🔥
打赏
1 评论
3 收藏
2
分享
返回顶部
顶部