最不常用 (LFU) 缓存跟踪
Least Frequently Used (LFU) cache tracing
我想知道我是否正确回答了这个问题：
The page references are in this sequence: *ABCBADACEBEFBEFBA
With LFU page replacement, how many page faults would occur?
SLOT
A
B
C
B
A
D
A
C
E
B
E
F
B
E
F
B
A
1
A
x
x
x
2
B
x
x
x
x
3
C
D
C
E
x
F
E
F
从我做的追踪来看。我得出的结论是有 9 个页面错误。我计算每次使用页面的频率，并在它们从插槽中移除（换出）时将其重置为 0。这是正确的方法吗？
SLOT
A
B
C
B
A
D
A
C
E
B
E
F
B
E
F
B
A
1
A
x
x
x
2
B
x
C
B
F
B
F
B
3
C
D
E
x
x
我得到的解决方案是这样的，它给了我们 11 个页面错误。但是，我不明白为什么当B的频率为2而插槽3中的D的频率仅为1时，第二个C会被替换在插槽2上。
您应该回到 class 中给出的 LFU 定义。好像你解释成
evict the entry with the least number of hits since it was populated.
在这种情况下，您的答案（第一个 table）确实是正确的。
然而，预期答案（第二个table）中使用的LFU策略似乎是
evict the entry with the smallest ratio of freq(X) = number of hits / its age.
在这种情况下，在第 2 个 C，你有
freq(A) = 3/7 = 0.429
freq(B) = 2/6 = 0.333
freq(D) = 1/2 = 0.500
而频率最低的条目确实是 B。
我希望 LFU 实施第二个策略，因为一旦您的缓存中有不同年龄的条目，您就必须考虑到它们有更少或更多的时间来累积统计信息。如果条目永远不会被驱逐，您的方法只会在极限内给出正确的频率——这不是一个实际有趣的情况。
我想知道我是否正确回答了这个问题：
The page references are in this sequence: *ABCBADACEBEFBEFBA With LFU page replacement, how many page faults would occur?
| SLOT | A | B | C | B | A | D | A | C | E | B | E | F | B | E | F | B | A |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 1 | A | x | x | x | |||||||||||||
| 2 | B | x | x | x | x | ||||||||||||
| 3 | C | D | C | E | x | F | E | F |
从我做的追踪来看。我得出的结论是有 9 个页面错误。我计算每次使用页面的频率，并在它们从插槽中移除（换出）时将其重置为 0。这是正确的方法吗？
| SLOT | A | B | C | B | A | D | A | C | E | B | E | F | B | E | F | B | A |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 1 | A | x | x | x | |||||||||||||
| 2 | B | x | C | B | F | B | F | B | |||||||||
| 3 | C | D | E | x | x |
我得到的解决方案是这样的，它给了我们 11 个页面错误。但是，我不明白为什么当B的频率为2而插槽3中的D的频率仅为1时，第二个C会被替换在插槽2上。
您应该回到 class 中给出的 LFU 定义。好像你解释成
evict the entry with the least number of hits since it was populated.
在这种情况下，您的答案（第一个 table）确实是正确的。
然而，预期答案（第二个table）中使用的LFU策略似乎是
evict the entry with the smallest ratio of
freq(X) = number of hits / its age.
在这种情况下，在第 2 个 C，你有
freq(A) = 3/7 = 0.429
freq(B) = 2/6 = 0.333
freq(D) = 1/2 = 0.500
而频率最低的条目确实是 B。
我希望 LFU 实施第二个策略，因为一旦您的缓存中有不同年龄的条目，您就必须考虑到它们有更少或更多的时间来累积统计信息。如果条目永远不会被驱逐，您的方法只会在极限内给出正确的频率——这不是一个实际有趣的情况。