编译器笔记43-运行存储分配-堆式存储分配

堆式存储分配

• 堆式存储分配是把连续存储区域分成块，当活动记录或其它对象需要时就分配。
• 块的释放可以按任意次序进行，所以经过一段时间后，对可能包含交错的正在使用和已经释放的区域。

堆式存储分配的示意图

堆式存储分配的示意图.png

申请

设当前自由块总长为M，欲申请长度为n。

如果存在若干个长度大于或等于n的存储块，可按以下策略之一进行存储分配：

• 取长度m满足需求的第1个自由块，将长度为m-n的剩余部分仍放在自由链中。
• 取长度m满足需求的最小的自由块
• 取长度m满足需求的最大的自由块

如果不存在长度大于或等于n的存储块

• 如果M≥n，将自由块在堆中进行移位和重组（对各有关部分都
  需作相应的修改，是一件十分复杂和困难的工作）
• 如果M<n，则应采用更复杂的策略来解决堆的管理问题。

释放

只需将被释放的存储块作为新的自由块插入自由链中，并删除已占块记录表中相应的记录即可。

为实现堆式存储管理

• 须完成大量的辅助操作：如排序、查表、填表、插入、删除、 ……
• 其空间和时间的开销较大