调度队列的作用

anonymous 转载编程分享 2020-09-20 22:52:04

简介调度队列篇 ...

调度队列篇

提示：本文基于开源鸿蒙内核分析，详细进入kernel_liteos_a查看源码。
本文作者：鸿蒙内核发烧友，将持续研究鸿蒙内核，更新博文，敬请关注。内容仅代表个人观点，错误之处，欢迎大家指正完善。

调度队列篇

调度队列的作用

涉及函数列表

调度队列的作用

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

本文详细讲述调度队列，详见代码: kernel_liteos_a/kernel/base/sched/sched_sq/los_priqueue.c

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

为何要单独讲调度队列？因为队列是调度的前置仓，如果把task比喻成粮食，那队列就是装粮食的仓库，调度算法就是运粮食的人，粮食和搬运的人固然很重要，但仓库也很重要，他们为调度提供了任务的来源，任务从哪里来，又去了哪里都是由这些队列所承载的逻辑来完成的。建议先看鸿蒙内核源码分析(Task/线程管理篇)，以便于更好的理解调度队列。

涉及函数

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

位图调度器

//*kfy 0x80000000U = 10000000000000000000000000000000(32位,1是用于移位的，设计之精妙，点赞) 
Iddefine PRIQUEUE_PRIOR0_BIT   0x80000000U 

Idifndef CLZ
Iddefine CLZ(value)                                  (__clz(value)) //汇编指令
Idendif

LITE_OS_SEC_BSS LOS_DL_LIST *g_priQueueList = NULL; //所有的队列 原始指针
LITE_OS_SEC_BSS UINT32 g_priQueueBitmap; // 位图调度
// priority = CLZ(bitmap); // 获取最高优先级任务队列 调度位

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

鸿蒙系统的调度是抢占式的，task分成32个优先级，如何快速的知道哪个队列是空的，哪个队列里有任务需要一个标识，而且要极高效的实现？答案是:位图调度器。

简单说就是一个变量的位来标记对应队列中是否有任务，在位图调度下,任务优先级的值越小则代表具有越高的优先级，每当需要进行调度时,从最低位向最高位查找出第一个置 1 的位的所在位置,即为当前最高优先级,然后从对应优先级就绪队列获得相应的任务控制块,整个调度器的实现复杂度是 O(1),即无论任务多少,其调度时间是固定的。具体的调度实现因涉及到汇编指令，将在鸿蒙内核源码分析(任务调度篇) 中分析

任务就绪队列机制

CPU执行速度是很快的，其运算速度和内存的读写速度是数量级的差异，与硬盘的读写更是指数级。鸿蒙内核默认一个时间片是 10ms, 资源很宝贵，它不断在众多任务中来回的切换，所以绝不能让CPU等待任务，CPU就像公司大boss，下面很多的部门等boss来审批，吃饭。只有大家等领导，哪有领导等你们的道理，所以工作要提前准备好，每个部门工作的优先级又不一样，所以有对应优先级的任务队列，里面放的全是领导能直接处理的任务，没准备好的不要放进来。
这就是任务就绪队列的机制，一共有32个任务就绪队列，因为线程的优先级是默认32个，每个队列中放同等优先级的task.

队列初始化做了哪些工作？详细看代码

Iddefine 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)));
    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个LOS_DL_LIST，再看一下LOS_DL_LIST结构体，因为它太重要了！越简单越灵活

typedef struct LOS_DL_LIST {
    struct LOS_DL_LIST *pstPrev; /**< Current node's pointer to the previous node */
    struct LOS_DL_LIST *pstNext; /**< Current node's pointer to the next node */
} LOS_DL_LIST;

几个常用函数

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

从代码中可以知道，调用了LOS_ListTailInsert(&priQueueList[priority], priqueueItem); 注意是从循环链表的尾部插入的，也就是同等优先级的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优先级的函数。

怎么理解线程组？

