[[398858]]

想了解更多內(nèi)容，請?jiān)L問：

51CTO和華為官方合作共建的鴻蒙技術(shù)社區(qū)

https://harmonyos.51cto.com

鴻蒙輕內(nèi)核源碼分析上一個(gè)系列，我們分析了雙向循環(huán)鏈表的源碼。本文會(huì)繼續(xù)給讀者介紹源碼中重要的數(shù)據(jù)結(jié)構(gòu)，任務(wù)基于優(yōu)先級的就緒隊(duì)列Priority Queue。在講解時(shí)，會(huì)結(jié)合數(shù)據(jù)結(jié)構(gòu)相關(guān)繪圖，培養(yǎng)讀者們的數(shù)據(jù)結(jié)構(gòu)的平面想象能力，幫助更好的學(xué)習(xí)和理解這些數(shù)據(jù)結(jié)構(gòu)的用法。

1 任務(wù)就緒隊(duì)列

在任務(wù)調(diào)度模塊，就緒隊(duì)列是個(gè)重要的數(shù)據(jù)結(jié)構(gòu)。任務(wù)創(chuàng)建后即進(jìn)入就緒態(tài)，并放入就緒隊(duì)列。在鴻蒙輕內(nèi)核中，就緒隊(duì)列是一個(gè)雙向循環(huán)鏈表數(shù)組，每個(gè)數(shù)組元素就是一個(gè)鏈表，相同優(yōu)先級的任務(wù)放入同一個(gè)鏈表。

任務(wù)就緒隊(duì)列Priority Queue主要供內(nèi)部使用，用戶進(jìn)行業(yè)務(wù)開發(fā)時(shí)不涉及，所以并未對外提供接口。雙向循環(huán)鏈表數(shù)組能夠更加方便的支持任務(wù)基于優(yōu)先級進(jìn)行調(diào)度。任務(wù)就緒隊(duì)列的核心代碼在kernel\src\los_task.c文件中。

1.1 任務(wù)就緒隊(duì)列的定義

在kernel\src\los_task.c文件中定義了和任務(wù)就緒隊(duì)列相關(guān)的主要變量。

源碼如下：

⑴ LITE_OS_SEC_BSS LOS_DL_LIST *g_losPriorityQueueList = NULL; 
 
⑵ static LITE_OS_SEC_BSS UINT32 g_priqueueBitmap = 0; 
 
⑶ #define PRIQUEUE_PRIOR0_BIT              (UINT32)0x80000000 
 
⑷ #define OS_PRIORITY_QUEUE_PRIORITYNUM    32 

 其中⑴表示任務(wù)就緒隊(duì)列，是一個(gè)雙向鏈表數(shù)組，后文初始化該數(shù)組時(shí)會(huì)將數(shù)組長度設(shè)置為⑷處定義的OS_PRIORITY_QUEUE_PRIORITYNUM;⑵表示優(yōu)先級位圖，標(biāo)識(shí)了任務(wù)就緒隊(duì)列中已掛載的就緒任務(wù)所在的優(yōu)先級;⑶表示優(yōu)先級為0的比特位;⑷表示任務(wù)就緒隊(duì)列支持的優(yōu)先級個(gè)數(shù)32，所以鴻蒙輕內(nèi)核優(yōu)先級的取值范圍為0-31，數(shù)值越小優(yōu)先級越大。

優(yōu)先級位圖g_priqueueBitmap的bit位和優(yōu)先級的關(guān)系為bit=31-priority，優(yōu)先級數(shù)組g_losPriorityQueueList[priority]包含了OS_PRIORITY_QUEUE_PRIORITYNUM個(gè)數(shù)組元素，每個(gè)數(shù)組元素都是一個(gè)雙向鏈表，同一優(yōu)先級的處于就緒狀態(tài)的所有任務(wù)都會(huì)掛載到對應(yīng)優(yōu)先級的雙向鏈表中。

示意圖如下：

2 任務(wù)就緒隊(duì)列操作

