巧妙的内存管理具有持续的时间操作？

Question

让我们考虑一个内存段（其大小可以生长或缩小，如文件，在需要时），您可以在其中执行涉及固定尺寸块的两个基本内存分配操作：

• 分配一个块
• 释放不再使用的先前分配的块。

同样，根据需要，不允许内存管理系统在当前分配的块中移动：它们的索引/地址必须保持不变。

最幼稚的内存管理算法将增加全局计数器（具有初始值0），并将其新值作为下一个分配的地址。但是，当仅保留几个分配的块时，这将永远不会缩短该细分市场。

更好的方法：保留计数器，但要维护已交易的块列表（可以在恒定时间内完成），并将其用作新分配的来源，只要它不是空的。

接下来是什么？是否可以做些聪明的事情，但仍具有恒定时间分配和交易的限制，这会使内存段尽可能短吗？

（目标可能是跟踪最小地址的当前非分配块，但在恒定时间内似乎不可行……）

Answer 1

使用固定尺寸的块，您描述的是 免费列表. 。这是一种非常常见的技术，具有以下扭曲：自由块的列表存储在自由块本身中。在C代码中，看起来像这样：

static void *alloc_ptr = START_OF_BIG_SEGMENT;
static void *free_list_head = NULL;

static void *
allocate(void)
{
    void *x;

    if (free_list_head == NULL) {
        x = alloc_ptr;
        alloc_ptr = (char *)alloc_ptr + SIZE_OF_BLOCK;
    } else {
        x = free_list_head;
        free_list_head = *(void **)free_list_head;
    }
    return x;
}

static void
release(void *x)
{
    *(void **)x = free_list_head;
    free_list_head = x;
}

只要所有分配的块都具有相同的大小，并且该大小是指针的大小的倍数，这样就可以很好地工作。分配和交易定位是恒定的（即，与内存访问和基本添加一样恒定的时间 - 在现代计算机中，内存访问可能涉及缓存失误甚至虚拟内存，因此磁盘访问，因此“恒定时间”可以很大）。没有内存的头顶（每个块指针或类似的东西都没有额外的记忆；分配的块是连续的）。另外，只有一次必须分配许多块时，分配指针才能达到给定点：由于分配喜欢使用免费列表，因此只有在当前指针以下的空间已满足时，分配指针才会增加。从这个意义上讲，这是一个 最佳 技术。

减少 发布后的分配指针可能更复杂，因为只能通过遵循免费列表来可靠地识别自由块，该列表以不可预测的顺序通过它们。如果在可能的情况下降低大细分市场的大小对您很重要，则可能需要使用替代技术，并带有更多开销：在任何两个分配的块之间，您都放了一个“孔”。这些孔通过内存顺序与双连接列表链接在一起。您需要一个孔的数据格式，以便您可以通过知道其结束的位置来找到孔启动地址，如果您知道孔在内存中的何处，则可以找到孔的大小。然后，当您释放一个块时，您会创建一个与下一个孔和以前的孔合并的孔，并重建所有孔的有序列表（仍处于恒定时间）。然后，每个分配的块大约是两个指针大小的单词。但是，以这个价格，您可以可靠地检测出“最终孔”的发生，即一种有机会降低大细分市场的大小。

有许多可能的变化。好的介绍性论文是 动态存储分配：调查和关键审查 威尔逊 等。

Answer 2

这个答案是关于通用内存管理技术。我错过了一个问题，询问所有块具有相同大小（并且对齐）的情况。

---

您应该知道的基本策略是首先合适的，Next的，最佳的，并且 好友系统. 。我写 简短的摘要 我教过一门课程，希望它可以阅读。我指着 一项相当详尽的调查.

实际上，您会看到这些基本策略的各种修改。但是这些都不是真正的时间！我认为在最坏的情况下，在使用有限的内存时，这是不可能的。

Answer 3

您可能想看看 摊销分析 以及特别的动态阵列。即使操作并非在每个步骤都在恒定时间内真正完成，从长远来看，情况似乎就是这种情况。