3

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.

trincot
  • 317,000
  • 35
  • 244
  • 286
uvdn7
  • 83
  • 4
  • No, it's not. But it's related to a course I am taking. I am asking this question just for curiosity. – uvdn7 Jan 30 '12 at 20:24

1 Answers1

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?

tjarratt
  • 1,692
  • 9
  • 17
  • It should be slow if it works. I am just curious about whether it could work. Thank you for your answer. – uvdn7 Feb 01 '12 at 21:41