1

データベース バッファ プール (メモリ プール) の実装では、メモリ内のページで構成されるバッファがあります。

ページにはさまざまなサイズがあります (すべて 512kb の整数倍)。

エビクション ポリシーが LRU (最近使用されていない) であるとしますが、エビクトしようとしているページのサイズが、置き換える必要のあるサイズよりも小さいとします。LRU にも従いたい場合は、収まるのに必要な数の LRU ページをエビクトする必要があります。私の新しいページ。

n最近使用したページを削除する必要があるとします。ただし、これらのページは、バッファ/メモリ プール内で必ずしも連続しているわけではありません。

私が考えた簡単な方法は、これらのnページを結合することです。つまり、バッファー プールを適切に並べ替える必要があります。

最も簡単な方法は、バッファー全体をコピーして永続バッファーを上書きし、データ型を適切に更新することです。ただし、これは、この操作のためにバッファ全体をコピーするのに十分な RAM があることを前提としています。バッファ全体をコピーする必要がない賢いアプローチはありますか?

ありがとう

4

1 に答える 1

1

バッファを移動する必要があるとすぐに、私の意見では「高パフォーマンス」にはなりませんが、これはどうですか:

削除しようとしているページの合計サイズは、ページ サイズ 512 kB のk倍、つまり受信ページのサイズです。

最悪の場合のレイアウトは次のようになります (4 文字 (バーを除く|) == 512 kB):

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

2 つのXes は、削除するページです。X2問題は、バッファーを連続させるために、次へX1(またはその逆)に移動する必要があることです。私のアプローチは、ページをX1右に向かって（にX2）移動することです。X2とにかくエビクトしたいので、オーバーライドしても安全です。

そうすれば、バッファ全体をコピーする代わりに、3 つのページ サイズを更新するだけで済みます。

より複雑な問題は次のようになります。

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

上記の素朴なアルゴリズムを引き続き使用できますが、最適化の可能性があります。たとえば、そこに収まるので、触れずに安全に移動1できますX2。2同じ2ことが、 に移動できる にも当てはまりX3ます。

実際には、動的配列の挿入と交換から知られている単純な移動手法をいつでも使用できますが、可能な最適化を確認するのが賢明かもしれません。この場合、単純なアルゴリズムによって移動する必要があるページを列挙し、最初に、それらを立ち退きスペースに直接合わせてみてください。(最初の例のように) 失敗した後にのみ、移動を使用する必要があります。

原子性が必要な場合にのみ、バッファ全体をコピーする必要があります。その場合、上記の最適化されたアプローチも機能しますが、立ち退くページに邪魔なページを収めることができなくなるとすぐに問題が発生します。その場合、適切な場所を見つけるためにエビクション アルゴリズムを再帰する必要があり、さらに多くのページをエビクトする可能性があります。

于 2014-01-28T18:57:40.337 に答える