Can defragmentation be done on a Knuth heap?

Question

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.

Answer 1

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?