0
  • 聊天消息
  • 系統(tǒng)消息
  • 評論與回復(fù)
登錄后你可以
  • 下載海量資料
  • 學(xué)習(xí)在線課程
  • 觀看技術(shù)視頻
  • 寫文章/發(fā)帖/加入社區(qū)
會員中心
創(chuàng)作中心

完善資料讓更多小伙伴認(rèn)識你,還能領(lǐng)取20積分哦,立即完善>

3天內(nèi)不再提示

深度解析鴻蒙內(nèi)核最重要的結(jié)構(gòu)體

鴻蒙系統(tǒng)HarmonyOS ? 來源:my.oschina ? 作者:鴻蒙內(nèi)核源碼分析 ? 2021-04-25 11:58 ? 次閱讀

誰是鴻蒙內(nèi)核最重要的結(jié)構(gòu)體?

答案一定是:LOS_DL_LIST(雙向鏈表),它長這樣.

typedef struct LOS_DL_LIST {//雙向鏈表,內(nèi)核最重要結(jié)構(gòu)體
    struct LOS_DL_LIST *pstPrev; /**< Current node's pointer to the previous node *///前驅(qū)節(jié)點(左手)
    struct LOS_DL_LIST *pstNext; /**< Current node's pointer to the next node *///后繼節(jié)點(右手)
} LOS_DL_LIST;

結(jié)構(gòu)體夠簡單了吧,只有前后兩個指向自己的指針,但恰恰是因為太簡單,所以才太不簡單. 就像氫原子一樣,宇宙中無處不在,占比最高,原因是因為它最簡單,最穩(wěn)定!

內(nèi)核的各自模塊都能看到雙向鏈表的身影,下圖是各處初始化雙向鏈表的操作,因為太多了,只截取了部分:

pIYBAGCE6DKAAf-bAARvRfH2FV4405.png

很多人問圖怎么來的,source insight 4.0是閱讀大型C/C++工程的必備工具,要用4.0否則中文有亂碼.

可以豪不夸張的說理解LOS_DL_LIST及相關(guān)函數(shù)是讀懂鴻蒙內(nèi)核的關(guān)鍵。前后指針(注者后續(xù)將比喻成一對左右觸手)靈活的指揮著系統(tǒng)精準(zhǔn)的運行,越是深入分析內(nèi)核源碼,越能感受到內(nèi)核開發(fā)者對LOS_DL_LIST非凡的駕馭能力,筆者仿佛看到了無數(shù)雙手前后相連,拉起了一個個雙向循環(huán)鏈表,把指針的高效能運用到了極致,這也許就是編程的藝術(shù)吧!這么重要的結(jié)構(gòu)體還是需詳細(xì)講解一下.

基本概念

雙向鏈表是指含有往前和往后兩個方向的鏈表,即每個結(jié)點中除存放下一個節(jié)點指針外,還增加一個指向其前一個節(jié)點的指針。其頭指針head是唯一確定的。從雙向鏈表中的任意一個結(jié)點開始,都可以很方便地訪問它的前驅(qū)結(jié)點和后繼結(jié)點,這種數(shù)據(jù)結(jié)構(gòu)形式使得雙向鏈表在查找時更加方便,特別是大量數(shù)據(jù)的遍歷。由于雙向鏈表具有對稱性,能方便地完成各種插入、刪除等操作,但需要注意前后方向的操作。

有好幾個同學(xué)問數(shù)據(jù)在哪? 確實LOS_DL_LIST這個結(jié)構(gòu)看起來怪怪的,它竟沒有數(shù)據(jù)域!所以看到這個結(jié)構(gòu)的人第一反應(yīng)就是我們怎么訪問數(shù)據(jù)?其實LOS_DL_LIST不是拿來單獨用的,它是寄生在內(nèi)容結(jié)構(gòu)體上的,誰用它誰就是它的數(shù)據(jù).看圖就明白了.

pIYBAGCE6EaAToV1AADMtl72i_g471.png

功能接口

鴻蒙系統(tǒng)中的雙向鏈表模塊為用戶提供下面幾個接口。

pIYBAGCE6FOAL5ATAAEsiAQ3PvI596.png

