9

私は LRU を理解しようとしていますが、意味がありません。理解できれば、コードを書きやすくなります。手順を説明してもらえますか? お気に入り、

  1. 現在いる参照文字列が配列内にある場合、次のスペースにインクリメントしますか?
  2. バッファ内に何かがあるかどうかを確認する場合、現在の場所または配列全体をスキャンする必要がありますか?

私は従うことができないようです。最近使用されていないものをどのように追跡していますか? 最も最近使用されたものは、あなたのインデックスの後のものであるべきではありませんか?

ここに画像の説明を入力

4

3 に答える 3

5

「アイテム」ごとに2つのアイテムを保管します。値（もちろん）と、増え続ける整数である「時間」。

したがって、データを使用して、1から4が順番にアクセスされたと仮定します。

(1, 1), (2, 2), (3, 3), (4, 4)

アクセス「1」（わかりやすくするために時間でソート、時間= 5）

(2, 2), (3, 3), (4, 4), (1, 5)

アクセス「2」（わかりやすくするために時間でソート、時間= 6）

(3, 3), (4, 4), (1, 5), (2, 6)

見つからない「5」にアクセスすると、キャッシュミスが発生します。「5」を格納する「スペース」を見つけるには、最近使用されていない（LRU）をフラッシュする必要があります。これは「3」を削除することを意味します。時間=7であることに注意してください。

(4, 4), (1, 5), (2, 6), (5, 7)

アクセス「1」（わかりやすくするために時間でソート、時間= 8）

(4, 4), (2, 6), (5, 7), (1, 8)

アクセス「2」（わかりやすくするために時間でソート、時間= 9）

(4, 4), (5, 7), (1, 8), (2, 9)

見つからない「3」にアクセスすると、キャッシュミスが発生します。「3」を格納する「スペース」を見つけるには、最近使用されていない（LRU）をフラッシュする必要があります。これは「4」を削除することを意味します。時間=10であることに注意してください。

(5, 7), (1, 8), (2, 9), (3, 10)

見つからない「4」にアクセスすると、キャッシュミスが発生します。「4」を格納する「スペース」を見つけるには、最近使用されていない（LRU）をフラッシュする必要があります。これは「5」を削除することを意味します。時間=11であることに注意してください。

(1, 8), (2, 9), (3, 10), (4, 11)

見つからない「5」にアクセスすると、キャッシュミスが発生します。「5」を格納する「スペース」を見つけるには、最近使用されていない（LRU）をフラッシュする必要があります。これは「1」を削除することを意味します。時間=12であることに注意してください。

(2, 9), (3, 10), (4, 11), (5, 12)

フラッシュするアイテムがどのように選択されたかがわかり、実際の例がわかったので、配列内でアイテムを移動せずにアイテムをフラッシュするのは、実装する必要があります。

---追加の説明付きで編集---

わかりました。リスト形式で表示するというアイデアからいくつか疑問が生じたようです。配列形式で表示します。

アクセス1、キャッシュミス、空のスロットが利用可能、最初に利用可能なスロットに保存

Value   Age
1       1
---     ---
---     ---
---     ---

アクセス2、キャッシュミス、空のスロットが利用可能、最初に利用可能なスロットに保存

Value   Age
1       1
2       2
---     ---
---     ---

アクセス3、キャッシュミス、空のスロットが利用可能、最初に利用可能なスロットに保存

Value   Age
1       1
2       2
3       3
---     ---

アクセス4、キャッシュミス、空のスロットが利用可能、最初に利用可能なスロットに保存

Value   Age
1       1
2       2
3       3
4       4

アクセス1、キャッシュヒット、更新アクセス時間

Value   Age
1       5
2       2
3       3
4       4

アクセス2、キャッシュヒット、更新アクセス時間

Value   Age
1       5
2       6
3       3
4       4

アクセス5、キャッシュミス、使用可能な空がない、「最近使用されていない」を破棄して置換

Value   Age
1       5
2       6
5       7
4       4

アクセス1、キャッシュヒット、更新アクセス時間

Value   Age
1       8
2       6
5       7
4       4

アクセス2、キャッシュヒット、更新アクセス時間

Value   Age
1       8
2       9
5       7
4       4

アクセス3、キャッシュミス、使用可能な空がない、「最近使用されていない」を破棄して置換

Value   Age
1       8
2       9
5       7
3       10

アクセス4、キャッシュミス、使用可能な空がない、「最近使用されていない」を破棄して置換

Value   Age
1       8
2       9
4       11
3       10

アクセス5、キャッシュミス、使用可能な空がない、「最近使用されていない」を破棄して置換

Value   Age
5       12
2       9
4       11
3       10
于 2012-11-12T03:33:35.210 に答える
5

LRUは通常、リストに入れられます。アイテムにアクセスしたら、リストから削除し（存在する場合）、後ろに押します。リストの後ろは最近使用されたものです。使用済みアイテムは継続的にリストの最後に移動するため、使用頻度の最も低いアイテムは自然にリストの前に移動します。十分なスペースがない場合は、正面から飛び出します。

于 2012-11-12T03:20:28.653 に答える