問題タブ [lru]

私はLRU cacheJavaで実装しようとしています。これは次のことができるはず
です。サイズを動的に変更する。SoftReferenceにサブスクライブするように計画しているという意味でReferenceQueue。したがって、メモリ消費量に応じて、キャッシュサイズは異なります。

値がソフト参照になる場所を使用ConcurrentHashMapし、定期的にキューをクリアしてマップを更新する予定です。
しかし、上記の問題は、どうすればそれを作成できるLRUかということです。

GCを制御できないことは知っていますが、キャッシュ内のすべての可能なオブジェクトが使用状況に応じて（つまり、前回）ソフトに到達可能になるように（キャッシュ内の）値への参照を管理できますか？アクセスされました）、ランダムな方法ではありません。

メインメモリは最大 4 ページまで保持できます。次の順序であるページで LRU アルゴリズムが使用された場合、最初にページ フォールトが発生するページはどれですか?

1,2,3,1,2,4,1,2,3

これは答えがないと思っていた試験問題です。メイン メモリには 4 ページを保持できますが、ページ 1、2、3、4 があるため、ページ フォールトが発生することはありません。

答えは4ページ目ですが、理由がわかりません。

アプリが画面から閉じられ、ユーザーが他のアプリに切り替えたときに、アプリのアクティビティがどうなるかについて非常に興味があります。アクティビティ サークルでは、アクティビティは onStop() に到達します。次に、システムがアクティビティを onRestart() または再起動する前にどのように処理しますか? ボンネットの下で正確に何が起こるのですか？まだキャッシュにあり、LRU に置き換えられますか?

この問題について議論しているアイデアや記事を知っている人はいますか?

可能であれば、それについて読むためのソースコードについて誰か言及できますか?

LRUキャッシュの場合、「シンプル、高速、実用的な非ブロッキングおよびブロッキング並行キューアルゴリズム」で説明されているものと同様のロックフリーキューのアルゴリズムが必要です。

ただし、LRUキューを維持するには、キュー内のノードを削除する可能性も必要になります（末尾のノードを除く）。

私の考えは、CAS操作でノードを削除済みとしてマークし、その後、キュー内から削除されたノードを削除する単一のクリーンアップスレッドを使用することです。

ロックフリーアルゴリズムの作成は、私が最初に予想したよりも複雑であることがわかりました。だから、私の質問は：
そのようなアルゴリズムはすでに利用可能ですか？

これは私が現在使用している構造です：

全般的

• ノードの構造は次のとおりです。struct{e*entry、nextポインター、prevポインター、state uint32}
• 新しいノードごとに複数のメモリが割り当てられるのを避けるために、ノードの配列が割り当てられます。
• ノードへのポインターは、配列インデックス値と更新カウンターで構成され、単一のuint64に多重化されます。
• ノード状態は、ノードが削除されたかどうかを示す上位ビットで構成されます。残りのビットは更新カウンターとして使用されます

エンキュー

• 補助キューは未使用のノードのリストを保持し、「新しい」ノードは補助キューからデキューを介してフェッチされ、デフォルトに設定されます
• node.prevは、新しいノードがエンキューされる前に現在のテールに設定されます

デキュー

• head.next.prevは、ヘッドデキューの前にNIL値にCASされます。head.next.prevがCLEANUP（クリーンアップスレッドによって処理されている）に設定されている場合、デキューは許可されず、スレッドはCPUを解放し、最初からやり直します。
• 削除されていない状態のノードのデキューが成功すると、状態はCASで削除され、ノードは補助キューに戻されます。失敗すると（または状態がすでに削除済みに設定されている場合）、デキューされたnode.prevはNILからCLEANUPに変更され、ノードがデキューされたことをクリーンアップスレッドに通知します。その後、削除されていないノードが正常にデキューされ、CASで削除されるまで、デキューは最初からやり直します。

消去

• キュー内の削除をマークするために、状態はCASで削除され、成功するとクリーンアップキューに渡されます。失敗しても何も行われませんが、関数は戻ります。

クリーンアップスレッド

• node.prevがCLEANUPの場合、Dequeueはそれをキューから削除しました。ノードは補助キューに戻されます。
• node.prevがNILの場合、ノードはヘッドになるか、ヘッドになるか、またはデキューされようとしています。node == headの場合、クリーンアップスレッドはデキューを実行しようとします（状態が削除済みに変更されます）。失敗すると、クリーンアッププロセスが最初から始まります。
• nodeが別のノードに設定されている場合、node.prevはCLEANUPにCASされます。これにより、head.next == nodeになるとすぐに、デキューが行われるのを防ぎます。成功すると、二重リンクリストを使用してキュー内の削除が行われます。失敗すると、クリーンアッププロセスが最初から始まります。

