<sup id="ai8i2"><center id="ai8i2"></center></sup>
<rt id="ai8i2"><small id="ai8i2"></small></rt>

鴻蒙內核源碼分析(調度隊列篇)

調度隊列篇

提示:本文基于開源鴻蒙內核分析,官方源碼【kernel_liteos_a】官方文檔【docs】參考文檔【Huawei LiteOS
本文作者:鴻蒙內核發燒友,用生活場景講故事的方式去解構內核,一窺究竟,讓神秘的內核栩栩如生,浮現眼前。博文持續更新,敬請關注。內容僅代表個人觀點,錯誤之處,歡迎大家指正完善。本系列全部文章進入鴻蒙系統源碼分析(總目錄)查看


強烈建議先閱讀同系列姊妹篇?鴻蒙內核源碼分析(必讀篇)|用故事說內核|張大爺的故事

目錄

調度隊列篇

為何單獨講調度隊列?

涉及函數

位圖調度器

進程就緒隊列機制

幾個常用函數

同一個進程下的線程的優先級可以不一樣嗎?

線程調度器

為何單獨講調度隊列?

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

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

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

涉及函數

功能分類

接口名

描述

創建隊列

OsPriQueueInit

創建了32個就緒隊列

獲取最高優先級隊列

OsPriQueueTop

查最高優先級任務

從頭部入隊列

OsPriQueueEnqueueHead

從頭部插入某個就緒隊列

從尾部入隊列

OsPriQueueEnqueue

默認是從尾部插入某個就緒隊列

出隊列

OsPriQueueDequeue

從最高優先級的就緒隊列中刪除

?

OsPriQueueProcessDequeue

從進程隊列中刪除

?

OsPriQueueProcessSize

用進程查隊列中元素個數

?OsPriQueueSize用任務查隊列中元素個數

?

OsTaskPriQueueTop查最高優先級任務
?OsDequeEmptySchedMap進程出列
?OsGetTopTask獲取被調度選擇的task

鴻蒙內核進程和線程各有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:

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

    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工作的是線程,進程只是個裝線程的容器,線程有任務??臻g,是獨立運行于內核空間,而進程只有用戶空間,具體在后續的內存篇會講,這里不展開說,但進程結構體LosProcessCB?有一個這樣的定義??疵志椭懒?#xff0c;那是跟調度相關的。

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

映射張大爺的故事:張大爺喊到張全蛋時進場時表演時,張全蛋要決定自己的哪個節目先表演,也要查下他的清單上優先級,它同樣也有個張大爺同款記分牌,就這么簡單。?

全部系列文章進入鴻蒙系統源碼分析(總目錄)查看

??2020 CSDN 皮膚主題: 大白 設計師:CSDN官方博客 返回首頁
彩61彩票