GATE CS 2016 Set 2 Q.60 (CS Q.50): File Systems, I/O and Disk Scheduling

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.

Line plot showing cache miss rate in percent against cache size in megabytes. The horizontal axis represents cache size from 0 to 90 MB in increments of 10 MB. The vertical axis represents miss rate from 0 to 90 percent in increments of 10 percent. Data points with dotted grid lines are: (10, 80%), (20, 60%), (30, 40%), (40, 35%), (50, 30%), (60, 25%), (70, 20%), and (80, 15%). — Cache Miss Rate (%) vs Cache Size (MB)

The smallest cache size required to ensure an average read latency of less than 6 ms is _____ MB.

Your answer

Official answer and solution

Official answer: 30
From: Official GATE 2016 answer key

Solution

Set up the average latency formula as a function of miss rate and read the smallest valid discrete cache size from the graph.

Let $m$ be the cache miss rate (expressed as a fraction $0 \le m \le 1$ ). The hit rate is $h = 1 - m$ .

Reading from cache takes $T_{\text{cache}} = 1\text{ ms}$ , while reading from disk on a miss takes $T_{\text{disk}} = 10\text{ ms}$ . The average read latency $T_{\text{avg}}$ is:

T_{\text{avg}} = (1 - m) \times 1\text{ ms} + m \times 10\text{ ms} = 1 + 9m\text{ ms}

We need the average read latency to be strictly less than 6 ms:

1 + 9m < 6 \implies 9m < 5 \implies m < \frac{5}{9} \approx 0.5556\text{ (or } 55.56\%\text{)}

From the given miss rate graph:

At Cache Size = 10 MB: Miss rate = 80% ( $T_{\text{avg}} = 1 + 9(0.8) = 8.2\text{ ms}$ )
At Cache Size = 20 MB: Miss rate = 60% ( $T_{\text{avg}} = 1 + 9(0.6) = 6.4\text{ ms}$ )
At Cache Size = 30 MB: Miss rate = 40% ( $T_{\text{avg}} = 1 + 9(0.4) = 4.6\text{ ms} < 6\text{ ms}$ )
At Cache Size = 40 MB: Miss rate = 30% ( $T_{\text{avg}} = 3.7\text{ ms}$ )

Since cache sizes are available in multiples of 10 MB, the smallest cache size that achieves an average read latency under 6 ms is 30 MB.

Final answer

Common trap

Adding disk access time on top of cache latency during a miss (i.e. $1 + 10 = 11\text{ ms}$ ), or misinterpolating the discrete values plotted on the graph.

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

Source

Paper: GATE 2016 Computer Science and Information Technology (CS) Session 2
Question: 60 of 65, printed as CS Q.50
Section: Computer Science and Information Technology

Report an error in this question

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.

Question

Solution

Source