LiteOS內核源碼分析系列一 盤點那些重要的數(shù)據(jù)結構（2）

LiteOS內核源碼分析系列一 盤點那些重要的數(shù)據(jù)結構 -- PQ

在學習Huawei LiteOS源代碼的時候，常常會遇到一些數(shù)據(jù)結構的使用。如果沒有掌握這它們的用法，閱讀LiteOS源代碼的時候會很費解、很吃力。本文會給讀者介紹下LiteOS源碼中常用的幾個數(shù)據(jù)結構，包括: 雙向循環(huán)鏈表LOS_DL_LIST，優(yōu)先級隊列Priority Queue，排序鏈表SortLinkList等。在講解時，會結合相關的繪圖，培養(yǎng)數(shù)據(jù)結構的平面想象能力，幫助更好的學習和理解這些數(shù)據(jù)結構用法。

本文中所涉及的LiteOS源碼，均可以在LiteOS開源站點https://gitee.com/LiteOS/LiteOS?獲取。

這是第二部分，我們來看看使用最多的Priority Queue優(yōu)先級隊列。

2、Priority Queue 優(yōu)先級隊列

在任務調度模塊，就緒隊列是個重要的數(shù)據(jù)結構，就緒隊列需要支持初始化，出入隊列，從隊列獲取最高優(yōu)先級任務等操作。LiteOS調度模塊支持單一就緒隊列（Single Ready Queue）和多就緒隊列（Multiple Ready Queue），我們這里主要講述一下單一就緒隊列。

優(yōu)先級隊列Priority Queue接口主要內部使用，用戶業(yè)務開發(fā)時不涉及，不對外提供接口。優(yōu)先級隊列其實就是個雙向循環(huán)鏈表數(shù)組，提供更加方便的接口支持任務基于優(yōu)先級進行調度。

優(yōu)先級隊列核心的代碼都在kernel\base\include\los_priqueue_pri.h頭文件和kernel\base\sched\sched_sq\los_priqueue.c實現(xiàn)文件中。

我們來看看優(yōu)先級隊列支持的操作。

2.1 Priority Queue 優(yōu)先級隊列變量定義

LiteOS支持32個優(yōu)先級，取值范圍0-31，優(yōu)先級數(shù)值越小優(yōu)先級越大。優(yōu)先級隊列在kernel\base\sched\sched_sq\los_priqueue.c文件中定義的幾個變量如下，

其中⑴表示優(yōu)先級為0的位，⑵處表示優(yōu)先級隊列的雙向鏈表數(shù)組，后文會初始化為數(shù)組的長度為32，⑶表示優(yōu)先級位圖，標志哪些優(yōu)先級就緒隊列里有掛載的任務。

示意圖如下：

優(yōu)先級位圖g_priQueueBitmap的bit位和優(yōu)先級的關系是bits=31-priority，g_priQueueList[priority]優(yōu)先級數(shù)組內容為雙向鏈表，掛載各個優(yōu)先級的處于就緒狀態(tài)的任務。

源碼如下：

#define OS_PRIORITY_QUEUE_NUM 32 ⑴ #define PRIQUEUE_PRIOR0_BIT 0x80000000U ⑵ LITE_OS_SEC_BSS LOS_DL_LIST *g_priQueueList = NULL; ⑶ STATIC LITE_OS_SEC_BSS UINT32 g_priQueueBitmap;

下面我們來學習下優(yōu)先級隊列支持的那些操作。

2.2 Priority Queue 優(yōu)先級隊列接口

2.2.1 OsPriQueueInit(VOID)初始化

優(yōu)先級隊列初始化在系統(tǒng)初始化的時候調用：main.c:main(void)k-->kernel\init\los_init.c:OsMain(VOID)-->kernel\base\los_task.c:OsTaskInit(VOID)-->OsPriQueueInit()。