真正让CPU工作的是线程，进程只是个装线程的容器，线程有任务栈空间，是独立运行于内核空间或用户空间，而进程是没有的，但进程结构体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个队列，其实属于进程自己就绪状态队列，本质上还是上面说的任务就绪队列，只不过管理方便从进程层面也可以方便的读取就绪队列。

举个例子说明下：A，B，C 三个公司各派年龄必须是18岁的 3个, 4个, 5个一共13人玩一个手拉手围成一个大圈圈的活动。

其中的 A,B,C 代表了进程，18岁代表了任务优先级， 3,4,5 代表线程数，围成的大圈圈就是一个优先级为 18的就绪队列。

而对于A进程来说，它自己记录一份公司3个18岁小伙伴参加了活动。

而对于B进程来说，它自己记录一份公司4个18岁小伙伴参加了活动。

而对于C进程来说，它自己记录一份公司5个18岁小伙伴参加了活动。

threadPriQueueList[OS_PRIORITY_QUEUE_NUM] 就是它自己用来记录从 0 - 31岁员工的人数的线程组，组长就是入队的第一个taskID

threadScheduleMap就是进程自己的位图调度器。

具体看进程入队和出队的源码。

STATIC INLINE VOID OsSchedTaskEnqueue(LosProcessCB *processCB, LosTaskCB *taskCB)
{
    if (((taskCB->policy == LOS_SCHED_RR) && (taskCB->timeSlice != 0)) ||
        ((taskCB->taskStatus & OS_TASK_STATUS_RUNNING) && (taskCB->policy == LOS_SCHED_FIFO))) {
        OS_TASK_PRI_QUEUE_ENQUEUE_HEAD(processCB, taskCB);
    } else {
        OS_TASK_PRI_QUEUE_ENQUEUE(processCB, taskCB);
    }
    taskCB->taskStatus |= OS_TASK_STATUS_READY;//已进入就绪队列,改变task状态
}

//*kyf 被调度的任务入队
LITE_OS_SEC_TEXT_INIT VOID OsTaskSchedQueueEnqueue(LosTaskCB *taskCB, UINT16 status)
{
    LosProcessCB *processCB = NULL;

    LOS_ASSERT(!(taskCB->taskStatus & OS_TASK_STATUS_READY));//只有非就绪状态任务才能入队

    processCB = OS_PCB_FROM_PID(taskCB->processID);
    if (!(processCB->processStatus & OS_PROCESS_STATUS_READY)) {
        if (((processCB->policy == LOS_SCHED_RR) && (processCB->timeSlice != 0)) ||
            ((processCB->processStatus & OS_PROCESS_STATUS_RUNNING) && (processCB->policy == LOS_SCHED_FIFO))) {
            OS_PROCESS_PRI_QUEUE_ENQUEUE_HEAD(processCB);
        } else {
            OS_PROCESS_PRI_QUEUE_ENQUEUE(processCB);
        }
        processCB->processStatus &= ~(status | OS_PROCESS_STATUS_PEND);
        processCB->processStatus |= OS_PROCESS_STATUS_READY;
    } else {
        LOS_ASSERT(!(processCB->processStatus & OS_PROCESS_STATUS_PEND));
        LOS_ASSERT((UINTPTR)processCB->pendList.pstNext);
        if ((processCB->timeSlice == 0) && (processCB->policy == LOS_SCHED_RR)) {
            OS_PROCESS_PRI_QUEUE_DEQUEUE(processCB);
            OS_PROCESS_PRI_QUEUE_ENQUEUE(processCB);
        }
    }

    OsSchedTaskEnqueue(processCB, taskCB);
}

//进程出列
VOID OsPriQueueProcessDequeue(LOS_DL_LIST *priqueueItem)
{
    LosProcessCB *runProcess = NULL;
    LOS_ListDelete(priqueueItem);

    runProcess = LOS_DL_LIST_ENTRY(priqueueItem, LosProcessCB, pendList);
    if (LOS_ListEmpty(&g_priQueueList[runProcess->priority])) {
        g_priQueueBitmap &= ~(PRIQUEUE_PRIOR0_BIT >> runProcess->priority);//队列空了，对应优先级位 置0
    }
}