本篇关键词:、、、

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

任务管理相关篇为:

为何单独讲调度队列?

鸿蒙内核代码中有两个源文件是关于队列的,一个是用于调度的队列,另一个是用于线程间通讯的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; // 位图调度
1
2
3
4

整个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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

因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
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

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

请先想一下这个问题。

进程和线程是一对多的父子关系,内核调度的单元是任务(线程),鸿蒙内核中任务和线程是一个东西,只是不同的身份。一个进程可以有多个线程,线程又有各自独立的状态,那进程状态该怎么界定?例如: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;//或位运算
1
2
3
4
5

一个变量存两种状态,怎么做到的?答案还是 按位保存啊。还记得上面的位图调度 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 */
1
2
3
4

咋一看怎么进程的结构体里也有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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

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

百文说内核 | 抓住主脉络

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

按功能模块:

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

百万注源码 | 处处扣细节

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

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

关注不迷路 | 代码即人生

  • 互联网从业十五年,计算机硕士,技术副总裁
  • 关注我,持续更新四十年,即聊技术也聊人生
  • 交有趣靠谱的人;做难而正确的事
  • 不做作,不炒作,只唯真
  • 不唯上,不唯书,只唯实

>> 捐助名单

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