本篇关键词:、、、

下载 >> 离线文档.鸿蒙内核源码分析(百篇博客分析.挖透鸿蒙内核).pdf

进程管理相关篇为:

二叉查找树 | BST

要理解红黑树,需要从二叉查找树(Binary Search Tree)开始说起。其特点是:

  • 1.左子树上所有结点的值均小于或等于它的根结点的值。
  • 2.右子树上所有结点的值均大于或等于它的根结点的值。
  • 3.左、右子树也分别为二叉排序树。

例如:想要找到下图节点 10 就需要经过路径 [ 9 | 13 | 11 ]

在理想的情况下,二叉查找树增删查改的时间复杂度为O(logN)(其中N为节点数),最坏的情况下为O(N)。

BST 的特点是在操作过程中容易失去平衡,数在插入的时候会导致树倾斜,不同的插入顺序会导致树的高度不一样,而树的高度直接的影响了树的查找效率。理想的高度是logN,最坏的情况是所有的节点都在一条斜线上,这样的树的高度为N。例如:下图为初始的二叉查找树 接下来依次插入如下五个结点:7,6,5,4,3,结果将变成简直没法看的

红黑树

基于BST存在的问题,一种新的树——平衡二叉查找树即 红黑树(Red-Black Tree,以下简称RBTree),它在插入和删除的时候,会通过旋转操作将高度保持在logN。通俗的讲就是会自我纠正,跟人睡觉一样,将自己的身体调整到一个让最省力,最舒服的姿势。其实际应用非常广泛,比如Linux内核中的完全公平调度器、高精度计时器、ext3文件系统等等,鸿蒙内核中也使用了红黑树来管理进程线性区。上图经过红黑树调整之后的姿势为:

红黑树有以下几个特点:

  • 1.任何一个节点都有颜色,黑色或者红色。
  • 2.根节点是黑色的。
  • 3.父子节点之间不能出现两个连续的红节点。
  • 4.任何一个节点向下遍历到其子孙的叶子节点,所经过的黑节点个数必须相等。
  • 5.空节点被认为是黑色的。
  • 6.从根到叶子的最长的可能路径不多于最短的可能路径的两倍长。

红黑树具体的调整姿势的方法有两种:

  • 变色 根据红黑树的规则,尝试把红色结点变为黑色,或者把黑色结点变为红色。
  • 旋转,根据旋转方向又分成 左旋转右旋转
    • 左旋转(逆时针旋转) 红黑树的两个结点,使得父结点被自己的右孩子取代,而自己成为自己的左孩子。
    • 右旋转(顺时针旋转) 红黑树的两个结点,使得父结点被自己的左孩子取代,而自己成为自己的右孩子。
  • 有兴趣的可以前往 红黑树演示网站 玩一下,很有意思

在鸿蒙使用

鸿蒙使用红黑树主要用来管理进程的 线性区 ,关于线性区不清楚的请自行翻看系列篇,简单说就是一个虚拟地址连续的内存记录。我们动态申请堆内存其实就是申请了一个线性区,释放内存时就需要查找这个记录,这种使用频率很高,而红黑树的查找效率最高。鸿蒙红黑树功能的核心结构体是 LosRbTree ,每一个进程都有一颗属于自己的红黑树。

typedef struct VmMapRange {//线性区范围结构体
    VADDR_T             base;           /**< vm region base addr | 线性区基地址*/
    UINT32              size;           /**< vm region size | 线性区大小*/
} LosVmMapRange;

typedef struct TagRbNode {//节点
    struct TagRbNode *pstParent; ///< 爸爸是谁 ?
    struct TagRbNode *pstRight;  ///< 右孩子是谁 ?
    struct TagRbNode *pstLeft;	 ///< 左孩子是谁 ?
    ULONG_T lColor; //是红还是黑节点
} LosRbNode;

typedef struct TagRbTree {//红黑树控制块
    LosRbNode *pstRoot;//根节点
    LosRbNode stNilT;//叶子节点
    LOS_DL_LIST stWalkHead;
    ULONG_T ulNodes;

    pfRBCmpKeyFn pfCmpKey; //比较两个节点大小 处理函数
    pfRBFreeFn pfFree;	//释放结点占用内存函数
    pfRBGetKeyFn pfGetKey;//获取指定线性区范围 VmMapRange 函数
} LosRbTree;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

