淺談鴻蒙內(nèi)核代碼調(diào)度隊(duì)列

為何單獨(dú)講調(diào)度隊(duì)列？

鴻蒙內(nèi)核代碼中有兩個(gè)源文件是關(guān)于隊(duì)列的，一個(gè)是用于調(diào)度的隊(duì)列，另一個(gè)是用于線程間通訊的IPC隊(duì)列。

本文詳細(xì)講述調(diào)度隊(duì)列，詳見(jiàn)代碼: kernel_liteos_a/kernel/base/sched/sched_sq/los_priqueue.c

IPC隊(duì)列后續(xù)有專門(mén)的博文講述，這兩個(gè)隊(duì)列的數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)采用的都是雙向循環(huán)鏈表，LOS_DL_LIST實(shí)在是太重要了，是理解鴻蒙內(nèi)核的關(guān)鍵，說(shuō)是最重要的代碼一點(diǎn)也不為過(guò)，源碼出現(xiàn)在 sched_sq模塊，說(shuō)明是用于任務(wù)的調(diào)度的，sched_sq模塊只有兩個(gè)文件，另一個(gè)los_sched.c就是調(diào)度代碼。

涉及函數(shù)

鴻蒙內(nèi)核進(jìn)程和線程各有32個(gè)就緒隊(duì)列，進(jìn)程隊(duì)列用全局變量存放，創(chuàng)建進(jìn)程時(shí)入隊(duì)，任務(wù)隊(duì)列放在進(jìn)程的threadPriQueueList中。

映射張大爺?shù)墓适拢壕途w隊(duì)列就是在外面排隊(duì)的32個(gè)通道，按優(yōu)先級(jí)0-31依次排好，張大爺?shù)霓k公室有個(gè)牌子，類似打籃球的記分牌，一共32個(gè)，一字排開(kāi)，隊(duì)列里有人時(shí)對(duì)應(yīng)的牌就是1，沒(méi)有就是0 ，這樣張大爺每次從0位開(kāi)始看，看到的第一個(gè)1那就是最高優(yōu)先級(jí)的那個(gè)人。辦公室里的記分牌就是位圖調(diào)度器。

位圖調(diào)度器

//*kfy 0x80000000U = 10000000000000000000000000000000(32位,1是用于移位的，設(shè)計(jì)之精妙，點(diǎn)贊) 
#define PRIQUEUE_PRIOR0_BIT   0x80000000U 

#ifndef CLZ
#define CLZ(value)                                  (__clz(value)) //匯編指令
#endif

LITE_OS_SEC_BSS LOS_DL_LIST *g_priQueueList = NULL; //所有的隊(duì)列 原始指針
LITE_OS_SEC_BSS UINT32 g_priQueueBitmap; // 位圖調(diào)度
// priority = CLZ(bitmap); // 獲取最高優(yōu)先級(jí)任務(wù)隊(duì)列 調(diào)度位

整個(gè)los_priqueue.c就只有兩個(gè)全部變量，一個(gè)是LOS_DL_LIST *g_priQueueList是32個(gè)進(jìn)程就緒隊(duì)列的頭指針，在就緒隊(duì)列中會(huì)講另一個(gè)UINT32 g_priQueueBitmap 估計(jì)很多人會(huì)陌生，是一個(gè)32位的變量，叫位圖調(diào)度器。怎么理解它呢？

鴻蒙系統(tǒng)的調(diào)度是搶占式的，task分成32個(gè)優(yōu)先級(jí)，如何快速的知道哪個(gè)隊(duì)列是空的，哪個(gè)隊(duì)列里有任務(wù)需要一個(gè)標(biāo)識(shí)，而且要極高效的實(shí)現(xiàn)？答案是:位圖調(diào)度器。

簡(jiǎn)單說(shuō)就是一個(gè)變量的位來(lái)標(biāo)記對(duì)應(yīng)隊(duì)列中是否有任務(wù)，在位圖調(diào)度下,任務(wù)優(yōu)先級(jí)的值越小則代表具有越高的優(yōu)先級(jí)，每當(dāng)需要進(jìn)行調(diào)度時(shí),從最低位向最高位查找出第一個(gè)置 1 的位的所在位置,即為當(dāng)前最高優(yōu)先級(jí),然后從對(duì)應(yīng)優(yōu)先級(jí)就緒隊(duì)列獲得相應(yīng)的任務(wù)控制塊,整個(gè)調(diào)度器的實(shí)現(xiàn)復(fù)雜度是 O(1),即無(wú)論任務(wù)多少,其調(diào)度時(shí)間是固定的。

進(jìn)程就緒隊(duì)列機(jī)制