2.1 初始化任務(wù)就緒隊(duì)列

任務(wù)就緒隊(duì)列初始化函數(shù)為OsPriQueueInit()，系統(tǒng)初始化階段被調(diào)用，調(diào)用路徑為：main.c:main() --> kernel\src\los_init.c:LOS_KernelInit() --> kernel\src\los_task.c:OsTaskInit() --> OsPriqueueInit()。

源碼如下：

STATIC UINT32 OsPriqueueInit(VOID) 
{ 
    UINT32 priority; 
⑴  UINT32 size = OS_PRIORITY_QUEUE_PRIORITYNUM * sizeof(LOS_DL_LIST); 
 
    g_losPriorityQueueList = (LOS_DL_LIST *)LOS_MemAlloc(m_aucSysMem0, size); 
    if (g_losPriorityQueueList == NULL) { 
        return LOS_NOK; 
    } 
 
    for (priority = 0; priority < OS_PRIORITY_QUEUE_PRIORITYNUM; ++priority) { 
⑵      LOS_ListInit(&g_losPriorityQueueList[priority]); 
    } 
    return LOS_OK; 
} 

 ⑴處計(jì)算就緒隊(duì)列數(shù)組需要的內(nèi)存大小，然后為任務(wù)就緒隊(duì)列申請內(nèi)存，占用內(nèi)存為OS_PRIORITY_QUEUE_PRIORITYNUM個(gè)雙向鏈表所需要的內(nèi)存大小，運(yùn)行期間該內(nèi)存不會(huì)釋放，為系統(tǒng)常駐內(nèi)存。⑵處代碼將每一個(gè)數(shù)組元素都初始化為雙向循環(huán)鏈表。

2.2 任務(wù)就緒隊(duì)列插入

任務(wù)就緒隊(duì)列插入函數(shù)為OsPriqueueEnqueue()，該函數(shù)把就緒狀態(tài)的任務(wù)插入任務(wù)就緒隊(duì)列的尾部。在任務(wù)就緒隊(duì)列中，先調(diào)用隊(duì)列頭部的任務(wù)，最后調(diào)用隊(duì)列尾部的任務(wù)。

源碼如下：

STATIC VOID OsPriqueueEnqueue(LOS_DL_LIST *priqueueItem, UINT32 priority) 
{ 
⑴  if (LOS_ListEmpty(&g_losPriorityQueueList[priority])) { 
⑵      g_priqueueBitmap |= (PRIQUEUE_PRIOR0_BIT >> priority); 
    } 
 
⑶  LOS_ListTailInsert(&g_losPriorityQueueList[priority], priqueueItem); 
} 

 ⑴處先判斷指定優(yōu)先級priority的任務(wù)就緒隊(duì)列是否為空，如果為空，則在⑵處更新優(yōu)先級位圖，將第31-prioritybit位設(shè)置為1。⑶處把就緒狀態(tài)的任務(wù)插入任務(wù)就緒隊(duì)列的尾部，進(jìn)行排隊(duì)。

2.3 從任務(wù)就緒隊(duì)列中刪除

從任務(wù)就緒隊(duì)列中刪除的函數(shù)為OsPriqueueDequeue()。任務(wù)被刪除、進(jìn)入suspend阻塞狀態(tài)、優(yōu)先級調(diào)整等場景中，都需要調(diào)用該函數(shù)把任務(wù)從任務(wù)就緒隊(duì)列中刪除。

源碼如下：

