开源鸿蒙内核源码分析系列 | 就绪队列 | 美好的事物永远值得等待(转载)

开源鸿蒙内核源码分析系列 | 就绪队列 | 美好的事物永远值得等待(转载)

为何单独讲调度队列?

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

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

涉及函数

功能分类接口名描述
创建队列OsPriQueueInit创建了32个就绪队列
获取最高优先级队列OSPriQueueTop查最高优先级任务
从头部入队列OsPriQueueEnqueueHead从头部插入某个就绪队列
从尾部入队列OsPriQueueEnqueue默认是从尾部插入某个就绪队列
出队列OsPriQueueDequeue从最高优先级的就绪队列中删除
OsPriQueueProcessDequeue从进程队列中删除
OsPriQueueProcessSize用进程查队列中元素个数
OsPriQueueSize用任务查队列中元素个数
OsTaskPriQueueTop查最高优先级任务
OSDequeEmptySchedMap进程出列
OsGetTopTask获取被调度选择的任务

开源鸿蒙内核进程和线程各有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),即无论任务多少,其调度时间是固定的。

进程就绪队列机制

爱德华·伯恩·琼斯的《黄金阶梯》(局部)1880

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:

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

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


VOID            *taskSem;           /**< Task-held semaphore */ //task在等哪个信号量
VOID            *taskMux;           /**< Task-held mutex */  //task在等哪把锁
VOID            *taskEvent;         /**< Task-held event */  //task在等哪个事件
UINT32          eventMask;          /**< Event mask */   //事件屏蔽
UINT32          eventMode;          /**< Event mode */   //事件模式
FutexNode       futex;    //实现快锁功能
LOS_DL_LIST     joinList;           /**< join list */ //联结链表,允许任务之间相互释放彼此
LOS_DL_LIST     lockList;           /**< Hold the lock list */ //拿到了哪些锁链表
UINT32          signal;             /**< Task signal */ //任务信号类型,(SIGNAL_NONE,SIGNAL_KILL,SIGNAL_SUSPEND,SIGNAL_AFFI)
sig_cb          sig;

一个变量存两种状态,怎么做到的?答案还是 按位保存啊。还记得上面的位图调度 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 代表文章序号和修改的次数,精雕细琢,言简意赅,力求打造精品内容。百篇博客系列思维导图结构如下:

根据上图的思维导图,我们未来将要和大家一一分享以上大部分关键技术点的博客文章。

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

如果大家觉得看文章不过瘾,想直接撸代码的话,可以去下面四大码仓围观同步注释内核源码:

gitee仓

https://gitee.com/weharmony/kernel_liteos_a_note

github仓 :

https://github.com/kuangyufei/kernel_liteos_a_note

codechina仓

https://codechina.csdn.net/kuangyufei/kernel_liteos_a_note

coding仓

https://weharmony.coding.net/public/harmony/kernel_liteos_a_note/git/files

写在最后

我们最近正带着大家玩嗨OpenHarmony。如果你有用OpenHarmony开发的好玩的东东,或者有对OpenHarmony的深度技术剖析,想通过我们平台让更多的小伙伴知道和分享的,欢迎投稿,让我们一起嗨起来!有点子,有想法,有Demo,立刻联系我们:

合作邮箱:zzliang@atomsource.org