解读

  • 红黑树初始化,在进程空间初始化期间会初始化红黑树,并指定三个回调函数(方便红黑树节点的遍历)。
    //初始化进程的红黑树
    VOID LOS_RbInitTree(LosRbTree *pstTree, pfRBCmpKeyFn pfCmpKey, pfRBFreeFn pfFree, pfRBGetKeyFn pfGetKey)
    {
        OsRbInitTree(pstTree);
        pstTree->pfCmpKey = pfCmpKey;
        pstTree->pfFree = pfFree;
        pstTree->pfGetKey = pfGetKey;
        return;
    }
    //初始化进程虚拟空间
    STATIC BOOL OsVmSpaceInitCommon(LosVmSpace *vmSpace, VADDR_T *virtTtb){
        //...
        LOS_RbInitTree(&vmSpace->regionRbTree, OsRegionRbCmpKeyFn, OsRegionRbFreeFn, OsRegionRbGetKeyFn);
    }
    ///通过红黑树节点找到对应的线性区
    VOID *OsRegionRbGetKeyFn(LosRbNode *pstNode)
    {
        LosVmMapRegion *region = (LosVmMapRegion *)LOS_DL_LIST_ENTRY(pstNode, LosVmMapRegion, rbNode);
        return (VOID *)&region->range;
    }
    ///比较两个红黑树节点
    ULONG_T OsRegionRbCmpKeyFn(const VOID *pNodeKeyA, const VOID *pNodeKeyB)
    {
        LosVmMapRange rangeA = *(LosVmMapRange *)pNodeKeyA;
        LosVmMapRange rangeB = *(LosVmMapRange *)pNodeKeyB;
        UINT32 startA = rangeA.base;
        UINT32 endA = rangeA.base + rangeA.size - 1;
        UINT32 startB = rangeB.base;
        UINT32 endB = rangeB.base + rangeB.size - 1;
    
        if (startA > endB) {// A基地址大于B的结束地址
            return RB_BIGGER; //说明线性区A更大,在右边
        } else if (startA >= startB) {
            if (endA <= endB) {
                return RB_EQUAL; //相等,说明 A在B中
            } else {
                return RB_BIGGER; //说明 A的结束地址更大
            }
        } else if (startA <= startB) { //A基地址小于等于B的基地址
            if (endA >= endB) {
                return RB_EQUAL; //相等 说明 B在A中
            } else {
                return RB_SMALLER;//说明A的结束地址更小
            }
        } else if (endA < startB) {//A结束地址小于B的开始地址
            return RB_SMALLER;//说明A在
        }
        return RB_EQUAL;
    }
    
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
  • 插入结点,注意线性区结构体(VmMapRegion)的首个成员便是红黑树节点,对于红黑树来说线性区只是一个红黑树节点。
    struct VmMapRegion {
      LosRbNode           rbNode;         /**< region red-black tree node | 红黑树节点,通过它将本线性区挂在VmSpace.regionRbTree*/
      // ...
    }
    //插入线性区,指的是向进程的红黑树 `LosRbTree` 插入 `LosRbNode`
    BOOL OsInsertRegion(LosRbTree *regionRbTree, LosVmMapRegion *region)
      {
          if (LOS_RbAddNode(regionRbTree, (LosRbNode *)region) == FALSE) {
              VM_ERR("insert region failed, base: %#x, size: %#x", region->range.base, region->range.size);
              OsDumpAspace(region->space);
              return FALSE;
          }
          return TRUE;
      }
    
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    具体插入过程不去说明,已经是很成熟的算法,通过比较线性区的范围来决定是插入进具体位置,插入过程会涉及到红黑树 颜色翻转左右旋转 两种变化

百文说内核 | 抓住主脉络

  • 百文相当于摸出内核的肌肉和器官系统,让人开始丰满有立体感,因是直接从注释源码起步,在加注释过程中,每每有心得处就整理,慢慢形成了以下文章。内容立足源码,常以生活场景打比方尽可能多的将内核知识点置入某种场景,具有画面感,容易理解记忆。说别人能听得懂的话很重要! 百篇博客绝不是百度教条式的在说一堆诘屈聱牙的概念,那没什么意思。更希望让内核变得栩栩如生,倍感亲切。
  • 与代码需不断debug一样,文章内容会存在不少错漏之处,请多包涵,但会反复修正,持续更新,v**.xx 代表文章序号和修改的次数,精雕细琢,言简意赅,力求打造精品内容。
  • 百文在 < 鸿蒙研究站 | 开源中国 | 博客园 | 51cto | csdn | 知乎 | 掘金 > 站点发布,百篇博客系列目录如下。

按功能模块:

基础知识 进程管理 任务管理 内存管理
双向链表
内核概念
源码结构
地址空间
计时单位
优雅的宏
钩子框架
位图管理
POSIX
main函数
调度故事
进程控制块
进程空间
线性区
红黑树
进程管理
Fork进程
进程回收
Shell编辑
Shell解析
任务控制块
并发并行
就绪队列
调度机制
任务管理
用栈方式
软件定时器
控制台
远程登录
协议栈
内存规则
物理内存
内存概念
虚实映射
页表管理
静态分配
TLFS算法
内存池管理
原子操作
圆整对齐
通讯机制 文件系统 硬件架构 内核汇编
通讯总览
自旋锁
互斥锁
快锁使用
快锁实现
读写锁
信号量
事件机制
信号生产
信号消费
消息队列
消息封装
消息映射
共享内存
文件概念
文件故事
索引节点
VFS
文件句柄
根文件系统
挂载机制
管道文件
文件映射
写时拷贝
芯片模式
ARM架构
指令集
协处理器
工作模式
寄存器
多核管理
中断概念
中断管理
编码方式
汇编基础
汇编传参
链接脚本
内核启动
进程切换
任务切换
中断切换
异常接管
缺页中断
编译运行 调测工具
编译过程
编译构建
GN语法
忍者无敌
ELF格式
ELF解析
静态链接
重定位
动态链接
进程映像
应用启动
系统调用
VDSO
模块监控
日志跟踪
系统安全
测试用例

百万注源码 | 处处扣细节

  • 百万汉字注解内核目的是要看清楚其毛细血管,细胞结构,等于在拿放大镜看内核。内核并不神秘,带着问题去源码中找答案是很容易上瘾的,你会发现很多文章对一些问题的解读是错误的,或者说不深刻难以自圆其说,你会慢慢形成自己新的解读,而新的解读又会碰到新的问题,如此层层递进,滚滚向前,拿着放大镜根本不愿意放手。

  • < gitee | github | coding | gitcode > 四大码仓推送 | 同步官方源码。

关注不迷路 | 代码即人生

  • 互联网从业十五年,计算机硕士,技术副总裁
  • 关注我,持续更新四十年,即聊技术也聊人生
  • 交有趣靠谱的人;做难而正确的事
  • 不做作,不炒作,只唯真
  • 不唯上,不唯书,只唯实

>> 捐助名单

据说喜欢 点赞 + 分享 的,后来都成了大神。😃