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

為何單獨講調(diào)度隊列？

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

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

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

涉及函數(shù)

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

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

位圖調(diào)度器

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

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

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

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

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

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

進程就緒隊列機制

CPU執(zhí)行速度是很快的，其運算速度和內(nèi)存的讀寫速度是數(shù)量級的差異，與硬盤的讀寫更是指數(shù)級。鴻蒙內(nèi)核默認一個時間片是 10ms,資源很寶貴，它不斷在眾多任務中來回的切換，所以絕不能讓CPU等待任務，CPU時間很寶貴，沒準備好的任務不要放進來。這就是進程和線程就緒隊列的機制，一共有32個任務就緒隊列，因為線程的優(yōu)先級是默認32個， 每個隊列中放同等優(yōu)先級的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)));
    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個優(yōu)先級，在初始化時內(nèi)核一次性創(chuàng)建了32個雙向循環(huán)鏈表，每種優(yōu)先級都有一個隊列來記錄就緒狀態(tài)的tasks的位置，g_priQueueList分配的是一個連續(xù)的內(nèi)存塊，存放了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;

幾個常用函數(shù)

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

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

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

同一個進程下的線程的優(yōu)先級可以不一樣嗎？

請先想一下這個問題。

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

先看官方文檔的說明后再看源碼。

進程狀態(tài)遷移說明：

Init→Ready：

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

Ready→Running：

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

Running→Pend：

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

Pend→Ready / Pend→Running：

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

Ready→Pend：

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

Running→Ready：

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

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

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

Running→Zombies：

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

注意看上面紅色的部分，一個進程竟然可以兩種狀態(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);//取反后的與位運算
    processCB->processStatus |= OS_PROCESS_STATUS_READY;//或位運算

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

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

線程調(diào)度器

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

    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個隊列，其實這就是線程的就緒狀態(tài)隊列。threadScheduleMap就是進程自己的位圖調(diào)度器。具體看進程入隊和出隊的源碼。調(diào)度過程是先去進程就緒隊列里找最高優(yōu)先級的進程，然后去該進程找最高優(yōu)先級的線程來調(diào)度。具體看筆者認為的內(nèi)核最美函數(shù)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;
}