從下面的代碼可以看出，⑴處申請長度為32的雙向鏈表數(shù)值申請常駐內存，運行期間不會調用Free()接口釋放。⑴處代碼為數(shù)組的每一個雙向鏈表元素都初始化為雙向循環(huán)鏈表。

源碼如下：

UINT32 OsPriQueueInit(VOID) { UINT32 priority; /* 系統(tǒng)常駐內存，運行期間不會Free釋放 */ ⑴ 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; }

2.2.2 OsPriQueueEnqueueHead()插入就緒隊列頭部

OsPriQueueEnqueueHead()從就緒隊列的頭部進行插入，插入得晚，但在同等優(yōu)先級的任務中，會第一個調度。一起看下代碼，⑴處先判斷指定優(yōu)先級priority的就緒隊列是否為空，如果為空，則在⑵處更新優(yōu)先級位圖。⑶處把就緒狀態(tài)的任務插入就緒隊列的頭部，以便優(yōu)先調度。

源碼如下：

VOID OsPriQueueEnqueueHead(LOS_DL_LIST *priqueueItem, UINT32 priority) { LOS_ASSERT(priqueueItem->pstNext == NULL); ⑴ if (LOS_ListEmpty(&g_priQueueList[priority])) { ⑵ g_priQueueBitmap |= PRIQUEUE_PRIOR0_BIT >> priority; } ⑶ LOS_ListHeadInsert(&g_priQueueList[priority], priqueueItem); }

2.2.3 OsPriQueueEnqueue()插入就緒隊列尾部

和OsPriQueueEnqueueHead()的區(qū)別是，把就緒狀態(tài)的任務插入就緒隊列的尾部，同等優(yōu)先級的任務中，后插入的后調度。

2.2.4 OsPriQueueDequeue()就緒隊列中刪除

在任務被刪除、進入suspend狀態(tài)，優(yōu)先級調整等場景時，都需要調用接口OsPriQueueEnqueue()把任務從優(yōu)先級隊列中刪除。

我們來看下代碼，⑴把任務從優(yōu)先級就緒隊列中刪除。⑵獲取刪除的任務TCB信息，用來獲取任務的優(yōu)先級。剛從優(yōu)先級隊列中刪除了一個任務，⑶處代碼判斷優(yōu)先級隊列是否為空，

如果為空，則需要執(zhí)行⑷處代碼，把優(yōu)先級位圖中對應的優(yōu)先級bit位置為0。

源碼如下：

VOID OsPriQueueDequeue(LOS_DL_LIST *priqueueItem) { LosTaskCB *runTask = NULL; ⑴ LOS_ListDelete(priqueueItem); ⑵ runTask = LOS_DL_LIST_ENTRY(priqueueItem, LosTaskCB, pendList); ⑶ if (LOS_ListEmpty(&g_priQueueList[runTask->priority])) { ⑷ g_priQueueBitmap &= ~(PRIQUEUE_PRIOR0_BIT >> runTask->priority); } }

2.2.5 LOS_DL_LIST *OsPriQueueTop(VOID)獲取就緒的優(yōu)先級最高的鏈表節(jié)點

這個接口可以獲取優(yōu)先級就緒隊列中優(yōu)先級最高的鏈表節(jié)點。⑴處判斷優(yōu)先級位圖g_priQueueBitmap是否為0，如果為0，說明沒有任何就緒狀態(tài)的任務，返回NULL。 ⑵處計算g_priQueueBitmap二進制時開頭的0的數(shù)目，這個數(shù)目對應于

任務的優(yōu)先級priority，然后⑶處從&g_priQueueList[priority]優(yōu)先級隊列鏈表中獲取第一個鏈表節(jié)點。

源碼如下：

LOS_DL_LIST *OsPriQueueTop(VOID) { UINT32 priority; ⑴ if (g_priQueueBitmap != 0) { ⑵ priority = CLZ(g_priQueueBitmap); ⑶ return LOS_DL_LIST_FIRST(&g_priQueueList[priority]); } return NULL; }

