first-fit算法用结构体数组实现,每个元素含start、size、free字段;分配时顺序扫描并拆分空闲块,回收时定位并合并相邻空闲区,变量归属通过地址反查已分配块确定。

First-Fit 算法用数组实现,核心是模拟“从头找第一个够用的空闲块”,不依赖链表也能跑通逻辑,适合教学、嵌入式小系统或快速验证场景。关键在于:数组要能表达空闲块的位置和大小,分配时顺序扫描,回收后需手动维护连续性(合并相邻空闲块)。
数组怎么存空闲块信息
用二维数组或结构体数组均可,推荐结构体数组,语义清晰:
- 每个元素含 start(起始地址)、size(大小)、free(是否空闲)三个字段;
- 初始化时把整段内存设为一个大空闲块,例如
{start: 0, size: 4096, free: True}; - 数组长度固定(如 32 或 64),代表最多支持多少个内存块(已分配 + 空闲);
- 不存 end_address,避免冗余——end 可由
start + size算出,更新时不易出错。
分配过程:顺序扫描 + 拆分判断
当请求大小为 req_size 时:
- 从索引 0 开始遍历数组,跳过已分配项(
free == False); - 对首个
free == True 且 size >= req_size的块执行分配; - 若
size - req_size (如 16 字节),整块分配,设 <code>free = False; - 否则拆分:原块保留为
size = req_size并标记已分配;新空闲块(start + req_size,size - req_size)填入数组下一个可用位置。
回收变量块:定位 + 合并相邻空闲区
回收前需知道该变量所在内存块的 起始地址 和 大小(通常由分配时记录在进程/对象元数据中)。回收步骤如下:
- 在数组中找到对应
start的项,将其free设为True; - 检查它前面一项:若存在、且
free == True、且前项.start + 前项.size == 当前项.start,则合并(前项 size += 当前项 size,当前项清空); - 再检查后面一项:若存在、且
free == True、且当前项.start + 当前项.size == 后项.start,同样合并(当前项 size += 后项 size,后项清空); - 合并后可选做一次紧凑(把非空项前移),但非必须;保持数组稀疏不影响查找逻辑。
实战查找变量块:靠地址反查数组
变量在运行时有确定的内存地址(如 C 中 &var,Python 中可通过 id() 近似估算)。查找它属于哪个内存块的方法是:
- 遍历数组中所有
free == False的已分配块; - 判断是否满足:
block.start ; - 匹配成功即为所属块,可读取其
size、确认归属进程 ID(如有记录)等; - 注意:若变量是栈上局部变量,此方法不适用——First-Fit 一般只管理堆或物理页帧,栈由编译器/运行时独立管理。