STATIC VOID OsPriqueueDequeue(LOS_DL_LIST *priqueueItem) 
{ 
    LosTaskCB *runningTask = NULL; 
⑴  LOS_ListDelete(priqueueItem); 
 
⑵  runningTask = LOS_DL_LIST_ENTRY(priqueueItem, LosTaskCB, pendList); 
⑶  if (LOS_ListEmpty(&g_losPriorityQueueList[runningTask->priority])) { 
⑷      g_priqueueBitmap &= ~(PRIQUEUE_PRIOR0_BIT >> runningTask->priority); 
    } 
} 

 ⑴把任務(wù)從任務(wù)就緒隊(duì)列中刪除。⑵獲取被刪除任務(wù)的任務(wù)控制塊信息，以獲取任務(wù)的優(yōu)先級。刪除完任務(wù)后隊(duì)列可能成為空隊(duì)列，所以⑶處代碼判斷任務(wù)就緒隊(duì)列是否為空，如果為空，則需要執(zhí)行⑷處代碼，更新優(yōu)先級位圖，將第31-prioritybit位設(shè)置為0。

2.4 獲取隊(duì)列中的最高優(yōu)先級節(jié)點(diǎn)

獲取任務(wù)就緒隊(duì)列中優(yōu)先級最高的鏈表節(jié)點(diǎn)的函數(shù)為OsPriQueueTop()。

源碼如下：

STATIC LOS_DL_LIST *OsPriqueueTop(VOID) 
{ 
    UINT32 priority; 
 
⑴  if (g_priqueueBitmap != 0) { 
⑵      priority = CLZ(g_priqueueBitmap); 
⑶      return LOS_DL_LIST_FIRST(&g_losPriorityQueueList[priority]); 
    } 
 
    return (LOS_DL_LIST *)NULL; 
} 

 ⑴處判斷優(yōu)先級位圖g_priqueueBitmap是否為0，如果為0則直接返回NULL，說明任務(wù)就緒隊(duì)列中沒有任何就緒狀態(tài)的任務(wù)。 ⑵處計(jì)算g_priqueueBitmap以二進(jìn)制表示時(shí)高位為0的位數(shù)，其值就是任務(wù)的優(yōu)先級priority，以此方法得到的優(yōu)先級就是任務(wù)就緒隊(duì)列中所有優(yōu)先級里最高的。然后⑶處從該優(yōu)先級的隊(duì)列&g_losPriorityQueueList[priority]中獲取第一個(gè)鏈表節(jié)點(diǎn)，獲取的就是任務(wù)就緒隊(duì)列中優(yōu)先級最高的任務(wù)。

2.5 獲取指定優(yōu)先級的就緒任務(wù)的數(shù)量

獲取任務(wù)就緒隊(duì)列中指定優(yōu)先級的任務(wù)數(shù)量的函數(shù)為OsPriqueueSize()。

源碼如下：

STATIC UINT32 OsPriqueueSize(UINT32 priority) 
{ 
    UINT32 itemCnt = 0; 
    LOS_DL_LIST *curPQNode = (LOS_DL_LIST *)NULL; 
 
⑴  LOS_DL_LIST_FOR_EACH(curPQNode, &g_losPriorityQueueList[priority]) { 
⑵      ++itemCnt; 
    } 
 
    return itemCnt; 
} 

 ⑴處代碼使用宏LOS_DL_LIST_FOR_EACH定義的for循環(huán)遍歷指定優(yōu)先級priority的雙向鏈表，如果獲取到新節(jié)點(diǎn)則表示該優(yōu)先級下有一個(gè)就緒任務(wù)，然后執(zhí)行⑵處代碼，對計(jì)數(shù)進(jìn)行加1操作，返回的結(jié)果就是指定優(yōu)先級下有多少個(gè)就緒任務(wù)。

小結(jié)

掌握鴻蒙輕內(nèi)核的優(yōu)先級就緒隊(duì)列Priority Queue這一重要的數(shù)據(jù)結(jié)構(gòu)，會(huì)給進(jìn)一步學(xué)習(xí)、分析鴻蒙輕內(nèi)核源代碼打下了基礎(chǔ)，讓后續(xù)的學(xué)習(xí)更加容易。后續(xù)也會(huì)陸續(xù)推出更多的分享文章，敬請期待。

想了解更多內(nèi)容，請?jiān)L問：

51CTO和華為官方合作共建的鴻蒙技術(shù)社區(qū)

https://harmonyos.51cto.com