具有可变大小页面的缓冲池。当传入页面大于要被驱逐的页面时，需要高性能的方式来合并页面

Question

在数据库缓冲池（内存池）的实现中，我有一个由内存中的页面组成的缓冲区。

页面有不同的大小（512kb的所有整数倍）。

说我的驱逐政策是LRU（最近最少使用），但我试图驱逐的页面尺寸比我需要替换的尺寸小，如果我想跟随LRU，我应该驱逐尽可能多的LRU页面必要适合我的新页面。

假设我需要n最近使用的页面被驱逐。但是，这些页面在缓冲区/内存池中不一定是连续的。

我想过的一个简单方法是合并这些页面，这意味着我需要适当地重新排序缓冲池。

最简单的方法是复制整个缓冲区并覆盖永久缓冲区并适当地更新数据类型。然而，这假定我们有足够的RAM来拷贝整个缓冲区来执行这个操作。有没有一种巧妙的方法，我不需要复制整个缓冲区？

感谢

Answer 1

只要你有移动周围的缓冲区，它不会在我看来，“高性能”，然而，这个怎么样：

你要驱逐是我们的网页总大小为k次页面大小512 kB，也就是传入页面的大小。

最坏情况下的布局是这样的（4个字符（除酒吧|）== 512 KB）：

|X1 |1  |2 |X2 |3  |4  | 

两个X ES是驱逐页面。现在的问题是要使缓冲区连续，您需要移动X2旁边X1（或相反方向）。我的方法是将X1之后的页面向右移动（到X2）。我们可以安全地覆盖X2，因为我们无论如何都想驱逐它。

这样，我们只需要更新3个页面大小而不是复制整个缓冲区。

更复杂的问题是：

|X1 |1 |2  |X2 |3  |X3  |4  |5 | 

一个仍然可以使用幼稚的算法从以上，但也有可能的优化。例如，可以安全地将1移动到X2而不碰2，因为它适合那里。 2也是如此，可以将其移动到X3。所以事实上，你可以随时使用从动态数组插入和交换中已知的简单移动技术，但是可能明智的做法是检查可能的优化，在这种情况下，枚举必须被移动的页面天真的算法，并首先尝试将它们直接安装到待驱逐的空间中。只有在失败后（如第一个例子），才能使用移动。

如果需要原子性，复制整个缓冲区只应该是必需的。在这种情况下，上面的优化方法也可以工作，但只要你不适合进入即将被驱逐的页面的页面，你就会惹上麻烦。在这种情况下，您必须递归驱逐算法以找到合适的位置，可能驱逐更多页面。