在 malloc 实现中维护空闲列表

Question

我正在尝试为我的操作系统类实现 malloc，并且我想知道维护空闲内存块的双向链表相对于单链表的优势。

Answer 1

如果您在 malloc() 中将一大块内存分成较小的内存块，那么当您使用 free() 返回这些内存块时，您必须将每个返回的块与其 2 个邻居连接起来。在这种情况下，双向链表是最容易处理的。

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);
    }
}

由于包含块大小的页眉在每个块的开头和结尾处重复，因此它充当双向链表，您可以向前和向后遍历空闲列表。指针是隐式的或相对的。