CPU執(zhí)行速度是很快的，其運(yùn)算速度和內(nèi)存的讀寫(xiě)速度是數(shù)量級(jí)的差異，與硬盤(pán)的讀寫(xiě)更是指數(shù)級(jí)。鴻蒙內(nèi)核默認(rèn)一個(gè)時(shí)間片是 10ms,資源很寶貴，它不斷在眾多任務(wù)中來(lái)回的切換，所以絕不能讓CPU等待任務(wù)，CPU時(shí)間很寶貴，沒(méi)準(zhǔn)備好的任務(wù)不要放進(jìn)來(lái)。這就是進(jìn)程和線程就緒隊(duì)列的機(jī)制，一共有32個(gè)任務(wù)就緒隊(duì)列，因?yàn)榫€程的優(yōu)先級(jí)是默認(rèn)32個(gè)， 每個(gè)隊(duì)列中放同等優(yōu)先級(jí)的task.

隊(duì)列初始化做了哪些工作？詳細(xì)看代碼

#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)));
    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個(gè)優(yōu)先級(jí)，在初始化時(shí)內(nèi)核一次性創(chuàng)建了32個(gè)雙向循環(huán)鏈表，每種優(yōu)先級(jí)都有一個(gè)隊(duì)列來(lái)記錄就緒狀態(tài)的tasks的位置，g_priQueueList分配的是一個(gè)連續(xù)的內(nèi)存塊，存放了32個(gè)LOS_DL_LIST，再看一下LOS_DL_LIST結(jié)構(gòu)體，因?yàn)樗匾?！越?jiǎn)單越靈活

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;

幾個(gè)常用函數(shù)

還是看入隊(duì)和出隊(duì)的源碼吧，注意bitmap的變化！

從代碼中可以知道，調(diào)用了LOS_ListTailInsert(&priQueueList[priority], priqueueItem); 注意是從循環(huán)鏈表的尾部插入的，也就是同等優(yōu)先級(jí)的TASK被排在了最后一個(gè)執(zhí)行，只要每次都是從尾部插入，就形成了一個(gè)按順序執(zhí)行的隊(duì)列。鴻蒙內(nèi)核的設(shè)計(jì)可謂非常巧妙，用極少的代碼，極高的效率實(shí)現(xiàn)了隊(duì)列功能。

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;//對(duì)應(yīng)優(yōu)先級(jí)位 置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;//對(duì)應(yīng)優(yōu)先級(jí)位 置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);//隊(duì)列空了，對(duì)應(yīng)優(yōu)先級(jí)位 置0
    }
}

同一個(gè)進(jìn)程下的線程的優(yōu)先級(jí)可以不一樣嗎？

請(qǐng)先想一下這個(gè)問(wèn)題。

進(jìn)程和線程是一對(duì)多的父子關(guān)系，內(nèi)核調(diào)度的單元是任務(wù)(線程)，鴻蒙內(nèi)核中任務(wù)和線程是一個(gè)東西，只是不同的身份。一個(gè)進(jìn)程可以有多個(gè)線程，線程又有各自獨(dú)立的狀態(tài)，那進(jìn)程狀態(tài)該怎么界定？例如：ProcessA有 TaskA(阻塞狀態(tài))，TaskB(就緒狀態(tài)) 兩個(gè)線程，ProcessA是屬于阻塞狀態(tài)還是就緒狀態(tài)呢？

先看官方文檔的說(shuō)明后再看源碼。

進(jìn)程狀態(tài)遷移說(shuō)明：

Init→Ready：

進(jìn)程創(chuàng)建或fork時(shí)，拿到該進(jìn)程控制塊后進(jìn)入Init狀態(tài)，處于進(jìn)程初始化階段，當(dāng)進(jìn)程初始化完成將進(jìn)程插入調(diào)度隊(duì)列，此時(shí)進(jìn)程進(jìn)入就緒狀態(tài)。

Ready→Running：

進(jìn)程創(chuàng)建后進(jìn)入就緒態(tài)，發(fā)生進(jìn)程切換時(shí)，就緒列表中最高優(yōu)先級(jí)的進(jìn)程被執(zhí)行，從而進(jìn)入運(yùn)行態(tài)。若此時(shí)該進(jìn)程中已無(wú)其它線程處于就緒態(tài)，則該進(jìn)程從就緒列表刪除，只處于運(yùn)行態(tài)；若此時(shí)該進(jìn)程中還有其它線程處于就緒態(tài)，則該進(jìn)程依舊在就緒隊(duì)列，此時(shí)進(jìn)程的就緒態(tài)和運(yùn)行態(tài)共存。

Running→Pend：

