csapp2025/malloclab/method.md

动态内存分配器实验修改思路

实验目标

实现一个动态内存分配器，支持以下功能：

1. 内存分配（mm_malloc）
2. 内存释放（mm_free）
3. 内存扩展（mm_realloc）

并通过 traces 目录下的测试用例，尽可能提高评分。

修改内容

1. 算法设计思想

• 使用 隐式空闲链表 管理内存块。
• 每个块包含头部和尾部，用于存储块大小和分配状态。
• 分配时，使用 首次适配算法 找到合适的空闲块。
• 释放时，合并相邻的空闲块以减少内存碎片。
• 通过对齐和块分割优化内存利用率。

2. 代码实现

主要宏定义

• PACK(size, alloc)：将块大小和分配位打包成一个字。
• GET 和 PUT：读取和写入地址处的字。
• HDRP 和 FTRP：计算块的头部和尾部地址。
• NEXT_BLKP 和 PREV_BLKP：计算下一个和前一个块的地址。

核心函数

1. mm_init

   • 初始化堆，创建序言块和结尾块。
   • 扩展堆以初始化空闲块。

2. extend_heap

   • 扩展堆的大小，分配新的空闲块。
   • 初始化新块的头部、尾部和结尾块。

3. coalesce

   • 合并相邻的空闲块，减少内存碎片。
   • 根据前后块的分配状态，处理 4 种情况。

4. mm_malloc

   • 调整请求大小以满足对齐要求。
   • 使用 find_fit 查找合适的空闲块。
   • 如果没有合适的块，扩展堆。

5. mm_free

   • 将块标记为空闲。
   • 调用 coalesce 合并相邻空闲块。

6. mm_realloc

   • 如果新大小小于当前块大小，直接返回。
   • 如果新大小大于当前块大小，分配新块并复制数据。

7. find_fit

   • 遍历隐式链表，找到第一个满足大小要求的空闲块。

8. place

   • 将请求大小的块放入空闲块中。
   • 如果剩余空间足够大，分割块。

3. 测试与优化

• 修改 TRACE_LIST.txt，运行不同的 trace 文件。
• 使用 make 和 ./malloc -t traces 测试实现。
• 优化分配和释放逻辑，提高效率和性能。

当前状态

• 正确性：所有 trace 文件均通过测试。
• 效率：平均效率为 77%。
• 性能：评分为 84/100。

后续优化方向

1. 使用 显式空闲链表 或 分离空闲链表 提高查找效率。
2. 动态调整堆扩展策略，减少不必要的扩展。
3. 优化块分割和合并逻辑，进一步减少内存碎片。

提交要求

• 将 mm.c 文件重命名为 mm_学号.c，并提交到指定平台。