巧妙的内存管理具有持续的时间操作?
-
16-10-2019 - |
题
让我们考虑一个内存段(其大小可以生长或缩小,如文件,在需要时),您可以在其中执行涉及固定尺寸块的两个基本内存分配操作:
- 分配一个块
- 释放不再使用的先前分配的块。
同样,根据需要,不允许内存管理系统在当前分配的块中移动:它们的索引/地址必须保持不变。
最幼稚的内存管理算法将增加全局计数器(具有初始值0),并将其新值作为下一个分配的地址。但是,当仅保留几个分配的块时,这将永远不会缩短该细分市场。
更好的方法:保留计数器,但要维护已交易的块列表(可以在恒定时间内完成),并将其用作新分配的来源,只要它不是空的。
接下来是什么?是否可以做些聪明的事情,但仍具有恒定时间分配和交易的限制,这会使内存段尽可能短吗?
(目标可能是跟踪最小地址的当前非分配块,但在恒定时间内似乎不可行……)
解决方案
使用固定尺寸的块,您描述的是 免费列表. 。这是一种非常常见的技术,具有以下扭曲:自由块的列表存储在自由块本身中。在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;
}
只要所有分配的块都具有相同的大小,并且该大小是指针的大小的倍数,这样就可以很好地工作。分配和交易定位是恒定的(即,与内存访问和基本添加一样恒定的时间 - 在现代计算机中,内存访问可能涉及缓存失误甚至虚拟内存,因此磁盘访问,因此“恒定时间”可以很大)。没有内存的头顶(每个块指针或类似的东西都没有额外的记忆;分配的块是连续的)。另外,只有一次必须分配许多块时,分配指针才能达到给定点:由于分配喜欢使用免费列表,因此只有在当前指针以下的空间已满足时,分配指针才会增加。从这个意义上讲,这是一个 最佳 技术。
减少 发布后的分配指针可能更复杂,因为只能通过遵循免费列表来可靠地识别自由块,该列表以不可预测的顺序通过它们。如果在可能的情况下降低大细分市场的大小对您很重要,则可能需要使用替代技术,并带有更多开销:在任何两个分配的块之间,您都放了一个“孔”。这些孔通过内存顺序与双连接列表链接在一起。您需要一个孔的数据格式,以便您可以通过知道其结束的位置来找到孔启动地址,如果您知道孔在内存中的何处,则可以找到孔的大小。然后,当您释放一个块时,您会创建一个与下一个孔和以前的孔合并的孔,并重建所有孔的有序列表(仍处于恒定时间)。然后,每个分配的块大约是两个指针大小的单词。但是,以这个价格,您可以可靠地检测出“最终孔”的发生,即一种有机会降低大细分市场的大小。
有许多可能的变化。好的介绍性论文是 动态存储分配:调查和关键审查 威尔逊 等。