I'm wondering if I've answered this question right:
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 |
From the tracing I've done. I've come to the conclusion that there are 9 page faults. I count the frequency of each time a page is used and reset it to 0 whenever they are removed from their slot (swapped out). Is this the right way to do this?
| 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 |
The solution I've been given is like this that gives us 11 page faults. However, I can't understand why the second C would be replaced on slot 2 when the frequency of B is 2 and the frequency of D in slot 3 is only 1.
CodePudding user response：
You should go back to the definition of LFU that your were given in class. It seems that you interpret it as
evict the entry with the least number of hits since it was populated.
in which case your answer (first table) is indeed correct.
However, it seems that the LFU policy used in the expected answer (second table) is
evict the entry with the smallest ratio of
freq(X) = number of hits / its age.
In such a case, at the 2nd C, you have
freq(A) = 3/7 = 0.429
freq(B) = 2/6 = 0.333
freq(D) = 1/2 = 0.500
and the entry with the least frequency is, indeed, B.
I'd expect LFU to implement the 2nd strategy, because once you have entries with different ages in your cache, you have to account for them having less or more time to accumulate statistics. Your approach would give correct frequencies only in the limit if the entries are never evicted -- which is not a practically interesting case.