A file system uses an in-memory cache to cache disk blocks. The miss rate of…
2016
A file system uses an in-memory cache to cache disk blocks. The miss rate of the cache is shown in the figure. The latency to read a block from the cache is 1 ms and to read a block from the disk is 10 ms. Assume that the cost of checking whether a block exists in the cache is negligible. Available cache sizes are in multiples of 10 MB.
The smallest cache size required to ensure an average read latency of less than 6 ms is __________ MB.
Attempted by 58 students.
Show answer & explanation
Correct answer: 30
Key equation: average latency L = (1 - m) * 1 ms + m * 10 ms = 1 + 9m (ms), where m is the miss rate as a fraction.
Require L < 6 ms, so 1 + 9m < 6 ⇒ 9m < 5 ⇒ m < 5/9 ≈ 0.555 (55.6%).
Read miss rates from the graph for available cache sizes (multiples of 10 MB): 10 MB → 80%, 20 MB → 60%, 30 MB → 40%, 40 MB → 35%, 50 MB → 30%, 60 MB → 25%, 70 MB → 20%, 80 MB → 15%.
Find the smallest cache size with miss rate < 55.6%: 20 MB has 60% (too high), 30 MB has 40% (satisfies the requirement).
Therefore the smallest cache size required is 30 MB.
A video solution is available for this question — log in and enroll to watch it.