鴻蒙輕內核M核源碼分析系列二數據結構-任務就緒隊列
鴻蒙輕內核源碼分析上一個系列，我們分析了雙向循環鏈表的源碼。本文會繼續給讀者介紹源碼中重要的數據結構，任務基于優先級的就緒隊列Priority Queue。在講解時，會結合數據結構相關繪圖，培養讀者們的數據結構的平面想象能力，幫助更好的學習和理解這些數據結構的用法。
1 任務就緒隊列
在任務調度模塊，就緒隊列是個重要的數據結構。任務創建后即進入就緒態，并放入就緒隊列。在鴻蒙輕內核中，就緒隊列是一個雙向循環鏈表數組，每個數組元素就是一個鏈表，相同優先級的任務放入同一個鏈表。
任務就緒隊列Priority Queue主要供內部使用，用戶進行業務開發時不涉及，所以并未對外提供接口。雙向循環鏈表數組能夠更加方便的支持任務基于優先級進行調度。任務就緒隊列的核心代碼在kernel\src\los_task.c文件中。
1.1 任務就緒隊列的定義
在kernel\src\los_task.c文件中定義了和任務就緒隊列相關的主要變量。
源碼如下：
- ⑴ 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
其中⑴表示任務就緒隊列，是一個雙向鏈表數組，后文初始化該數組時會將數組長度設置為⑷處定義的OS_PRIORITY_QUEUE_PRIORITYNUM;⑵表示優先級位圖，標識了任務就緒隊列中已掛載的就緒任務所在的優先級;⑶表示優先級為0的比特位;⑷表示任務就緒隊列支持的優先級個數32，所以鴻蒙輕內核優先級的取值范圍為0-31，數值越小優先級越大。
優先級位圖g_priqueueBitmap的bit位和優先級的關系為bit=31-priority，優先級數組g_losPriorityQueueList[priority]包含了OS_PRIORITY_QUEUE_PRIORITYNUM個數組元素，每個數組元素都是一個雙向鏈表，同一優先級的處于就緒狀態的所有任務都會掛載到對應優先級的雙向鏈表中。
示意圖如下：
2 任務就緒隊列操作
2.1 初始化任務就緒隊列
任務就緒隊列初始化函數為OsPriQueueInit()，系統初始化階段被調用，調用路徑為：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;
- }
⑴處計算就緒隊列數組需要的內存大小，然后為任務就緒隊列申請內存，占用內存為OS_PRIORITY_QUEUE_PRIORITYNUM個雙向鏈表所需要的內存大小，運行期間該內存不會釋放，為系統常駐內存。⑵處代碼將每一個數組元素都初始化為雙向循環鏈表。
2.2 任務就緒隊列插入
任務就緒隊列插入函數為OsPriqueueEnqueue()，該函數把就緒狀態的任務插入任務就緒隊列的尾部。在任務就緒隊列中，先調用隊列頭部的任務，最后調用隊列尾部的任務。
源碼如下：
- 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);
- }
⑴處先判斷指定優先級priority的任務就緒隊列是否為空，如果為空，則在⑵處更新優先級位圖，將第31-prioritybit位設置為1。⑶處把就緒狀態的任務插入任務就緒隊列的尾部，進行排隊。
2.3 從任務就緒隊列中刪除
從任務就緒隊列中刪除的函數為OsPriqueueDequeue()。任務被刪除、進入suspend阻塞狀態、優先級調整等場景中，都需要調用該函數把任務從任務就緒隊列中刪除。
源碼如下：
- 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);
- }
- }
⑴把任務從任務就緒隊列中刪除。⑵獲取被刪除任務的任務控制塊信息，以獲取任務的優先級。刪除完任務后隊列可能成為空隊列，所以⑶處代碼判斷任務就緒隊列是否為空，如果為空，則需要執行⑷處代碼，更新優先級位圖，將第31-prioritybit位設置為0。
2.4 獲取隊列中的最高優先級節點
獲取任務就緒隊列中優先級最高的鏈表節點的函數為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;
- }
⑴處判斷優先級位圖g_priqueueBitmap是否為0，如果為0則直接返回NULL，說明任務就緒隊列中沒有任何就緒狀態的任務。 ⑵處計算g_priqueueBitmap以二進制表示時高位為0的位數，其值就是任務的優先級priority，以此方法得到的優先級就是任務就緒隊列中所有優先級里最高的。然后⑶處從該優先級的隊列&g_losPriorityQueueList[priority]中獲取第一個鏈表節點，獲取的就是任務就緒隊列中優先級最高的任務。
2.5 獲取指定優先級的就緒任務的數量
獲取任務就緒隊列中指定優先級的任務數量的函數為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循環遍歷指定優先級priority的雙向鏈表，如果獲取到新節點則表示該優先級下有一個就緒任務，然后執行⑵處代碼，對計數進行加1操作，返回的結果就是指定優先級下有多少個就緒任務。
小結
掌握鴻蒙輕內核的優先級就緒隊列Priority Queue這一重要的數據結構，會給進一步學習、分析鴻蒙輕內核源代碼打下了基礎，讓后續的學習更加容易。后續也會陸續推出更多的分享文章，敬請期待。
