Схемы распределения Malloc

Question

Да, я беру курс компьютерных систем. У меня было несколько вопросов о различных схемах распределения для реализации malloc. Для явных списков, если я реализую malloc с помощью LIFO-подобного стека, какова именно цель иметь указатели на предыдущую освобожденную память? Например, почему вам нужны дважды связанные списки? Не будут ли одинаковые списки ссылок работать так же хорошо?

Malloc lecture. Я нашел эту ссылку в Интернете, вы можете посмотреть слайд 7, чтобы узнать, о чем я говорю.

При взгляде на схему распределения разделенных списков эти списки однонаправленны правильно? А также, что такое механизм коалесценции? Как, например, если 4 слова освобождены, вы бы сначала попытались присоединиться к нему, когда свободное пространство вокруг вас, прежде чем вставлять его обратно в соответствующий выделенный список? Или вы просто введете блок из 4 слов в разделе «4 слова» соответствующего отдельного связанного списка?

спасибо.

Answer 1

Так как у освобожденного блока всегда есть место для двух указателей, почему бы не удвоить ссылку? Он упрощает коаксиальный код, поэтому при перемещении списка ему не нужно поддерживать трейлинг-указатель. Он также позволяет перемещать список в любом направлении в случае, если есть подсказка, для которой конец списка может быть ближе для начала поиска. Одна неясная система, которую я когда-то смотрел, содержала указатель в «середине», где происходило последнее действие.

При освобождении блока. Есть только четыре возможных случая:

• Свободный блок примыкает после свободный блок.
• Свободный блок находится рядом до свободный блок.
• Свободный блок находится между и свободными блоками до и после него.
• Свободный блок не находится рядом с любым свободным блоком.

Цели коалесценции соседних свободных блоков являются:

• уменьшить длину связанного списка
• точно отражает размер свободного блока, не обременяя аллокатора смотреть вперед, чтобы увидеть если два блока смежны

Сортировка свободного блока в конкретный вариант freelist часто имеет преимущества, но в большинстве практических реализаций коалесцирование является приоритетом, так что alloc() запрос на блок разного размера не будет отклонён, если есть много разных блоков разного размера.