77 lines
2.6 KiB
Markdown
77 lines
2.6 KiB
Markdown
# 动态内存分配器实验修改思路
|
||
|
||
## 实验目标
|
||
实现一个动态内存分配器，支持以下功能：
|
||
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`，并提交到指定平台。
|