Question 1454

Twelve References Three Slots

A cache holds 3 entries. This reference string arrives:

step 1 2 3 4 5 6 7 8 9 10 11 12
key A B C A B D A B C D A B

Count the hits under LRU, under LFU (counters kept only while an entry is resident, ties broken by evicting the least recently used), and under FIFO.

A

LRU 6, LFU 6, FIFO 2

B

LRU 4, LFU 6, FIFO 2

C

LRU 4, LFU 6, FIFO 4

D

LRU 4, LFU 4, FIFO 2