鴻蒙內核源碼分析(雙向鏈表篇) | 最重要結構體
https://harmonyos.51cto.com/#zz
鴻蒙內核源碼注釋中文版 < Gitee倉 | CSDN倉 | Github倉 | Coding倉 >精讀內核源碼,中文注解分析,深挖地基工程,構建底層網圖,四大碼倉每日同步更新。
鴻蒙源碼分析系列篇 < CSDN | OSCHINA | WeHarmony | 公眾號 >問答式導讀,生活式比喻,表格化說明,圖形化展示,主流站點每日同步更新。
誰是鴻蒙內核最重要的結構體?
答案一定是: 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;
結構體夠簡單了吧,只有前后兩個指向自己的指針,但恰恰是因為太簡單,所以才太不簡單. 就像氫原子一樣,宇宙中無處不在,占比最高,原因是因為它最簡單,最穩定!
內核的各自模塊都能看到雙向鏈表的身影,下圖是各處初始化雙向鏈表的操作,因為太多了,只截取了部分:
很多人問圖怎么來的, source insight 4.0 是閱讀大型C/C++工程的必備工具,要用4.0否則中文有亂碼。
可以豪不夸張的說理解LOS_DL_LIST及相關函數是讀懂鴻蒙內核的關鍵。前后指針(注者后續將比喻成一對左右觸手)靈活的指揮著系統精準的運行，越是深入分析內核源碼，越能感受到內核開發者對LOS_DL_LIST非凡的駕馭能力，筆者仿佛看到了無數雙手前后相連，拉起了一個個雙向循環鏈表，把指針的高效能運用到了極致，這也許就是編程的藝術吧!這么重要的結構體還是需詳細講解一下。
基本概念
雙向鏈表是指含有往前和往后兩個方向的鏈表，即每個結點中除存放下一個節點指針外，還增加一個指向其前一個節點的指針。其頭指針head是唯一確定的。從雙向鏈表中的任意一個結點開始，都可以很方便地訪問它的前驅結點和后繼結點，這種數據結構形式使得雙向鏈表在查找時更加方便，特別是大量數據的遍歷。由于雙向鏈表具有對稱性，能方便地完成各種插入、刪除等操作，但需要注意前后方向的操作。
功能接口
鴻蒙系統中的雙向鏈表模塊為用戶提供下面幾個接口。
請結合下面的代碼和圖去理解雙向鏈表,不管花多少時間,一定要理解它的插入/刪除動作, 否則后續內容將無從談起.
- //將指定節點初始化為雙向鏈表節點
- LITE_OS_SEC_ALW_INLINE STATIC INLINE VOID LOS_ListInit(LOS_DL_LIST *list)
- {
- list->pstNext = list;
- list->pstPrev = list;
- }
- //將指定節點掛到雙向鏈表頭部
- LITE_OS_SEC_ALW_INLINE STATIC INLINE VOID LOS_ListAdd(LOS_DL_LIST *list, LOS_DL_LIST *node)
- {
- node->pstNext = list->pstNext;
- node->pstPrev = list;
- list->pstNext->pstPrev = node;
- list->pstNext = node;
- }
- //將指定節點從鏈表中刪除,自己把自己摘掉
- LITE_OS_SEC_ALW_INLINE STATIC INLINE VOID LOS_ListDelete(LOS_DL_LIST *node)
- {
- node->pstNext->pstPrev = node->pstPrev;
- node->pstPrev->pstNext = node->pstNext;
- node->pstNext = NULL;
- node->pstPrev = NULL;
- }
具體用法
舉例 ProcessCB(進程控制塊)是描述一個進程的所有信息,其中用到了 8個雙向鏈表,這簡直比章魚還牛逼,章魚也才四雙觸手,但進程有8雙(16只)觸手。
- typedef struct ProcessCB {
- LOS_DL_LIST pendList; /**< Block list to which the process belongs */ //進程所屬的阻塞列表,如果因拿鎖失敗,就由此節點掛到等鎖鏈表上
- LOS_DL_LIST childrenList; /**< my children process list */ //孩子進程都掛到這里,形成雙循環鏈表
- LOS_DL_LIST exitChildList; /**< my exit children process list */ //那些要退出孩子進程掛到這里，白發人送黑發人。
- LOS_DL_LIST siblingList; /**< linkage in my parent's children list */ //兄弟進程鏈表, 56個民族是一家,來自同一個父進程.
- ProcessGroup *group; /**< Process group to which a process belongs */ //所屬進程組
- LOS_DL_LIST subordinateGroupList; /**< linkage in my group list */ //進程是組長時,有哪些組員進程
- UINT32 threadGroupID; /**< Which thread group , is the main thread ID of the process */ //哪個線程組是進程的主線程ID
- UINT32 threadScheduleMap; /**< The scheduling bitmap table for the thread group of the
- process */ //進程的各線程調度位圖
- LOS_DL_LIST threadSiblingList; /**< List of threads under this process *///進程的線程(任務)列表
- LOS_DL_LIST threadPriQueueList[OS_PRIORITY_QUEUE_NUM]; /**< The process's thread group schedules the
- priority hash table */ //進程的線程組調度優先級哈希表
- volatile UINT32 threadNumber; /**< Number of threads alive under this process */ //此進程下的活動線程數
- UINT32 threadCount; /**< Total number of threads created under this process */ //在此進程下創建的線程總數
- LOS_DL_LIST waitList; /**< The process holds the waitLits to support wait/waitpid *///進程持有等待鏈表以支持wait/waitpid
- } LosProcessCB;
看個簡單點的 pendList表示這個進程中所有被阻塞的任務(task)都會掛到這個鏈表上管理. 任務阻塞的原因很多,可能是申請互斥鎖失敗,可能等待事件讀消息隊列,還可能開了一個定時任務等等。
再來看一個復雜點的 threadPriQueueList,這又是干嘛的?從名字可以看出來是線程的隊列鏈表,在鴻蒙內核線程就是任務(task),任務分等了32個優先級,同級的任務放在同一個雙向鏈表中, 32級就是32個雙向鏈表,所以是個鏈表數組,每條鏈表中存放的是已就緒等待被調度的任務。
雙向鏈表是內核最重要的結構體,精讀內核的路上它會反復的映入你的眼簾,理解它是理解內存運作的關鍵所在!
作者郵箱:weharmony@126.com
鴻蒙內核源碼注釋中文版 < Gitee倉 | CSDN倉 | Github倉 | Coding倉 >精讀內核源碼,中文注解分析,深挖地基工程,構建底層網圖,四大碼倉每日同步更新
鴻蒙源碼分析系列篇 < CSDN | OSCHINA | WeHarmony | 公眾號 >問答式導讀,生活式比喻,表格化說明,圖形化展示,主流站點每日同步更新
©著作權歸作者和HarmonyOS技術社區共同所有，如需轉載，請注明出處，否則將追究法律責任。
https://harmonyos.51cto.com/#zz
