基于C语言的动态内存分配器.zip

# 基于C语言的动态内存分配器 # 一、实验基本信息 ### 实验目的 理解现代计算机系统虚拟存储的基本知识 掌握 C 语言指针相关的基本操作 深入理解动态存储申请、释放的基本原理和相关系统函数 用 C 语言实现动态存储分配器，并进行测试分析 培养 Linux 下的软件系统开发与测试能力 ### 实验环境与工具 硬件环境 CPU；2GHz；2G RAM；256GHD Disk 以上 软件环境 Windows7 64 位以上；VirtualBox/Vmware 11 以上；Ubuntu 16.04 LTS 64 位/优麒麟 64 位 开发工具 clion # 二、实验预习 总分 20 分 动态内存分配器的基本原理（5 分） 动态内存分配器维护者一个进程的虚拟内存区域堆，每个块就是一个连续的虚拟内存片，已分配的块显式的保留为供应用程序使用，空闲块可用来分配。空闲块保持空闲，直到它显示的被应用所分配。一个已分配的块保持已分配的状态，直到它被释放，这种释放要么是应用程序显式执行的，要么是内存分配器自身隐式执行的。 带边界标签的隐式空闲链表分配器原理（5 分） 一个块是由一个字的头部、有效载荷，以及可能的一些额外的填充组成的，头部编码了这个快的大小，以及这个块是已分配的还是空闲的。每进行一个操作，就需要链表进行一次搜索，如果要分配内存，就找到大小符合的块进行分配，，如果要释放，就将头部和尾部的信息修改为空闲，然后搜索相邻的块进行合并成一个大块。 显示空间链表的基本原理（5 分） 在每个空闲块里都包含一个 pred(前驱)和后继指针，形成一个双向链表，是的首次适配的分配时间从块总数的线性时间减少到了空闲块数量的线性时间。 红黑树的结构、查找、更新算法（5 分） 结构： 每个节点或者是黑色，或者是红色。 根节点是黑色。 每个叶子节点（NIL）是黑色。 如果一个节点是红色的，则它的子节点必须是黑色的。 从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点。 查找： 与普通二叉树的查找方法相同。 更新： 插入：将新插入的节点标记为红色并按照普通二叉树的插入方法插入到红黑树中，然后对树进行调整使其重新满足红黑树的 5 条性质，具体调整方案如下： 情形 1:新节点 N 位于树的根上，没有父节点。在这种情形下，我们把它重绘为黑色以满足性质 2。因为它在每个路径上对黑节点数目增加一，性质 5 匹配。 情形 2:新节点的父节点 P 是黑色，所以性质 4 没有失效（新节点是红色的）。在这种情形下，树仍是有效的。性质 5 也未受到威胁，尽管新节点 N 有两个黑色叶子子节点；但由于新节点 N 是红色，通过它的每个子节点的路径就都有同通过它所取代的黑色的叶子的路径同样数目的黑色节点，所以依然满足这个性质。 情形 3:如果父节点 P 和叔父节点 U 二者都是红色，则我们可以将它们两个重绘为黑色并重绘祖父节点 G 为红色（用来保持性质 5）。现在我们的新节点 N 有了一个黑色的父节点 P。因为通过父节点 P 或叔父节点 U 的任何路径都必定通过祖父节点 G，在这些路径上的黑节点数目没有改变。但是，红色的祖父节点 G 可能是根节点，这就违反了性质 2，也有可能祖父节点 G 的父节点是红色的，这就违反了性质 4。为了解决这个问题，我们在祖父节点 G 上递归地进行情形 1 的整个过程。（把 G 当成是新加入的节点进行各种情形的检查） 情形 4:父节点 P 是红色而叔父节点 U 是黑色或缺少，并且新节点 N 是其父节点 P 的右子节点而父节点 P 又是其父节点的左子节点。在这种情形下，我们进行一次左旋转调换新节点和其父节点的角色;接着，我们按情形 5 处理以前的父节点 P 以解决仍然失效的性质 4。注意这个改变会导致某些路径通过它们以前不通过的新节点 N 或不通过节点 P，但由于这两个节点都是红色的，所以性质 5 仍有效。 情形 5：父节点 P 是红色而叔父节点 U 是黑色或缺少，新节点 N 是其父节点的左子节点，而父节点 P 又是其父节点 G 的左子节点。在这种情形下，我们进行针对祖父节点 G 的一次右旋转；在旋转产生的树中，以前的父节点 P 现在是新节点 N 和以前的祖父节点 G 的父节点。我们知道以前的祖父节点 G 是黑色，否则父节点 P 就不可能是红色（如果 P 和 G 都是红色就违反了性质 4，所以 G 必须是黑色）。我们切换以前的父节点 P 和祖父节点 G 的颜色，结果的树满足性质 4。性质 5 也仍然保持满足，因为通过这三个节点中任何一个的所有路径以前都通过祖父节点 G，现在它们都通过以前的父节点 P。在各自的情形下，这都是三个节点中唯一的黑色节点。 删除：仅讨论最复杂的要删除的节点和它的儿子二者都是黑色的情况，我们首先把要删除的节点替换为它的儿子。出于方便，称呼这个儿子为 N（在新的位置上），称呼它的兄弟（它父亲的另一个儿子）为 S。我们还是使用 P 称呼 N 的父亲，SL 称呼 S 的左儿子，SR 称呼 S 的右儿子。 情形 1: N 是新的根。在这种情形下，我们就做完了。我们从所有路径去除了一个黑色节点，而新根是黑色的，所以性质都保持着。 情形 2： S 是红色。在这种情形下我们在 N 的父亲上做左旋转，把红色兄弟转换成 N 的祖父，我们接着对调 N 的父亲和祖父的颜色。完成这两个操作后，尽管所有路径上黑色节点的数目没有改变，但现在 N 有了一个黑色的兄弟和一个红色的父亲（它的新兄弟是黑色因为它是红色 S 的一个儿子），所以我们可以接下去按情形 4、情形 5 或情形 6 来处理。 情形 3： N 的父亲、S 和 S 的儿子都是黑色的。在这种情形下，我们简单的重绘 S 为红色。结果是通过 S 的所有路径，它们就是以前不通过 N 的那些路径，都少了一个黑色节点。因为删除 N 的初始的父亲使通过 N 的所有路径少了一个黑色节点，这使事情都平衡了起来。但是，通过 P 的所有路径现在比不通过 P 的路径少了一个黑色节点，所以仍然违反性质 5。要修正这个问题，我们要从情形 1 开始，在 P 上做重新平衡处理。 情形 4： S 和 S 的儿子都是黑色，但是 N 的父亲是红色。在这种情形下，我们简单的交换 N 的兄弟和父亲的颜色。这不影响不通过 N 的路径的黑色节点的数目，但是它在通过 N 的路径上对黑色节点数目增加了一，添补了在这些路径上删除的黑色节点。 情形 5： S 是黑色，S 的左儿子是红色，S 的右儿子是黑色，而 N 是它父亲的左儿子。在这种情形下我们在 S 上做右旋转，这样 S 的左儿子成为 S 的父亲和 N 的新兄弟。我们接着交换 S 和它的新父亲的颜色。所有路径仍有同样数目的黑色节点，但是现在 N 有了一个黑色兄弟，他的右儿子是红色的，所以我们进入了情形 6。N 和它的父亲都不受这个变换的影响。 情形 6： S 是黑色，S 的右儿子是红色，而 N 是它父亲的左儿子。在这种情形下我们在 N 的父亲上做左旋转，这样 S 成为 N 的父亲（P）和 S 的右儿子的父亲。我们接着交换 N 的父亲和 S 的颜色，并使 S 的右儿子为黑色。子树在它的根上的仍是同样的颜色，所