23_就绪队列篇

本篇关键词：、、、

下载 >> 离线文档.鸿蒙内核源码分析(百篇博客分析.挖透鸿蒙内核).pdf

任务管理相关篇为:

• v21.07 鸿蒙内核源码分析(任务控制块) | 内核最重要的概念
• v22.05 鸿蒙内核源码分析(并发并行) | 如何搞清楚它俩区分
• v23.03 鸿蒙内核源码分析(就绪队列) | 美好的事物永远值得等待
• v24.08 鸿蒙内核源码分析(调度机制) | 公平是相对的
• v25.05 鸿蒙内核源码分析(任务管理) | 如何管理任务池
• v26.03 鸿蒙内核源码分析(用栈方式) | 谁来提供程序运行场地
• v27.02 鸿蒙内核源码分析(软件定时器) | 内核最高级任务竟是它
• v28.01 鸿蒙内核源码分析(控制台) | 一个让很多人模糊的概念
• v29.01 鸿蒙内核源码分析(远程登录) | 内核如何接待远方的客人
• v30.01 鸿蒙内核源码分析(协议栈) | 正在制作中 ...

为何单独讲调度队列？

鸿蒙内核代码中有两个源文件是关于队列的，一个是用于调度的队列，另一个是用于线程间通讯的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;
}

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

百文说内核 | 抓住主脉络

• 百文相当于摸出内核的肌肉和器官系统，让人开始丰满有立体感，因是直接从注释源码起步，在加注释过程中，每每有心得处就整理,慢慢形成了以下文章。内容立足源码，常以生活场景打比方尽可能多的将内核知识点置入某种场景，具有画面感，容易理解记忆。说别人能听得懂的话很重要! 百篇博客绝不是百度教条式的在说一堆诘屈聱牙的概念，那没什么意思。更希望让内核变得栩栩如生，倍感亲切。
• 与代码需不断debug一样，文章内容会存在不少错漏之处，请多包涵，但会反复修正，持续更新，v**.xx 代表文章序号和修改的次数，精雕细琢，言简意赅，力求打造精品内容。
• 百文在 < 鸿蒙研究站 | 开源中国 | 博客园 | 51cto | csdn | 知乎 | 掘金 > 站点发布，百篇博客系列目录如下。
• 

按功能模块:

基础知识	进程管理	任务管理	内存管理
双向链表 内核概念 源码结构 地址空间 计时单位 优雅的宏 钩子框架 位图管理 POSIX main函数	调度故事 进程控制块 进程空间 线性区 红黑树 进程管理 Fork进程 进程回收 Shell编辑 Shell解析	任务控制块 并发并行 就绪队列 调度机制 任务管理 用栈方式 软件定时器 控制台 远程登录 协议栈	内存规则 物理内存 内存概念 虚实映射 页表管理 静态分配 TLFS算法 内存池管理 原子操作 圆整对齐
通讯机制	文件系统	硬件架构	内核汇编
通讯总览 自旋锁 互斥锁 快锁使用 快锁实现 读写锁 信号量 事件机制 信号生产 信号消费 消息队列 消息封装 消息映射 共享内存	文件概念 文件故事 索引节点 VFS 文件句柄 根文件系统 挂载机制 管道文件 文件映射 写时拷贝	芯片模式 ARM架构 指令集 协处理器 工作模式 寄存器 多核管理 中断概念 中断管理	编码方式 汇编基础 汇编传参 链接脚本 内核启动 进程切换 任务切换 中断切换 异常接管 缺页中断
编译运行	调测工具
编译过程 编译构建 GN语法 忍者无敌 ELF格式 ELF解析 静态链接 重定位 动态链接 进程映像 应用启动 系统调用 VDSO	模块监控 日志跟踪 系统安全 测试用例

百万注源码 | 处处扣细节

• 百万汉字注解内核目的是要看清楚其毛细血管，细胞结构，等于在拿放大镜看内核。内核并不神秘，带着问题去源码中找答案是很容易上瘾的，你会发现很多文章对一些问题的解读是错误的，或者说不深刻难以自圆其说，你会慢慢形成自己新的解读，而新的解读又会碰到新的问题，如此层层递进，滚滚向前，拿着放大镜根本不愿意放手。

• < gitee | github | coding | gitcode > 四大码仓推送 | 同步官方源码。

  

关注不迷路 | 代码即人生

期间不断得到小伙伴的支持，有学生，有职场新人，也有老江湖，在此一并感谢，大家的支持是前进的动力。尤其每次收到学生的赞助很感慨，后生可敬。 >> 查看捐助名单

据说喜欢 点赞 + 分享 的,后来都成了大神。:)