請結(jié)合下面的代碼和圖去理解雙向鏈表,不管花多少時間,一定要理解它的插入/刪除動作,否則后續(xù)內(nèi)容將無從談起.

//將指定節(jié)點初始化為雙向鏈表節(jié)點
LITE_OS_SEC_ALW_INLINE STATIC INLINE VOID LOS_ListInit(LOS_DL_LIST *list)
{
    list->pstNext = list;
    list->pstPrev = list;
}

//將指定節(jié)點掛到雙向鏈表頭部
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;
}
//將指定節(jié)點從鏈表中刪除,自己把自己摘掉
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;
}

pIYBAGCE6GqAMe0lAAHgHk5dkIE576.png

強大的宏

除了內(nèi)聯(lián)函數(shù),對雙向遍歷的初始化,定位,遍歷 等等操作提供了更強大的宏支持.使內(nèi)核以極其簡潔高效的代碼實現(xiàn)復(fù)雜邏輯的處理.

//定義一個節(jié)點并初始化為雙向鏈表節(jié)點
#define LOS_DL_LIST_HEAD(list) LOS_DL_LIST list = { &(list), &(list) }

//獲取指定結(jié)構(gòu)體內(nèi)的成員相對于結(jié)構(gòu)體起始地址的偏移量
#define LOS_OFF_SET_OF(type, member) ((UINTPTR)&((type *)0)->member)

//獲取包含鏈表的結(jié)構(gòu)體地址,接口的第一個入?yún)⒈硎镜氖擎湵碇械哪硞€節(jié)點,第二個入?yún)⑹且@取的結(jié)構(gòu)體名稱,第三個入?yún)⑹擎湵碓谠摻Y(jié)構(gòu)體中的名稱
#define LOS_DL_LIST_ENTRY(item, type, member) \
    ((type *)(VOID *)((CHAR *)(item) - LOS_OFF_SET_OF(type, member)))

//遍歷雙向鏈表
#define LOS_DL_LIST_FOR_EACH(item, list) \
    for (item = (list)->pstNext;         \
         (item) != (list);               \
         item = (item)->pstNext)

//遍歷指定雙向鏈表,獲取包含該鏈表節(jié)點的結(jié)構(gòu)體地址,并存儲包含當(dāng)前節(jié)點的后繼節(jié)點的結(jié)構(gòu)體地址
#define LOS_DL_LIST_FOR_EACH_ENTRY_SAFE(item, next, list, type, member)               \
    for (item = LOS_DL_LIST_ENTRY((list)->pstNext, type, member),                     \
         next = LOS_DL_LIST_ENTRY((item)->member.pstNext, type, member);              \
         &(item)->member != (list);                                                   \
         item = next, next = LOS_DL_LIST_ENTRY((item)->member.pstNext, type, member))

//遍歷指定雙向鏈表,獲取包含該鏈表節(jié)點的結(jié)構(gòu)體地址
#define LOS_DL_LIST_FOR_EACH_ENTRY(item, list, type, member)             \
    for (item = LOS_DL_LIST_ENTRY((list)->pstNext, type, member);        \
         &(item)->member != (list);                                      \
         item = LOS_DL_LIST_ENTRY((item)->member.pstNext, type, member))

例如在調(diào)度算法中獲取當(dāng)前最高優(yōu)先級的任務(wù)時,就需要遍歷整個進程和進程任務(wù)的所有就緒列表.LOS_DL_LIST_FOR_EACH_ENTRY高效的解決了層層循環(huán)的問題,讓代碼簡潔易懂.

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

結(jié)構(gòu)體的最愛

LOS_DL_LIST是復(fù)雜結(jié)構(gòu)體的最愛,以下舉例ProcessCB(進程控制塊)是描述一個進程的所有信息,其中用到了 8個雙向鏈表,這簡直比章魚還牛逼,章魚也才四雙觸手,但進程有8雙(16只)觸手.

