Можно ли выполнить дефрагментацию в куче Кнута?

Question

Я думаю, возможно ли устранить внешнюю фрагментацию кучи памяти Кнута?Прежде чем пытаться решить эту проблему, я не уверен, сможем ли мы перемещать блоки в куче.Если мы сможем переместить блоки, то я считаю, что решение проблемы внешней фрагментации тривиально.

Я немного подумал над этой проблемой.В чем проблема, если я просто скопирую весь контент в новое местоположение (виртуальный адрес), а затем обновлю все указатели, которые ранее указывали на блок, на новый адрес?Я думаю, что это может быть правильным решением, но я не очень уверен в этом.

У кого-нибудь есть идеи по этому вопросу?

Заранее спасибо.

Answer 1

Звучит правильно - вам просто нужно проверить, что вы действительно можете выделить достаточно памяти (или что существует достаточно предварительно выделенной памяти), прежде чем копировать ее. Кроме этого, я не могу думать ни о каких проблемах, которые у вас были бы. Кажется, что продвижение и обновление всех указателей будет довольно медленным - не будет ли это O (n) для каждого блока, который вы хотите обновить, если вам нужно сканировать всю кучу?