具有可變大小頁面的緩衝池。當傳入頁面大於要被驅逐的頁面時，需要高性能的方式來合併頁面

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。所以事實上，你可以隨時使用從動態數組插入和交換中已知的簡單移動技術，但是可能明智的做法是檢查可能的優化，在這種情況下，枚舉必須被移動的頁面天真的算法，並首先嚐試將它們直接安裝到待驅逐的空間中。只有在失敗後（如第一個例子），才能使用移動。

如果需要原子性，複製整個緩衝區只應該是必需的。在這種情況下，上面的優化方法也可以工作，但只要你不適合進入即將被驅逐的頁面的頁面，你就會惹上麻煩。在這種情況下，您必須遞歸驅逐算法以找到合適的位置，可能驅逐更多頁面。