edited by
14,857 views
63 votes
63 votes

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.

edited by

13 Answers

Best answer
71 votes
71 votes

Look aside Cache Latency $= 1$ ms

Main Memory Latency $= 10$ ms

  • Lets try with  $20$ MB

         Miss rate $= 60\%$ , Hit rate $= 40\%$

         Avg  $=0.4 (1) +0.6 (10)$

                 $= 0.4 +6 = 6.4 \ \text{ms} > 6\ \text{ms}$

  • Next Take $30$ MB 

          Miss rate $= 40\%$ , Hit rate $= 60\%$

          Avg  $= 0.6 (1) + 0.4 (10)$

                 $= 0.6 + 4 = 4.6 \ \text{ms} < 6 \ \text{ms}$

So answer is $30$ MB

edited by
44 votes
44 votes

Tavg = h.Tcache+ (1 − h).Tdisk

Now as in the diagram miss rate(m) is given so we can convert above eqn as : 

Tavg = (1 − m).Tcache+ m.Tdisk

          = (1 - m) * 1 + m * 10                , as Tcache = 1ms and Tdisk = 10 ms

       = 1 + 9m

now question is saying that Tavg should be less than 6ms

    i.e.,       Tavg  < 6

    or,    (1 + 9m) < 6  

    or,            m  <  5/9

    or,            m  < 55.55%

Thus, if we see the given graph size of the cashes for which miss rate < 55.55 % are 30MB, 40MB, 50MB, 60MB, 70MB, 80MB. And questionn is asking for the smallest size among them. Thus required size is 30 MB (smallest one).

          

          

10 votes
10 votes
Tavg=H(1ms) + (1-H)(10ms)

6ms=H(1ms) + (1-H)(10ms)

if u solved u will get H=4/9

but in graph they have given miss rate(%)

so miss rate approx 55% if u increase miss rate it is not possibe to get 6ms

so ans should be 30MB since if u achieve ur goal with 55% miss rate definately possible with 40% miss rate
edited by
8 votes
8 votes

Cache access time = 1ms

Disk read time = 10ms

question says what minimum size of cache should we select (also cache size should be a multiple of 10 as indicated by last line of the question) so that average read latency comes below 6ms.

So, our formula for average read access time is as follows

$T_{avg_{Read}}$ = Hit rate of cache * Cache access time + Miss rate of cache *( Time required to check cache(Given to be 0) +  Time required to read from disk)

let Hit rate of cache be x

Now it is given Average Read access time must be LESS than 6ms.

So using above equation

$T_{avg_{read}} \lt6ms$

$H_rT_c+(1-H_r)T_d \lt 6$

where $H_r=Hit \,ratio$

$T_c=$Latency to read a block from cache.

$T_d=$Latency to read a block from disk

$H_r(1)+(1-H_r)(10) \lt 6$

$0.44 \lt H_r$ which specifies the hit ratio of the cache must be strictly greater than 0.44.

For 20MB Cache: Miss Rate=60%, Hit Rate=40%. This cache is not suitable as implied by above analysis.

With this cache: $T_{avg_{read}}=0.4*1+0.6*10=6.4 \not \lt 6$

For 30MB Cache: Miss rate=40%, Hit rate=60%. This cache should be suitable as $H_r \gt 0.44$

$T_{avg{Read}}=0.6+0.4*10=4.6 \lt 6$

So minimum size cache required=30MB.

 

edited by
Answer:

Related questions

50 votes
50 votes
4 answers
1
Akash Kanase asked Feb 12, 2016
17,628 views
The width of the physical address on a machine is $40$ bits. The width of the tag field in a $512$ KB $8$-way set associative cache is ________ bits.