c++ - 如何根据先前的行为预测系统的行为

Question

我正在寻找一种算法，它可以根据系统以前的行为来预测 future 的行为。

我正在构建一个并行内存分配器，它有一个空 block 的公共(public)列表。每个线程在需要时都可以从此列表中获取 block 并从中分配。这些 block 根据分配大小(8、12、16 字节......到大约 4 KB)分组在 bin 中。当一个 block 变空时，它被返回到全局列表(当然有同步开销)。如果一个 bin 中没有 block 是空的，它会尝试从其他 bin 中的 block 中“窃取”位置，然后再获得一个新的空 block 。

现在有两种情况让我担心:

1. 一个线程可能会分配占用 5 个 block 的内存。一段时间后，它释放所有这些内存(并且 block 进入全局列表)。紧接着，它再次分配 5 个 block ，释放它们，依此类推。在这种情况下，明智的做法是始终保留这 5 个 block 并且不要将它们返回到全局列表，因为这样可以避免同步开销。
2. 如果分配器“窃取”了一个位置，它就会使用本来会被浪费的内存。但在某些情况下，这会增加内存使用量。

我想做一个可以观察这种模式的系统，并将结果保存在某个地方，以便下次分配器知道什么是明智的，什么不是(在 bin X 中至少保留 N 个 block ，不要't 从 bin Y 中“偷”)。

遗传算法有用吗？我对他们一无所知，但我听说他们擅长机器学习或类似的东西。

提前致谢!

Answer 1

关于正确实现内存管理器的文章很多。这些文章中的大多数都提供了时间测量，说明什么花费了多少时间，以及为什么。所以我建议你看看这个领域已经做了什么。有不少有趣的点子，其中有很多很好用，并且有智慧和有趣的概念。

虽然学习和了解机器学习技术很有趣，但我怀疑它们在现实生活中不会产生好的结果。原因是他们需要大量的开销才能工作。我更相信更接近现代缓存工作方式的方法——最近最少使用方法的不同变体。

因此在您的示例中，我将执行以下操作:

• 使用不同大小的“缓存”，并使用它。这意味着保存一个最小的大小，不会返回到系统，并用于“重用”。
• 高速缓存大小可以动态确定:检查为该线程分配和取消分配新内存的频率。如果脱粒过于频繁(通常可能是时间参数)，则会增加缓存大小。
• 关于窃取:缓存大小可以是不可窃取的，解决缓存和脱粒问题。

这种方法的主要缺点是内存开销。如果缓存大小减少，它也可以减少(因为在您的情况下这是一种权衡)。