济南网站建设要多少钱,什么网站可以兼职做平面设计,什么是域名访问网站,重庆建设空调网站目录前言分区式内存管理动态分区内存管理总结本笔记参考黄工的https://mp.weixin.qq.com/s/k0W_LqI1zBAYC1GU1U2HQA
前言
内存管理模块主要负责内存的初始化、分配以及释放。 从分配内存是否连续可以分为两大类#xff1a;
1、连续内存管理 为进程分配的内存空间是连续的
1、连续内存管理 为进程分配的内存空间是连续的但这种分配方式容易形成内存碎片降低内存利用率。连续内存管理主要分为单一连续内存管理和分区内存管理两种。2、非连续内存管理 将进程分散到多个不连续的内存空间种可以减少内存碎片内存使用率更高。如果分配的基本单位是页则称为分页式内存管理如果基本单位式段则称为分段式内存管理
目前的OS主要采用非连续内存管理。对于内存较小的嵌入式系统一般采用连续内存管理。 这里详细讲解连续内存管理的分区式内存管理当然了解相关原理后也可以用于自己构建相关内存池。
分区式内存管理
分区式内存管理分为固定分区和动态分区
固定分区 事先就把内存划分为若干个固定大小的区域。分区大小既可以相等也可以不等。固定分区易于实现但是会造成分区内碎片浪费而且分区总数固定限制了可以并发执行的进程数动态分区 根据进程的实际需要动态地给进程分配所需内存
动态分区内存管理
运作机制 动态分区管理一般采用空闲链表法即基于一个双向链表来保存空闲分区。对于初始状态整个内存块都会被作为一个大的空闲分区加入到空闲链表中。当进程申请内存时将会从这个空闲链表种找到一个大小满足要求地空闲分区。如果分区大于所需内存则从该分区中拆分出需求大小地内存交给进程并将此拆分出的内存从空闲链表中移除剩下的内存仍然是一个挂在空闲链表上的空闲分区。 数据结构 空闲链表法有多种数据结构实现方式这里介绍一种较为简单的数据结构。每个空闲分区的数据结构中包含分区大小以及指向前一个分区和后一个分区的指针这样就能将各个空闲分区链接成一个双向链表。
内存分配算法
First Fit首次适应算法 First Fit要求空闲分区链表以地址从小到大顺序链接。分配内存时从链表的第一个空闲分区开始查找将最先能够满足要求的空闲分区分配给进程。Next Fit循环首次适应算法 该算法由FF算法演变而来。分配内存时从上一次刚分配过的空闲分区的下一个开始查找直到找到能满足要求的空闲分区。查找时会采用循环查找的方式即如果直到链表最后一个空闲分区都不满足则返回到第一个空闲分区开始查找Best Fit最佳适应算法 从所有空闲分区中找到能满足要求的、且大小最小的空闲分区。为了加快查找速度BF算法会把所有空闲分区按其容量从小到大的顺序链接起来这样第一次找到的满足大小要求的内存必然是最小的空闲分区 与此相反的有个Worst Fit最坏适应算法它是找到大小最大的空闲分区然后按照容量从大到小顺序链接所有空闲分区块Two LevelSegregated FitTLSF 使用两层链表来管理空闲内存将空闲分区大小进行分类 每个类用一个空闲链表表示其中空闲内存大小都在某个特定值或者范围内。这样存在多个空闲链表所以又用一个索引链表来管理这些空闲链表该表的每一项都对应一种空闲链表并记录该类空闲链表的表头指针。 第一层链表将空闲块的大小根据2的幂次进行分类。 第二层链表是具体的每一类空闲内存块按照一定的范围进行线性分段 同时为了快速检索到空闲块每一层链表都有一个bitmap用于标记对应的链表中是否有空闲块。 如第一层bitmap后三位010表示2^5这一类内存区间有空闲块。对应的第二层bitmap为0100表示【25162524这个区间有空闲块伙伴算法 该算法为TLSF算法的变种具有更好的内存拆分和回收合并效率。 伙伴算法有很多种类比如BinaryBuddies、Fibonacci Buddies等。Binary Buddies是最简单也是最流行的一种。 将所有空闲分区根据分区的大小进行分类每一类都是具有相同大小的空闲分区的集合使用一个空闲双向链表表示。BinaryBuddies中所有的内存分区都是2的幂次方。 无论是已分配还是空闲的分区其大小都是2的幂次方即使进程申请的内存小于分配给它的内存块多余的内存也不会再拆分出来给其他进程使用这样就容易造成内部碎片。 当进程申请一块大小为n的内存时的分配步骤为 1、计算一个i值使得2 ^ i-1 n ≤2 ^ i 2、在空闲分区大小为2 ^ i 的空闲链表中查找 3、如果找到空闲块则分配给进程 4、如果2 ^ i的空闲分区已经耗尽则在分区大小为2 ^ i1的空闲链表中查找 5、如果存在2 ^i1 的空闲分区则将此空闲块分为相等的两个分区 这两个分区就是一对伙伴其中一块分配给进程另一块挂到分区大小为2 ^ i的空闲链表中 6、如果2 ^ i1 的空闲分区还是不存在则继续查找大小为2 ^ i2 的空闲分区。如果找到需要进行两次拆分。第一次拆分为两块大小为2 ^ i1的空闲分区一块挂到2 ^ i1的空闲链表中另一块分区继续拆分为两块大小为2 ^ i的空闲分区一块分配给进程另一块挂到大小为2 ^ i的空闲链表中 7、如果2 ^ i2的空闲分区也找不到则继续查找2 ^ i3依次类推 在内存回收时如果待回收的内存块与空闲链表中的一块内存互为伙伴则将它们合并为一块更大的内存块。如果合并后的内存块在空闲链表中还有伙伴则继续合并到不能合并为止并将合并后的内存块挂到对应的空闲链表中
总结
