实验三:动态内存分配器的实现 助教:吴加禹、李佳伟、唐凯成 田成锦、汪睿、游翎璟
实验三：动态内存分配器的实现 助教：吴加禹、李佳伟、唐凯成 田成锦、汪睿、游翎璟
实验目的 学习内存管理模型与其数据结构 使用显示空闲链表实现一个32位系统堆内存分配器 了解基础的内存管理算法 尝试更高级的内存分配算法(*) 2021/1/26
实验目的 ➢学习内存管理模型与其数据结构 ➢使用显示空闲链表实现一个32位系统堆内存分配器 ➢了解基础的内存管理算法 ➢尝试更高级的内存分配算法（*） 2021/1/26 2
实验环境 主机: Ubuntu32位1404(或其他32位 Ubuntu系统) >本次实验搭载在助教提供的由c构架的一个简易内存管理分 配平台上 下载教学主页上的lab-3基础代码并解压即可开始实验 2021/1/26
实验环境 ➢主机：Ubuntu 32位 14.04 （或其他32位Ubuntu系统） ➢本次实验搭载在助教提供的由c构架的一个简易内存管理分 配平台上 ➢下载教学主页上的lab-3基础代码并解压即可开始实验 2021/1/26 3
实验讲解—1.有关内存管理的AP简介 malloc/free是c标准库函数,用于从堆中分配内存 void* malloc(size t size); malloc函数返回一个指针,指向大小至少为sze字节的空闲 内存块。 返回的内存块首地址是双字对齐的,即在64位系统中地址 为16的倍数,32位系统中为8的倍数。 2021/1/26
实验讲解——1.有关内存管理的API简介 ➢malloc/free是c标准库函数，用于从堆中分配内存 ➢malloc函数返回一个指针，指向大小至少为size字节的空闲 内存块。 ➢返回的内存块首地址是双字对齐的，即:在64位系统中地址 为16的倍数，32位系统中为8的倍数。 2021/1/26 4 void* malloc(size_t size);
实验讲解—1.有关内存管理的AP简介 void sbrk (intptr t incr); 进程的堆内存是有限的,内核维护一个指针brk指向当前堆顶。 >当堆中剩余内存不足以响应 malloc请求时,需要向操作系统 申请更多的堆内存。sbrk函数通过将bk指针增加inc来扩展 和收缩堆(即当incr为负数时收缩堆)。成功时返回旧bk的地 址(因此扩展堆后返回值指向一块大小为incr的空闲内存),失 败时返回 2021/1/26
实验讲解——1.有关内存管理的API简介 ➢进程的堆内存是有限的，内核维护一个指针brk指向当前堆顶。 ➢当堆中剩余内存不足以响应malloc请求时，需要向操作系统 申请更多的堆内存。sbrk函数通过将brk指针增加incr来 扩展 和收缩堆(即当incr为负数时收缩堆)。成功时返回旧brk的地 址(因此扩展堆后返回值指向一块大小为incr的空 闲内存)，失 败时返回-1。 2021/1/26 5 void *sbrk(intptr_t incr);
实验讲解—1.有关内存管理的AP简介 void free(void *ptr)i fre函数释放ptr指向的内存块,释放出的内存可以在之后的 malloc调用中被使用。 注意pt必须指向由 malloc. calloc、 realloc分配的内存块的 起始位置。 2021/1/26
实验讲解——1.有关内存管理的API简介 ➢free函数释放ptr指向的内存块，释放出的内存可以在之后的 malloc调用中被使用。 ➢注意:ptr必须指向由malloc、calloc、realloc分配的内存块的 起始位置。 2021/1/26 6 void free(void *ptr);
实验讲解—2隐式空闲链表管理 隐式空闲链表 隐式空闲链表将堆中的内存块按地址顺序串成一个链表,接受到内 存分配请求时,分配器遍历该链表来找到合适的空闲内存块并返回。 当找不到合适的空闲内存块时(如堆内存不足,或没有大小足够的 空闲内存块),调用Sbk向堆顶扩展更多的内存。 未使用的 堆的 双字 起始 8/0 16/l 320 对齐的 ■图中淡蓝色部分为已分配块,深蓝色为填充块(为了内存双字对齐 数字为块头部。 2021/1/26
实验讲解——2.隐式空闲链表管理 ➢隐式空闲链表 ◼ 隐式空闲链表将堆中的内存块按地址顺序串成一个链表，接受到内 存分配请求时，分配器遍历该链表来找到合适的空闲内存块并返回。 ◼ 当找不到合适的空闲内存块时(如:堆内存不足，或没有大小足够的 空闲内存块)，调用sbrk向堆顶扩展更多的内存。 ◼ 图中淡蓝色部分为已分配块，深蓝色为填充块(为了内存双字对齐)， 数字为块头部。 2021/1/26 7
实验讲解—2隐式空闲链表管理 >块头部表 ■堆中的各内存块需要某种标志来区分块的边界,记录块的大小,以 及标记该内存块是否已被使用。因此为每个内存块保留一个字(4字 节)的头部记录这些数据。 块头部记录了该内存块的大小。由于内存块以8字节对齐,块大小 二进制的最低3位一定为0,因此可以用最后一位来标记该块是否已 被分配。 31头部 210 ma1loc返回一个指针, 块大小 a=1:已分配的 00a a=0:空闲的 它指向有效载荷的开始处 有效载荷 块大小包括头部 (只包括已分配的块) 有效载荷和所有的填充 填充(可选) 个简单的堆块的格式 2021/1/26
实验讲解——2.隐式空闲链表管理 ➢块头部表 ◼ 堆中的各内存块需要某种标志来区分块的边界，记录块的大小，以 及标记该内存块是否已被使用。因此为每个内存块保留一个字(4字 节)的头部记录这些数据。 ◼ 块头部记录了该内存块的大小。由于内存块以8字节对齐，块大小 二进制的最低3位一定为0，因此可以用最后一位来标记该块是否已 被分配。 2021/1/26 8
实验讲解—2隐式空闲链表管理 >链表管理 在隐式链表管理方案下,分配器维护一个指针 heap listp指向堆 中的第一个内存块,也即链表中的第一个块。 ■根据该内存块头部中记录的块大小信息便可计算出下一块的位置 heap listptsIze ),依此类推 >放置策略 当请求一个k字节的内存块时,分配器需要搜索堆中的内存块找 到一个足够大的空闲块并返回。具体选择哪一个内存块由放置 策略决定。主要有两种 首次适配∶从头开始搜索链表,找到第一个大小合适的空闲内存 块便返回。 最佳适配∶搜索整个链表,返回满足需求的最小的空闲块。 两者相比较,首次适配速度较快,最佳适配内存利用率更高。后 面的实现采用首次适配方法。 2021/1/26
实验讲解——2.隐式空闲链表管理 ➢链表管理 ◼ 在隐式链表管理方案下，分配器维护一个指针heap_listp指向堆 中的第一个内存块，也即链表中的第一个块。 ◼ 根据该内存块头部中记录的块大小信息便可计算出下一块的位置 (heap_listp+size)，依此类推。 ➢放置策略 ◼ 当请求一个k字节的内存块时，分配器需要搜索堆中的内存块找 到一个足够大的空闲块并返回。具体选择哪一个内存块由放置 策略决定。主要有两种: ⚫ 首次适配：从头开始搜索链表，找到第一个大小合适的空闲内存 块便返回。 ⚫ 最佳适配：搜索整个链表，返回满足需求的最小的空闲块。 ◼ 两者相比较，首次适配速度较快，最佳适配内存利用率更高。后 面的实现采用首次适配方法。 2021/1/26 9
实验讲解—2隐式空闲链表管理 分割空闲块 当分配器找到一个合适的空闲块后,如果空闲块大小大于请求的内 存大小,则需要分割该空闲块,避免内存浪费。 具体步骤为 修改空闲块头部,将大小改为分配的大小,并标记该块为已分配。 为多余的内存添加一个块头部,记录其大小并标记为未分配,使其成 为一个新的空闲内存块。 返回分配的块指针 未使用的 堆的 双字 起始 8/0 16/l 320 l6/1 位置 对齐的 未使用的 堆的 8/0 16/1l 16/1 6 双字 起始 160 位置 对齐的 2021/1/26
实验讲解——2.隐式空闲链表管理 ➢分割空闲块 ◼ 当分配器找到一个合适的空闲块后，如果空闲块大小大于请求的内 存大小，则需要分割该空闲块，避免内存浪费。 ◼ 具体步骤为: ⚫ 修改空闲块头部，将大小改为分配的大小，并标记该块为已分配。 ⚫ 为多余的内存添加一个块头部，记录其大小并标记为未分配，使其成 为一个新的空闲内存块。 ⚫ 返回分配的块指针。 2021/1/26 10