鸿蒙内核源码分析(调度队列篇) | 为什么只有就绪状态才有队列 ? | 百篇博客分析HarmonyOS源码 | v6.04
为何单独讲调度队列?
鸿蒙内核代码中有两个源文件是关于队列的,一个是用于调度的队列,另一个是用于线程间通讯的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:
进程由运行态转为就绪态的情况有以下两种:
有更高优先级的进程创建或者恢复后,会发生进程调度,此刻就绪列表中最高优先级进程变为运行态,那么原先运行的进程由运行态变为就绪态。
若进程的调度策略为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; }
登录后复制
映射张大爷的故事:张大爷喊到张全蛋时进场时表演时,张全蛋要决定自己的哪个节目先表演,也要查下他的清单上优先级,它同样也有个张大爷同款记分牌,就这么简单。
鸿蒙源码百篇博客 往期回顾
v44.03 (中断管理篇) | 硬中断的实现<>观察者模式 < csdn | harmony | 掘金 >
v43.03 (中断概念篇) | 外人眼中权势滔天的当红海公公 < csdn | harmony | 掘金 >
v42.03 (中断切换篇) | 中断切换在切换什么? < csdn | harmony | 掘金 >
v41.03 (任务切换篇) | 汇编逐行注解分析任务上下文 < csdn | harmony | 掘金 >
v40.03 (汇编汇总篇) | 所有的汇编代码都在这里 < csdn | harmony | 掘金 >
v39.03 (异常接管篇) | 社会很单纯,复杂的是人 < csdn | harmony | 掘金 >
v38.03 (寄存器篇) | ARM所有寄存器一网打尽,不再神秘 < csdn | harmony | 掘金 >
v37.03 (系统调用篇) | 全盘解剖系统调用实现过程 < csdn | harmony | 掘金 >
v36.03 (工作模式篇) | CPU是韦小宝,有哪七个老婆? < csdn | harmony | 掘金 >
v35.03 (时间管理篇) | Tick是操作系统的基本时间单位 < csdn | harmony | 掘金 >
v34.03 (原子操作篇) | 是谁在为原子操作保驾护航? < csdn | harmony | 掘金 >
v33.03 (消息队列篇) | 进程间如何异步解耦传递大数据 ? < csdn | harmony | 掘金 >
v32.03 (CPU篇) | 内核是如何描述CPU的? < csdn | harmony | 掘金 >
v31.03 (定时器篇) | 内核最高优先级任务是谁? < csdn | harmony | 掘金 >
v30.03 (事件控制篇) | 任务间多对多的同步方案 < csdn | harmony | 掘金 >
v29.03 (信号量篇) | 信号量解决任务同步问题 < csdn | harmony | 掘金 >
v28.03 (进程通讯篇) | 进程间通讯有哪九大方式? < csdn | harmony | 掘金 >
v27.03 (互斥锁篇) | 互斥锁比自旋锁可丰满许多 < csdn | harmony | 掘金 >
v26.03 (自旋锁篇) | 想为自旋锁立贞节牌坊! < csdn | harmony | 掘金 >
v25.03 (并发并行篇) | 怎么记住并发并行的区别? < csdn | harmony | 掘金 >
v24.03 (进程概念篇) | 进程在管理哪些资源? < csdn | harmony | 掘金 >
v23.02 (汇编传参篇) | 汇编如何传递复杂的参数? < csdn | harmony | 掘金 >
v22.02 (汇编基础篇) | CPU在哪里打卡上班? < csdn | harmony | 掘金 >
v21.02 (线程概念篇) | 是谁在不断的折腾CPU? < csdn | harmony | 掘金 >
v20.02 (用栈方式篇) | 栈是构建底层运行的基础 < csdn | harmony | 掘金 >
v19.02 (位图管理篇) | 为何进程和线程优先级都是32个? < csdn | harmony | 掘金 >
v18.02 (源码结构篇) | 内核500问你能答对多少? < csdn | harmony | 掘金 >
v17.02 (物理内存篇) | 这样记伙伴算法永远不会忘 < csdn | harmony | 掘金 >
v16.02 (内存规则篇) | 内存管理到底在管什么? < csdn | harmony | 掘金 >
v15.02 (内存映射篇) | 什么是内存最重要的实现基础 ? < csdn | harmony | 掘金 >
v14.02 (内存汇编篇) | 什么是虚拟内存的实现基础? < csdn | harmony | 掘金 >
v13.02 (源码注释篇) | 热爱是所有的理由和答案 < csdn | harmony | 掘金 >
v12.02 (内存管理篇) | 虚拟内存全景图是怎样的? < csdn | harmony | 掘金 >
v11.02 (内存分配篇) | 内存有哪些分配方式? < csdn | harmony | 掘金 >
v10.02 (内存主奴篇) | 紫禁城的主子和奴才如何相处? < csdn | harmony | 掘金 >
v09.02 (调度故事篇) | 用故事说内核调度 < csdn | harmony | 掘金 >
v08.02 (总目录) | 百万汉字注解 百篇博客分析 < csdn | harmony | 掘金 >
v07.02 (调度机制篇) | 任务是如何被调度执行的? < csdn | harmony | 掘金 >
v06.02 (调度队列篇) | 就绪队列对调度的作用 < csdn | harmony | 掘金 >
v05.02 (任务管理篇) | 谁在让CPU忙忙碌碌? < csdn | harmony | 掘金 >
v04.02 (任务调度篇) | 任务是内核调度的单元 < csdn | harmony | 掘金 >
v03.02 (时钟任务篇) | 触发调度最大的动力来自哪里? < csdn | harmony | 掘金 >
v02.02 (进程管理篇) | 进程是内核资源管理单元 < csdn | harmony | 掘金 >
v01.09 (双向链表篇) | 谁是内核最重要结构体? < csdn | harmony | 掘金 >