Ведение свободного списка в реализации malloc

Question

Я пытаюсь реализовать malloc для своего класса операционных систем, и мне было интересно узнать о преимуществах поддержки двусвязного списка свободных блоков памяти по сравнению с односвязным списком.

Answer 1

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

Answer 2

Грубый набросок free_block с использованием списка последствий. Память организована в виде массива целых чисел, block - это смещение блока к свободному в этом массиве, prev и next - смещения предыдущего и последующего блоков. Каждый блок начинается и заканчивается целым числом, содержащим размер блока, включая верхний и нижний колонтитулы:

void free_block(int memory[], int block) {
    // Write the header of the free block
    int block_size = GET_SIZE(memory[block]);
    memory[block] = MAKE_FREE(block_size);

    // Check if the next block is free
    int next = block + block_size;
    int next_size = GET_SIZE(memory[next]);
    if (IS_FREE(memory[next])) {
        // Great! Coalesce the blocks
        block_size = block_size + next_size;
        memory[block] = MAKE_FREE(block_size);
    }

    // Check if the previous block is free
    int prev_size = GET_SIZE(memory[block - 1]);
    int prev = block - prev_size;
    if (IS_FREE(memory[prev])) {
        prev_size = prev_size + block_size;
        memory[prev] = MAKE_FREE(prev_size);
    }
}

Поскольку заголовок, содержащий размер блока, дублируется в начале и конце каждого блока, он служит в качестве двусвязного списка, и вы можете перемещаться по свободному списку вперед и назад. Указатели являются неявными или относительными.