進(jìn)程內(nèi)所有的線程均處于阻塞態(tài)時(shí)，進(jìn)程在最后一個(gè)線程轉(zhuǎn)為阻塞態(tài)時(shí)，同步進(jìn)入阻塞態(tài)，然后發(fā)生進(jìn)程切換。

Pend→Ready / Pend→Running：

阻塞進(jìn)程內(nèi)的任意線程恢復(fù)就緒態(tài)時(shí)，進(jìn)程被加入到就緒隊(duì)列，同步轉(zhuǎn)為就緒態(tài)，若此時(shí)發(fā)生進(jìn)程切換，則進(jìn)程狀態(tài)由就緒態(tài)轉(zhuǎn)為運(yùn)行態(tài)。

Ready→Pend：

進(jìn)程內(nèi)的最后一個(gè)就緒態(tài)線程處于阻塞態(tài)時(shí)，進(jìn)程從就緒列表中刪除，進(jìn)程由就緒態(tài)轉(zhuǎn)為阻塞態(tài)。

Running→Ready：

進(jìn)程由運(yùn)行態(tài)轉(zhuǎn)為就緒態(tài)的情況有以下兩種：

有更高優(yōu)先級(jí)的進(jìn)程創(chuàng)建或者恢復(fù)后，會(huì)發(fā)生進(jìn)程調(diào)度，此刻就緒列表中最高優(yōu)先級(jí)進(jìn)程變?yōu)檫\(yùn)行態(tài)，那么原先運(yùn)行的進(jìn)程由運(yùn)行態(tài)變?yōu)榫途w態(tài)。

若進(jìn)程的調(diào)度策略為SCHED_RR，且存在同一優(yōu)先級(jí)的另一個(gè)進(jìn)程處于就緒態(tài)，則該進(jìn)程的時(shí)間片消耗光之后，該進(jìn)程由運(yùn)行態(tài)轉(zhuǎn)為就緒態(tài)，另一個(gè)同優(yōu)先級(jí)的進(jìn)程由就緒態(tài)轉(zhuǎn)為運(yùn)行態(tài)。

Running→Zombies：

當(dāng)進(jìn)程的主線程或所有線程運(yùn)行結(jié)束后，進(jìn)程由運(yùn)行態(tài)轉(zhuǎn)為僵尸態(tài)，等待父進(jìn)程回收資源。

注意看上面紅色的部分，一個(gè)進(jìn)程竟然可以兩種狀態(tài)共存！

UINT16 processStatus; /**< [15:4] process Status; [3:0] The number of threads currently

                                                            running in the process */

    processCB->processStatus &= ~(status | OS_PROCESS_STATUS_PEND);//取反后的與位運(yùn)算
    processCB->processStatus |= OS_PROCESS_STATUS_READY;//或位運(yùn)算

一個(gè)變量存兩種狀態(tài)，怎么做到的？答案還是按位保存啊。還記得上面的位圖調(diào)度g_priQueueBitmap嗎，那可是存了32種狀態(tài)的。其實(shí)這在任何一個(gè)系統(tǒng)的內(nèi)核源碼中都很常見(jiàn)，類似的還有左移 <<，右移 >>等等

繼續(xù)說(shuō)進(jìn)程和線程的關(guān)系，線程的優(yōu)先級(jí)必須和進(jìn)程一樣嗎？他們可以不一樣嗎？答案是：可以不一樣，否則怎么會(huì)有設(shè)置task優(yōu)先級(jí)的函數(shù)。

線程調(diào)度器

真正讓CPU工作的是線程，進(jìn)程只是個(gè)裝線程的容器，線程有任務(wù)?？臻g，是獨(dú)立運(yùn)行于內(nèi)核空間，而進(jìn)程只有用戶空間，具體在后續(xù)的內(nèi)存篇會(huì)講，這里不展開(kāi)說(shuō)，但進(jìn)程結(jié)構(gòu)體LosProcessCB有一個(gè)這樣的定義?？疵志椭懒耍鞘歉{(diào)度相關(guān)的。

    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 */

咋一看怎么進(jìn)程的結(jié)構(gòu)體里也有32個(gè)隊(duì)列，其實(shí)這就是線程的就緒狀態(tài)隊(duì)列。threadScheduleMap就是進(jìn)程自己的位圖調(diào)度器。具體看進(jìn)程入隊(duì)和出隊(duì)的源碼。調(diào)度過(guò)程是先去進(jìn)程就緒隊(duì)列里找最高優(yōu)先級(jí)的進(jìn)程，然后去該進(jìn)程找最高優(yōu)先級(jí)的線程來(lái)調(diào)度。具體看筆者認(rèn)為的內(nèi)核最美函數(shù)OsGetTopTask，能欣賞到他的美就讀懂了就緒隊(duì)列是怎么管理的。

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;
}