3

下图可视化了 16 个不同大小的内存块所需的寿命:

在此处输入图像描述

我实际上要寻找的是给定大小为i和生存期[begin i , end i )的N个块,返回在我们的总时间间隔和N个偏移量中包含它们所需的最小总内存块,偏移量i , 到输入块的这个总内存块中。

一个简单的非最优算法如下:

int offsets[N];
offsets[0] = 0;
int total_size = size[0];
for (int i = 1; i < N; ++i)
{
    offsets[i] = offsets[i - 1] + size[i - 1];
    total_size += size[i];
}

我们当前的算法是按大小对块进行排序,然后从最大到最小处理它们,找到该块不与已“分配”的块重叠的第一个偏移量。这本质上是一个贪心算法,所以我有一种感觉,它可以做得更好。

该算法只需要在应用程序启动时运行一次,因此它不必非常快。分配的数量大约为 10-50,为了我们的目的,可以将时间离散化为大约 50 个固定大小的单位。

4

1 回答 1

0

从开始结束时间间隔列表中查找最短开始时间和最长结束时间。这是您感兴趣的时间的总间隔 (t_min, t_max)。接下来,将时间间隔划分为一些离散且均匀的间隔。设此区间的长度为u。这基本上是您的内存管理的最大分辨率(您可以多久释放和/或声明一块内存)。

对于每个时间单位,确定哪些分配 ID 需要内存以及它们各自需要的大小,称为s(t, id)所有分配 ID 的s(t, id)总和是您在任何给定时间需要多少总内存的下限。你不能比这个函数的最大值做得更好,它没有考虑到将事物分配在同一区域而不在每个时间步移动它们的愿望。

要为每个项目找到最佳位置,您可以使用启发式搜索。基本上,在每个内存块的所有可能起始地址的状态空间中搜索占用最小内存总量的解决方案,您可以通过模拟从 t_min 到 t_max 的时间进程来找到该解决方案。

一个可能值得尝试的启发式方法是更喜欢大块占用以前由其他大块占用的空间的分配,而小块被放置在对策略的最大内存使用贡献很小的位置。您还可以修剪任何比迄今为止最好的策略更糟糕的策略,因为该策略声称的最大内存随着时间的推移是单调的。

启发式搜索方法可能很慢,但听起来您更关心最佳内存使用而不是分配算法的运行时间。

于 2013-07-26T03:52:16.717 回答