可以在 Knuth 堆上进行碎片整理吗？
我正在考虑是否可以消除 Knuth 内存堆上的外部碎片？在尝试解决这个问题之前，我不确定我们是否可以在堆上移动块。如果我们可以移动块，那么我相信解决外部碎片是微不足道的。
我对这个问题做了一些思考。如果我只是将所有内容复制到新位置（虚拟地址），然后将之前指向该块的所有指针更新到新地址，会有什么问题？我认为这可能是一个正确的解决方案，但我不太有信心。
有人对这个问题有任何想法吗？
提前致谢。
I am considering is it possible to eliminate external fragmentation on a Knuth memory heap? Before trying to solve this problem, I am not sure whether we can move blocks on a heap. If we can move blocks then I believe solving external fragmentation is trivial.
I have done some thinking about this problem. What's the problem if I just copy all the content to the new location(virtual address) and then update all the pointers that previously pointed to the block to the new address? I think this might be a correct solution but I am not very confident.
Does anyone has any idea about this question?
Thanks in advance.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
这听起来不错——您只需在复制之前检查是否能够实际分配足够的内存（或者是否存在足够的预分配内存）。除此之外，我想不出你还会遇到什么问题。似乎继续更新所有指针会相当慢——如果您需要扫描整个堆，那么对于您想要更新的每个块来说，这不是 O(n) 吗？
That sounds about right -- you'll just have to check that you were able to actually allocate enough memory (or that enough pre-allocated memory exists) before you copy it. Other than that, I can't think of any problems you'd have. It seems that going along and updating all of the pointers will be fairly slow -- won't this be O(n) for each block you want to update if you need to scan through the entire heap?