Node.prevは、次のことを伝えるために使用されます。

• キューの前にあるノード
• ノードがヘッドになりそうです/ヘッドです
• ノードはクリーンアップスレッドによって処理されています
• ノードはデキューされます

この例に基づいて、Boost.MultiIndex を使用して作成された次の LRU 実装があります。

問題は、index_by セクションの順序を変更すると (それに応じて enum index_idx を更新すると)、以下を含む行でエラーが発生することです。

次の診断を使用します。

エラー 1 エラー C2661: 'boost::multi_index::detail::sequenced_index::insert': オーバーロードされた関数は 1 つの引数を取らない c:\code\code.cpp 79

コードは次のとおりです。

変更されたインデックスの順序:

LRU キャッシュ設計の参照

回答について質問があります。

ハッシュ マップがいっぱいだとします (インタビュアーが最大サイズを教えてくれました) [マップに既に存在するペアを取得する必要がある場合は、最近使用したことを示すためにリスト エントリを先頭に移動します。]

しかし、追加するエントリがあり、このキーが別のキーと同じ位置にハッシュされるとどうなりますか。(衝突) どうすればいいの？

チェーニングまたはプロービングを行いますか? チェーンを行う場合、マップ サイズを大きくする必要がありますか? 最も古いエントリを削除すると、ハッシュ マップ内の場所が空になります。しかし、新しいエントリはこの場所にハッシュされない可能性がありますか? 別の完全なエントリにハッシュされる可能性がありますか? (異なるキー、値のペア) これを解決するにはどうすればよいですか?

hashtable+linked list を使用して LRU を実装しました。

ハッシュ テーブルには連鎖があります。コードの構造は次のとおりです。

trackHead および trackTail ポインターは、挿入のシーケンスを追跡するためのものです。これは、最も使用頻度の低い要素を削除するために使用されます。1 つではなく、複数の交換ポリシーが使用されていると思います。したがって、LRUは何かの組み合わせで使用されます。したがって、要素に再度アクセスするときに要素を LRU から削除する場合は、LRU から要素を削除する必要があります。

本質的に私はシーケンス全体を維持していますが、何百万ものエントリがある場合、それは悪いことです。プライオリティ キュー + ハッシュテーブルを使用する以外に、これを改善する方法はありますか

redisインスタンスのすべてのキーに有効期限が設定されていると仮定すると、volatile-lruとallkeys-lruは類似しています。しかし、キーが削除されたときの2つの間に大きなパフォーマンスの違いはありますか？

ボーナス質問：

allkeys-lruポリシーで構成され、同じコンテンツと同じ構成を持つ2つの異なるインスタンス間。ただし、次の点を除きます。

• インスタンスAには、すべてのキーに有効期限が設定されています（expireの値が異なります）
• インスタンスBには、有効期限が設定されたキーがありません

期限切れビットによるインスタンスAのメモリのオーバーヘッドは別として、allkeys-lruアルゴリズムによってキーが削除された場合の2つの間にパフォーマンスの違いはありますか？

どちらの場合も、maxmemoryに達したときにmaxmemory = 3Gbで4-5000キーのLinux64ビット上のredis2.4.xのインスタンスについて話しています（ほとんどのキーはハッシュです）。

ありがとう

重複の可能性：
LRUキャッシュ設計

私はプログラミングのインタビューでこの質問を受けました。どのように答えるかを自由に考えてください。

C ++でLRU（最近更新されていない）キャッシュをどのように実装しますか？基本的に、キャッシュは最大Nアイテムを保持できます。新しいアイテムが挿入され、キャッシュ内のアイテムの数が、未満の場合、そのアイテムは挿入されたNだけです。ただし、新しいアイテムが挿入され、キャッシュ内のアイテムの数がすでにある場合はN、使用頻度が最も低いアイテムをキャッシュから削除する必要があります。

各操作にかかる実行時間を考えてください。

オペレーティング システム コースのページ置換をシミュレートするプロジェクトを行っています。私は、1200 の参照に対して 3 つのアルゴリズムすべてを実行するシミュレーターを持っています。ただし、ほとんどの場合、LRU アルゴリズムが FIFO と同じかそれより低いスコアしか得られないページ フォールト率が発生しています。ときどき、LRU のページ フォールト率が FIFO よりわずかに高いという入力が実行されます。これは間違っていますか？

LRU を実装するために、ラウンドごとにインクリメントされる各ページ番号のカウンターを使用しています。使用中のページのカウンターは 0 にリセットされます。フレームを交換するときは、カウンター値が最大のフレームを使用します。私の実装は正しいはずだと思います。