為何單獨講調度隊列？

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

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

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

涉及函數

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

映射張大爺的故事：就緒隊列就是在外面排隊的32個通道，按優先級0-31依次排好，張大爺的辦公室有個牌子，類似打籃球的記分牌，一共32個，一字排開，隊列里有人時對應的牌就是1，沒有就是0 ，這樣張大爺每次從0位開始看，看到的第一個1那就是最高優先級的那個人。辦公室里的記分牌就是位圖調度器。

位圖調度器

//*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; // 位圖調度
// 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時間很寶貴，沒準備好的任務不要放進來。這就是進程和線程就緒隊列的機制，一共有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)));
    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：

進程由運行態轉為就緒態的情況有以下兩種：

有更高優先級的進程創建或者恢復后，會發生進程調度，此刻就緒列表中最高優先級進程變為運行態，那么原先運行的進程由運行態變為就緒態。

若進程的調度策略為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個隊列，其實這就是線程的就緒狀態隊列。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;
}