typedef struct ProcessCB {
    //...此處省略其他變量
    LOS_DL_LIST          pendList;                     /**< Block list to which the process belongs */ //進程所屬的阻塞列表,如果因拿鎖失敗,就由此節(jié)點掛到等鎖鏈表上
    LOS_DL_LIST          childrenList;                 /**< my children process list */	//孩子進程都掛到這里,形成雙循環(huán)鏈表
    LOS_DL_LIST          exitChildList;                /**< my exit children process list */	//那些要退出孩子進程掛到這里,白發(fā)人送黑發(fā)人。
    LOS_DL_LIST          siblingList;                  /**< linkage in my parent's children list */ //兄弟進程鏈表, 56個民族是一家,來自同一個父進程.
    LOS_DL_LIST          subordinateGroupList;         /**< linkage in my group list */ //進程是組長時,有哪些組員進程
    LOS_DL_LIST          threadSiblingList;            /**< List of threads under this process *///進程的線程(任務(wù))列表
    LOS_DL_LIST          threadPriQueueList[OS_PRIORITY_QUEUE_NUM]; /**< The process's thread group schedules thepriority hash table */	//進程的線程組調(diào)度優(yōu)先級哈希表
    LOS_DL_LIST          waitList;     /**< The process holds the waitLits to support wait/waitpid *///進程持有等待鏈表以支持wait/waitpid
} LosProcessCB;

解讀

pendList個人認(rèn)為它是鴻蒙內(nèi)核功能最多的一個鏈表,它遠(yuǎn)不止字面意思阻塞鏈表這么簡單,只有深入解讀源碼后才能體會它真的是太會來事了,一般把它理解為阻塞鏈表就行.上面掛的是處于阻塞狀態(tài)的進程.

childrenList孩子鏈表,所有由它fork出來的進程都掛到這個鏈表上.上面的孩子進程在死亡前會將自己從上面摘出去,轉(zhuǎn)而掛到exitChildList鏈表上.

exitChildList退出孩子鏈表,進入死亡程序的進程要掛到這個鏈表上,一個進程的死亡是件挺麻煩的事,進程池的數(shù)量有限,需要及時回收進程資源,但家族管理關(guān)系復(fù)雜,要去很多地方消除痕跡.尤其還有其他進程在看你笑話,等你死亡(wait/waitpid)了通知它們一聲.

siblingList兄弟鏈表,和你同一個父親的進程都掛到了這個鏈表上.

subordinateGroupList朋友圈鏈表,里面是因為興趣愛好(進程組)而掛在一起的進程,它們可以不是一個父親,不是一個祖父,但一定是同一個老祖宗(用戶態(tài)和內(nèi)核態(tài)根進程).

threadSiblingList線程鏈表,上面掛的是進程ID都是這個進程的線程(任務(wù)),進程和線程的關(guān)系是1:N的關(guān)系,一個線程只能屬于一個進程.這里要注意任務(wù)在其生命周期中是不能改所屬進程的.

threadPriQueueList線程的調(diào)度隊列數(shù)組,一共32個,任務(wù)和進程一樣有32個優(yōu)先級,調(diào)度算法的過程是先找到優(yōu)先級最高的進程,在從該進程的任務(wù)隊列里去最高的優(yōu)先級任務(wù)運行.

waitList是等待子進程消亡的任務(wù)鏈表,注意上面掛的是任務(wù).任務(wù)是通過系統(tǒng)調(diào)用

  pid_t wait(int *status);
  pid_t waitpid(pid_t pid, int *status, int options);
將任務(wù)掛到waitList上.鴻蒙waitpid系統(tǒng)調(diào)用為SysWait,具體看進程回收篇.

雙向鏈表是內(nèi)核最重要的結(jié)構(gòu)體,精讀內(nèi)核的路上它會反復(fù)的映入你的眼簾,理解它是理解內(nèi)核運作的關(guān)鍵所在!

編輯:hfy

聲明:本文內(nèi)容及配圖由入駐作者撰寫或者入駐合作網(wǎng)站授權(quán)轉(zhuǎn)載。文章觀點僅代表作者本人,不代表電子發(fā)燒友網(wǎng)立場。文章及其配圖僅供工程師學(xué)習(xí)之用,如有內(nèi)容侵權(quán)或者其他違規(guī)問題,請聯(lián)系本站處理。 舉報投訴
  • 內(nèi)核
    +關(guān)注

    關(guān)注

    3

    文章

    1373

    瀏覽量

    40310
  • 鴻蒙系統(tǒng)
    +關(guān)注

    關(guān)注

    183

    文章

    2636

    瀏覽量

    66399
