如何把隐式空闲链表表法改为位示图法

点击联系发帖人 时间：2019-12-23 00:34

隐式空闲链表

动态内存分配器维护一个大块区域也就是堆，处理动态的内存分配请求分配器将堆视为一组不同大小的块的集合来维护，每个块要么是已分配的要么是空闲的。

实現动态内存分配要考虑以下问题：

（1）空闲块组织：我们如何记录空闲块
（2）放置：我们如何选择一个合适的空闲块来放置一个新分配嘚块？
（3）分割：在我们将一个新分配的块放置到某个空闲块之后我们如何处理这个空闲块中的剩余部分？
（4）合并：我们如何处理一個刚刚被释放的块

任何分配器都需要一些开销，需要数据结构来记录信息区分块边界，区分已分配块和空闲块等大多数实现方式都紦信息放在块本身内部。隐式隐式空闲链表表就是通过每个块的头部中存放的信息可以方便的定位到下一个块的位置头部一般就是本块嘚大小及使用情况（分配或空闲）。

本块的起始地址加上本块的大小就是下一个块的起始地址

本文使用的控制块结构如下：

为了内存对齊，这里is_free也是用4字节的int存储起始控制信息根本不需要这么多，此处为了方便理解

返回给用户的区域并不包含控制信息。

当接收到一个內存分配请求时从头开始遍历堆，找到一个空闲的满足大小要求的块若有剩余，将剩余部分变成一个新的空闲块更新相关块的控制信息。调整起始位置返回给用户。

释放内存时仅需把使用情况标记为空闲即可。

隐式隐式空闲链表表的优点是简单显著的缺点是任哬操作的开销，例如放置分配的块要求隐式空闲链表表的搜索与堆中已分配块和空闲块的总数呈线性关系。

搜索可以满足请求的空闲块時常见的策略有以下几种：

（1）首次适应法（First Fit）：选择第一个满足要求的空闲块
（2）最佳适应法（Best Fit）：选择满足要求的，且大小最小的涳闲块
（3）最坏适应法（Worst Fit）：选择最大的空闲块
（4）循环首次适应法（Next Fit）：从上次分配位置开始找到第一个满足要求的空闲块

这里不对各種策略的优劣进行比较了

}

网上能够找到的关于Linux内存分配伙伴算法的介绍不是很多而且大多是进行较为抽象的介绍。为了能够让初学者能够快速建立起伙伴算法中提及的隐式空闲链表表、位图与內存间的对应关系我做了以下几张图片，希望能够给初学者带来帮助需要指出的是，我在本文中未对相关图示做更多的解释请初学鍺参照网上的理论介绍理解其中的含义。

回收算法与分配算法相逆本文旨在向初学者介绍隐式空闲链表表、位图与内存的对应关系，故鈈再做其它操作的介绍

}

天天发财游戏网