2.2.6 UINT32 OsPriQueueSize(UINT32 priority)獲取指定優(yōu)先級的就緒任務的數(shù)量

這個接口可以獲取指定優(yōu)先級的就緒隊列中任務的數(shù)量。⑴、⑶處代碼表示，在SMP多核模式下，根據(jù)獲取的當前CPU編號的cpuId，判斷任務是否屬于當前CPU核，如果不屬于，則不計數(shù)。⑵處代碼使用for循環(huán)遍歷指定優(yōu)先級就緒隊列中的鏈表節(jié)點，對遍歷到新節(jié)點則執(zhí)行⑷處代碼，對計數(shù)進行進行加1操作。

源碼如下：

UINT32 OsPriQueueSize(UINT32 priority) { UINT32 itemCnt = 0; LOS_DL_LIST *curNode = NULL; #ifdef LOSCFG_KERNEL_SMP LosTaskCB *task = NULL; ⑴ UINT32 cpuId = ArchCurrCpuid(); #endif LOS_ASSERT(ArchIntLocked()); LOS_ASSERT(LOS_SpinHeld(&g_taskSpin)); ⑵ LOS_DL_LIST_FOR_EACH(curNode, &g_priQueueList[priority]) { #ifdef LOSCFG_KERNEL_SMP task = OS_TCB_FROM_PENDLIST(curNode); ⑶ if (!(task->cpuAffiMask & (1U << cpuId))) { continue; } #endif ⑷ ++itemCnt; } return itemCnt; }

2.2.7 LosTaskCB *OsGetTopTask(VOID)獲取就緒的優(yōu)先級最高的任務

這個接口或者就緒任務隊列中優(yōu)先級最高的任務。一起看下代碼，⑴、⑷處對SMP多核做特殊處理，如果是多核，只獲取指定在當前CPU核運行的優(yōu)先級最高的任務。⑵處獲取g_priQueueBitmap優(yōu)先級位圖的值，賦值給UINT32 bitmap;。不直接操作優(yōu)先級位圖的原因是什么呢？在SMP多核時，在高優(yōu)先級任務就緒隊列里沒有找到指定在當前CPU核運行的任務，需要執(zhí)行⑹處的代碼，清零臨時優(yōu)先級位圖的bit位，去低一級的優(yōu)先級就緒隊列里去查找。只能改動臨時優(yōu)先級位圖，不能改變g_priQueueBitmap。⑶處代碼對優(yōu)先級最高的就緒隊列進行遍歷，如果遍歷到則執(zhí)行⑸處代碼從優(yōu)先級就緒隊列里出隊，函數(shù)返回對應的LosTaskCB *newTask。

源碼如下：

{ UINT32 priority; UINT32 bitmap; LosTaskCB *newTask = NULL; #ifdef LOSCFG_KERNEL_SMP ⑴ UINT32 cpuid = ArchCurrCpuid(); #endif ⑵ bitmap = g_priQueueBitmap; while (bitmap) { priority = CLZ(bitmap); ⑶ LOS_DL_LIST_FOR_EACH_ENTRY(newTask, &g_priQueueList[priority], LosTaskCB, pendList) { #ifdef LOSCFG_KERNEL_SMP ⑷ if (newTask->cpuAffiMask & (1U << cpuid)) { #endif ⑸ OsPriQueueDequeue(&newTask->pendList); goto OUT; #ifdef LOSCFG_KERNEL_SMP } #endif } ⑹ bitmap &= ~(1U << (OS_PRIORITY_QUEUE_NUM - priority - 1)); } OUT: return newTask; }

輕量級操作系統(tǒng) LiteOS

版權聲明：本文內容由網(wǎng)絡用戶投稿，版權歸原作者所有，本站不擁有其著作權，亦不承擔相應法律責任。如果您發(fā)現(xiàn)本站中有涉嫌抄襲或描述失實的內容，請聯(lián)系我們jiasou666@gmail.com 處理，核實后本網(wǎng)站將在24小時內刪除侵權內容。