收藏 人收藏

    評論

    相關(guān)推薦

    鴻蒙案例技術(shù)分享 | 基于AIoT-3568X的鴻蒙通行一機方案項目

    案例展示視美泰鴻蒙通行一機方案以鴻蒙版AIoT-3568X人工智能主板為核心平臺,搭載OpenHarmony操作系統(tǒng),使用自研算法和國產(chǎn)芯片,可管可控,并提供身份識別以及其他外設(shè)配件生態(tài)鏈支持
    的頭像 發(fā)表于 12-13 16:25 ?330次閱讀
    <b class='flag-5'>鴻蒙</b>案例技術(shù)分享 | 基于AIoT-3568X的<b class='flag-5'>鴻蒙</b>通行一<b class='flag-5'>體</b>機方案項目

    結(jié)構(gòu)成員的順序會影響結(jié)構(gòu)的大小嗎

    相同的結(jié)構(gòu)成員,如果把順序調(diào)整一下,會不會影響結(jié)構(gòu)的大??? 答案是會的,這主要跟字節(jié)對齊有關(guān)。 比如這樣的結(jié)構(gòu)
    的頭像 發(fā)表于 11-25 16:24 ?196次閱讀

    增強型MOS管的結(jié)構(gòu)解析

    增強型MOS管(Enhancement MOSFET)是一種重要的場效應(yīng)晶體管,具有高輸入阻抗、低輸入電流、高速開關(guān)和低噪聲等優(yōu)點,被廣泛應(yīng)用于電子設(shè)備中。以下是對增強型MOS管結(jié)構(gòu)的詳細(xì)解析
    的頭像 發(fā)表于 07-24 10:51 ?1626次閱讀

    溫度補償振蕩器TG-3541CE的深度解析

    溫度補償振蕩器TG-3541CE的深度解析
    的頭像 發(fā)表于 07-18 17:48 ?330次閱讀

    深度神經(jīng)網(wǎng)絡(luò)(DNN)架構(gòu)解析與優(yōu)化策略

    深度神經(jīng)網(wǎng)絡(luò)(Deep Neural Network, DNN)作為機器學(xué)習(xí)領(lǐng)域中的一種重要技術(shù),以其強大的特征學(xué)習(xí)能力和非線性建模能力,在多個領(lǐng)域取得了顯著成果。DNN的核心在于其多層結(jié)構(gòu),通過
    的頭像 發(fā)表于 07-09 11:00 ?1922次閱讀

    華為鴻蒙內(nèi)核獲中國信通院自主成熟度A級認(rèn)證

    在科技創(chuàng)新的浪潮中,華為再次以其卓越的自主研發(fā)能力引領(lǐng)行業(yè)前行。近日,中國信息通信研究院(簡稱“中國信通院”)官方公眾號宣布了一項重要成果:華為技術(shù)有限公司的鴻蒙內(nèi)核成功通過了自主成熟度等級認(rèn)證
    的頭像 發(fā)表于 07-03 14:32 ?657次閱讀

    歡創(chuàng)播報 華為宣布鴻蒙內(nèi)核已超越Linux內(nèi)核

    1 華為宣布鴻蒙內(nèi)核已超越Linux內(nèi)核 ? 6月21日,在華為開發(fā)者大會上, HarmonyOS NEXT(鴻蒙NEXT)——真正獨立于安卓和iOS的
    的頭像 發(fā)表于 06-27 11:30 ?852次閱讀

    PLC基本結(jié)構(gòu)解析

    方式和便捷的編程方式,被廣泛應(yīng)用于各種工業(yè)控制系統(tǒng)中。本文將詳細(xì)解析PLC的基本結(jié)構(gòu),包括其主要組成部分的功能和特點,以便讀者對PLC有更深入的了解。
    的頭像 發(fā)表于 06-25 14:30 ?1003次閱讀

    華為發(fā)布鴻蒙原生智能,OS深度融合AI,小藝升級為系統(tǒng)級智能

    Beta。鴻蒙原生智能是基于軟硬芯云協(xié)同的硬件與基礎(chǔ)設(shè)施架構(gòu),AI與OS深度融合的智能系統(tǒng)。 小藝智能:能思考,會規(guī)劃,可執(zhí)行 基于鴻蒙原生智能強大的AI底座,搭載盤古大模型,小藝升
    的頭像 發(fā)表于 06-24 14:30 ?548次閱讀
    華為發(fā)布<b class='flag-5'>鴻蒙</b>原生智能,OS<b class='flag-5'>深度</b>融合AI,小藝升級為系統(tǒng)級智能<b class='flag-5'>體</b>

    HDC2024華為發(fā)布鴻蒙原生智能:AI與OS深度融合,開啟全新的AI時代

    6月21日,華為開發(fā)者大會2024(HDC.2024)召開。 HarmonyOS NEXT將AI與OS深度融合,構(gòu)筑全新鴻蒙原生智能框架。大會現(xiàn)場,華為常務(wù)董事、終端BG董事長、智能汽車解決方案BU
    的頭像 發(fā)表于 06-24 09:28 ?626次閱讀
    HDC2024華為發(fā)布<b class='flag-5'>鴻蒙</b>原生智能:AI與OS<b class='flag-5'>深度</b>融合,開啟全新的AI時代

    【JAVA UI】【HarmonyOS】【Demo】 鴻蒙如何進行 xml 解析

    鴻蒙鴻蒙如何進行數(shù)據(jù)解析 【問題描述】有時候我們從服務(wù)器獲取是 xml 格式數(shù)據(jù),我們需要將 xml 轉(zhuǎn)化成 model 對象,該如何使用呢?下面舉個例子說明一下,將分以下幾步進行 1.準(zhǔn)備條件
    的頭像 發(fā)表于 02-19 15:59 ?579次閱讀
    【JAVA UI】【HarmonyOS】【Demo】 <b class='flag-5'>鴻蒙</b>如何進行 xml <b class='flag-5'>解析</b>

    鴻蒙開發(fā)者預(yù)覽版如何?

    Linux內(nèi)核以及AOSP代碼,采用的鴻蒙內(nèi)核以及代碼,HarmonyOS NEXT系統(tǒng)僅支持鴻蒙內(nèi)核
    發(fā)表于 02-17 21:54

    鴻蒙使用的是微內(nèi)核?

    我們常說,看一個系統(tǒng)是不是自研,就看它的內(nèi)核,常見的內(nèi)核分為:宏內(nèi)核和微內(nèi)核,當(dāng)然還有兩者結(jié)合體,他們到底有什么區(qū)別? 白話宏內(nèi)核和微
    的頭像 發(fā)表于 01-30 16:43 ?493次閱讀
    <b class='flag-5'>鴻蒙</b>使用的是微<b class='flag-5'>內(nèi)核</b>?

    鴻蒙OS和開源鴻蒙什么關(guān)系?

    開源鴻蒙(Open Harmony) 鴻蒙系統(tǒng)愿來的設(shè)計初衷,就是讓所有設(shè)備都可以運行一個系統(tǒng),但是每個設(shè)備的運算能力和功能都不同,所以內(nèi)核的設(shè)計上,采用了微內(nèi)核的設(shè)計,除了最基礎(chǔ)的功
    的頭像 發(fā)表于 01-30 15:44 ?1159次閱讀
    <b class='flag-5'>鴻蒙</b>OS和開源<b class='flag-5'>鴻蒙</b>什么關(guān)系?

    結(jié)構(gòu)與指針的關(guān)系

    在C語言中,結(jié)構(gòu)(Struct)是一種用戶自定義的數(shù)據(jù)類型,它允許您將不同類型的數(shù)據(jù)項組合在一起,以便形成一個更復(fù)雜的數(shù)據(jù)結(jié)構(gòu)。結(jié)構(gòu)可以
    的頭像 發(fā)表于 01-11 08:00 ?1008次閱讀
    <b class='flag-5'>結(jié)構(gòu)</b><b class='flag-5'>體</b>與指針的關(guān)系