Мнения и предложения, касающиеся моего подхода к первичной подгонке функции malloc

Question

Я пишу функцию malloc для назначения в колледже. Вот основная схема моей идеи:

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

2) Функция Маллока. Начиная с первого узла, проходите через каждый узел, проверяя наличие вакансий. Если узел свободен и достаточно велик, верните ptr в начало области, не включая узел. Если свободного места нет, используйте sbrk для выделения запрошенного пространства плюс пространство для узла.

3) Свободная функция. Перейти к указателю, переданному в качестве параметра sizeof (struct node) и установить вакансию на вакантный. Затем, начиная с начала списка, просмотрите список, объединяя смежные свободные пробелы.

Как звучит этот подход? Мое главное беспокойство связано с фактическим запуском связанного списка. Например, мне следует создать узел с помощью sbrk, прежде чем я начну делать какие-либо выделения и сохранить ptr для него в качестве глобальной переменной? Если да, то как мне инициализировать первый узел, прежде чем разрешить вызывать функцию malloc программой драйвера?

Заранее спасибо. Я не прошу, чтобы кто-то написал мой код, только чтобы дать некоторое представление и предложения относительно моих идей.

Answer 1

1. Я бы не стал хранить всю бухгалтерскую информацию на узлах, пока они выделены. У меня был бы минимум информации (обычно только размер блока) в начале блока, но не более того.
2. Я бы отслеживал свободные блоки и выделенные блоки отдельно, поэтому, когда вы ищете свободный блок, вы не тратите время на блоки, которые уже используются.
3. Я бы разделил свободный список на две части и лениво слил блоки. Другими словами, у вас есть один свободный список, из которого вы выделяете, а второй - просто область хранения. Когда пользователь звонит бесплатно, просто свяжите блок с областью ожидания, не более того. Когда список, который вы используете для распределений, начинает исчерпывать себя, сортируйте блоки в области хранения по адресу, затем объединяйте их со списком свободных распределений. Затем пройдитесь по списку и объедините смежные блоки.
4. Когда вам нужно вызвать sbrk (или что-то еще), чтобы выделить больше места из системы, не просто выделите достаточно места для удовлетворения текущего запроса на выделение. Вместо этого выделите довольно большой блок (например, мегабайт), а затем разделите его, чтобы получить удовлетворяющий запрос, и добавьте остальное как блок в свободный список. Если у вас недостаточно памяти, чтобы перейти к sbrk один раз, скорее всего, следующие несколько вызовов сделают то же самое, так что вы можете быть жадными и сразу же захватить достаточно памяти, чтобы иметь приличный шанс удовлетворить больше запросы также.

Основная идея третьего - избегать объединения как можно дольше, чтобы увеличить шансы на поиск соседних блоков, поэтому, когда вы делаете объединение, вы, вероятно, сделаете что-то действительно хорошее, и не тратите время на попытки объединения, когда есть только объединение. несколько смежных блоков бесплатно.