大邑县建设局网站,哪个网站做简历免费,庐江网站制作,百度如何搜索到自己的网站一、实验要求
优化TLSF算法#xff0c;将Best-fit策略优化为Good-fit策略#xff0c;进一步降低时间复杂度至O(1)。
优化思路#xff1a;
1.初始化时预先为每个索引中的内存块挂上若干空闲块#xff0c;在实际分配时避免分割#xff08;split#xff09;操作#xff…一、实验要求
优化TLSF算法将Best-fit策略优化为Good-fit策略进一步降低时间复杂度至O(1)。
优化思路
1.初始化时预先为每个索引中的内存块挂上若干空闲块在实际分配时避免分割split操作加速分配过程
2.定位到比当前所需空间更大一级的内存块进行空闲块分配避免因遍历链表寻找合适大小的空闲块所导致的时间浪费。
为了严谨起见先规范一下术语注意概念的大小索引内存块空闲块。绿色是小桶紫色是大桶 二、实验准备
第1步下载带有TLSF算法的源码
在这里下载OpenHarmony 1.1.0 LTS实测内部含有内存两级分割策略算法TLSF算法的代码实现repo地址如下
repo init -u https://gitee.com/openharmony/manifest.git -b refs/tags/OpenHarmony_release_v1.1.0 --no-repo-verify 原本的想法是要编写一个程序来验证新内存分配算法的正确性但由于补丁只能打1.0版本而这个是1.1版本抱有侥幸心理试试补丁能不能打1.x版本于是下载了这个版本事实证明补丁依旧不能打上..
在openharmony/kernel/liteos_a/kernel/base/mem下有一个tlsf文件夹这个文件夹里存储的正是tlsf算法的实现 进入到tlsf文件夹下的los_memory.c文件中。
第2步查看结构体 图中的结构体如下
OsMemPoolInfo OsMemFreeNodeHead OsMemNodeHead OsMemUsedNodeHead 第3步检查常用宏 宏的含义可参考ppt。
第4步理解TLSF算法
TLSF算法采用的是两级索引。右边的是第一级索引将空间按2的指数大小...进行分块。其内部的内存块是否空闲用位图(一维数组)进行标识1表示块内有剩余空间0表示块内已经被挤得满满的。 中间的是第二级索引二级索引在一级索引分块的基础上进一步进行分块如图中将一级索引中的每块进一步分成了8块例如32-63这段被分为了32-35,36-39,40-43,44-47,48-51,52-55,56-59,60-63每块长度是4。用位图(二维数组)标识是否存在空闲内存块。有空闲的块标记为1没有空闲的块标记为0。
左边的是空闲块空闲块的大小是一个确定的值该值要在二级索引的区间范围之内。 上图告诉我们鸿蒙系统将内存块大小分为两个部分~和~。
在4~127区间上是小桶申请可以这么理解在4~127区间上有31个桶4812...124每个桶的大小代表了所能挂的空闲块的大小比如12代表只能挂12B大小的空闲块120代表只能挂120B大小的空闲块没有二级索引。
大于127的是大桶申请可以这么理解一共有24个大桶~~... ~这里的大桶代表了一级索引然后每个大桶里又有8个小桶这里的小桶代表2级索引然后每个小桶里又可以挂若干个空闲块。
三、改进TLSF算法
事先说明
1. 修改不保证完全正确如有疏漏望请指正。
2. 所修改的函数都在openharmony/kernel/liteos_a/kernel/base/mem/tlsf下的los_memory.c文件中。
3.所修改的源码是OpenHarmony 1.1.0 LTS版本其它版本可能会有所差异。
1.定位到比当前所需空间更大一级的内存块
修改对象OsMemFreeListIndexGet函数
改进思路在当前内存块位置的基础上1指向下一块内存块的位置需要考虑的是1后从小桶变成大桶的情况所以当size124时归属于小桶当size124时归属于大桶。
修改如下 首先复制OsMemFreeListIndexGet这个函数粘贴到原函数下面改名为NewOsMemFreeListIndexGet然后就不再变动NewOsMemFreeListIndexGet这个函数。
fl的值表示的是在一级索引中的位置OS_MEM_SMALL_BUCKET_MAX_SIZE是一个宏其值为128如果size124就让fl1相当于索引指向当前桶的上一级桶。
如果size124此时考虑临界状态当size为124时再上一级桶时4后会进入到大桶的范围因为小桶的最大上界为127所以此时会返回newFl。
newFl会进入到OsMemSlGet函数这个函数的作用是返回某个值在二级索引中的位置详见第四部分所以sl的值代表了size在二级索引中的位置。
此时我们让sl1就相当于指向了下一个位置的二级索引最后这里return的这一长串数很巧妙同样详见第2部分。
为什么要这么修改呢原因因为OsMemFreeListIndexGet这个函数的作用是返回要插入空闲块的内存块位置我们为了在一般情况下默认定位到比当前所需空间更大一级的内存块进行空闲块插入所以对OsMemFreeListIndexGet这个函数进行修改。
在特殊情况下比如初始化时预先为每个索引挂上若干空闲块要求12B就是为大小为12的内存块预先挂上空闲块因此设定仍按准确的大小定位。 2.初始化时预先为每个内存块挂上若干空闲块
修改对象OsMemPoolInit函数、OsMemFreeNodeAdd函数
修改思路在初始化内存池的时候同时为内存块挂上空闲块。人为给出要预先为哪些索引上的内存块挂上空闲块内存块的大小用sizeArray给出然后为OsMemNodeHead结构体的变量freeNode赋值进行初始化存储逻辑上用双向链表进行连接索引逻辑上通过NewOsMemFreeNodeAdd函数将特定大小的空闲块挂载到内存块上。
修改如下 OsMemPoolInit这个函数是用于初始化内存池的可以在该函数中预先挂上空闲块。
首先我定义了一个名为currentNode的OsMemNodeHead结构体指针指向的是初始节点newNode的末尾即后续空闲的线性空间的开头用于存储新的结构体和空闲块。
preveNode的作用是要记录前驱节点方便后续双向链表的构建。
然后我定义了n和sizeArray这里是用于指定想要在哪个桶上挂空闲块比如12代表想要在大小为12B的桶上挂空闲块可以根据自己的需要将空闲块挂到其它桶上只需修改size的值即可。
在for循环里主要就是给freeNode结构体内的参数赋值freeNode指向的是newNode的末尾地址即未被占用的线性空间开头的位置。
如果i0前驱节点要指向newNode如果i0此时preveNode的作用就凸显出来freeNode当前节点的前驱就指向preveNode前一个节点。
然后调用NewOsMemFreeNodeAdd函数这个函数主要是将结构体插入到索引当中。
preveNode freeNode是令前一个节点指向当前节点。
最后一行是令currentNode指向后续空闲空间的起始位置方便添加新的结构体。 在OsMemPoolInit函数中调用到NewOsMemFreeNodeAdd这个函数这个函数原名是OsMemFreeNodeAdd只需在前面加上New即可然后这里就和本节1中修改的NewOsMemFreeListIndexGet函数联系在一起。
四、源码解析修改逻辑分析
1.定位到比当前所需空间更大一级的索引
首先我们分析一下OsMemFlGet这个函数调用逻辑是OsMemFlGet-OsMemLog2-OsMemFLS- 我们直接看OsMemFLS函数OS_MEM_BITMAP_MASK是一个宏定义代表数310到31共计32位因为操作系统是32位的。
CLZ是“Count Leading Zeros”的缩写用于统计二进制数前导0的个数比如一个32位的数0000010100...前导0有5个。
OS_MEM_BITMAP_MASK-CLZ(bitmap)是计算第1个“1”所在的位置比如上面举例的32位数0000010100...前导0有5个用31-5得到的就是该数最高位的“1”所在的位置是26这个的用处就是去定位这个数是在哪一个一级索引里比如上面那个数最后会被放在2^26~2^27-1这个一级索引里参考下面的图来理解 接下来我们看OsMemSlGet函数OS_MEM_SLI是一个宏定义值为3OS_MEM_FREE_LIST_NUM是13即值为8。
size OS_MEM_SLI是将size扩大8倍(size OS_MEM_SLI)fl是将乘8后的size再除以2^fl倍这个的目的是得到二级索引的值不至于移除低位导致精度缺失比如对于数111000000fl即一级索引是8如果不乘8此时将该数右移8位结果为1明显不对而乘8后右移8位结果为1110十进制为14此时减8结果为6表明该数在一级索引中是2^9~2^10-1在二级索引中排在第6个块中。 最后解释一下return的这段代码的含义我首先各处各个变量代表的含义OS_MEM_SMALL_BUCKET_COUNT31代表小桶一共被分为31个区间。OS_MEM_LARGE_START_BUCKET72^7128即大桶开始的位置。sl返回的是2级索引的值。fl是1级索引的值。
然后我们看表达式fl - OS_MEM_LARGE_START_BUCKET表达式的含义是size所处的一级索引位置减去大桶开始的位置如下图1 fl - OS_MEM_LARGE_START_BUCKET) OS_MEM_SLI是将上图中那部分一级索引的个数乘以8为什么要乘以8因为每个一级索引大桶对应有8个二级索引块所以是计算出二级索引块的个数。
OS_MEM_SMALL_BUCKET_COUNT ((fl - OS_MEM_LARGE_START_BUCKET) OS_MEM_SLI)意思是在前面二级索引块数的基础上再加上一级索引块的数量因为128的一级索引属于小桶范畴不具备二级索引如上图2所以直接加上即可。
OS_MEM_SMALL_BUCKET_COUNT ((fl - OS_MEM_LARGE_START_BUCKET) OS_MEM_SLI) sl就是把所有的小桶大桶的二级索引块全部加上然后加上sl自身这个块的偏移量就能够定位到要在哪个大桶的二级索引块上加入空闲块。
2.初始化时预先为每个索引挂上若干空闲块
首先看osmempoolinit的函数主要要关注poolHead,newNode,endNode的结构体这个大家自己看了。
然后要注意newNode OS_MEM_FIRST_NODE(pool)和endNodeOS_MEM_END_NODE(pool,size)这两个函数对应的是一段计算公式计算的是起始地址和结束地址endNode标记的是末尾结点。
再然后要关注OsMemFreeNodeAdd这个函数只有理清了这个函数才能真正理解是如何为每个桶挂上空闲块的。 1.分析OsMemPoolHead和OsMemNodeHead结构体
poolHead - OsMemPoolHead
newNode、endNode - OsMemNodeHead
OsMemPoolHead包含了OsMemPoolInfo结构体其中freeList表示索引列表 OS_MEM_FREE_LIST_COUNT小桶31个 大桶24个x 8 223个 从这里可以看出对于小桶128是给每个一级索引分配一个链表对于大桶是给每个二级索引分配一个链表链表可以在后续挂载空闲块。
OsMemFreeNodeHead包含了OsMemNodeHead结构体 2.OS_MEM_FIRST_NODE(pool)和OS_MEM_END_NODE(pool,size)
OS_MEM_FIRST_NODE是一段宏定义用于指明第1个结点的起始位置。pool是内存池的起始位置sizeof(struct OsMemPoolHead)是内存池的头的长度第1个结点从内存池头后开始。 OS_MEM_FIRST_NODE是一段宏定义用于指明最后1个结点的起始位置。因为size代表的是整个内存池的大小OS_MEM_NODE_HEAD_SIZE相当于就是endNode本身的结构体OsMemNodeHead大小所以整个式子的含义就是指向刚好容纳最后一个节点的起始位置。 3.OsMemFreeNodeAdd函数
OsMemFreeNodeAdd函数的作用是将空闲块挂载到对应索引的内存块上。
首先进入到OsMemFreeNodeAdd函数后会调用OsMemFreeListIndexGet函数这就是我们前面的函数用于返回对应索引的内存块位置。
然后会调用OsMemListAdd函数freeList就是内存池pool中的索引然后会根据listIndex的值将空闲块挂在到该索引上。 【到此为止源码分析就结束了如果觉得有帮助记得点赞收藏吧】
下面补充内存池知识点
OsMemPoolInit函数用来初始化一个内存池。
内存池Memory Pool是一个用于管理内存分配的系统它预先分配一块大的内存区域并将其划分为小块以供程序使用。这样做的好处包括减少内存碎片、提高内存分配效率和简化内存管理。
一二级索存在于内存池中是内存池中的数据结构它们用于快速定位和管理内存块。
在一个系统中会有多个内存池比如用户空间和内核空间的内存池。操作系统的内存不仅由内存池构成还包括页表、段表等内存池只适用特定场景。空闲块是由内存池中的索引结构组织。
