1
$\begingroup$

Here is the question:

Consider a computer system that has cache memory, main memory (RAM) and disk, and the operating system uses virtual memory. It takes 2 nsec to access a word from the cache, 10 nsec to access a word from the RAM, and 10 ms to access a word from the disk. If the cache hit rate is 95% and main memory hit rate (after a cache miss) is 99%, what is the average time to access a word?

Here is how I solved it. consider 100 references 95 cache hits(due to 0.95 cache hit ratio) 95*2nsec = 190 nsec

this would leave 5 references which were passed to memory 5*0.99=4.95=5 successfully found in memory

this would count for

5*10nsec=50nsec

average access time=total time/total accesses =(50+190)/100 nsec =240/100 nsec =2.4 nsec

Is this correct?

Here is another solution

memory access time =cache hit ratio * cache access time + (1 - hit ratio) * miss penalty(or memory access time) =0.95*2+(1-0.95)10 2.4 nsec

which one is the perfect solution to this problem?

In question memory hit ratio is also given but is not used in the formula I used in second solution.Was it unnecessarily given in the question? If there is a problem where cache hit rate is 85% and memory hit rate is 5% and disk hit rate is 10%, then what would be the miss penalty in that case?

$\endgroup$
  • $\begingroup$ Please don't use code formatting for text and formulae. You can use LaTeX mathematics here. $\endgroup$ – Raphael Mar 23 '15 at 6:59
  • $\begingroup$ I encourage you to attempt writing your own answer to your question. $\endgroup$ – babou Mar 23 '15 at 9:18
  • $\begingroup$ "Please check whether my answer" questions are not considered on-topic for this site. Your question already includes a complete answer to the original problem, but having others check whether your answer is correct allows only "yes/no" answers, helping neither you nor future visitors. Please read related meta discussions here and here. It's better to focus on a specific question about a single element of your answer you are uncertain about, rather than "is my answer correct?". $\endgroup$ – D.W. Mar 24 '15 at 17:04
  • 1
    $\begingroup$ @D.W. I feel somewhat awkward with this rule as it conflicts with the common request that people should show they did some work before asking. So it is very much a matter of presentation. But this may be more a discussion for meta, or chat. $\endgroup$ – babou Mar 24 '15 at 21:00
  • 1
    $\begingroup$ @babou, I think I can see where you're coming from. Maybe post a question on meta with your concerns? (My take: People have to both show effort, and ask a question that admits a useful answer. "Here's a dump of my answer to my exercise; is it correct?" doesn't lead to useful answers; it only admits yes/no answers, which usually aren't useful. Basically, there are two requirements; questions need to meet both requirements. But that's just my take, and this might be a good topic to work out at more length in general on meta.) $\endgroup$ – D.W. Mar 24 '15 at 22:01
1
$\begingroup$

This is not the answer, but you may consider it as hints to find it yourself.

Why do you write 4.95=5 without any explanation. Is that your idea of perfect solution? Apparently your first solution never accesses the disk. Your second solution is essentially the same as the first, presented more abstractedly (hence a bit better in my opinion, but the reasonning may not be explicited enough for what seems to be your level of proficiency), but it ignores the disk access as much as the first soution.

That may not always be true, but you should always worry at least a little bit where you are ignoring part of the data of your problem. You should convince yourself that the data you ignore is

  • either redundant with the data you use. This means that it is actually a consequence of the data you are using, and can thus be taken into acount implicitly through the data you are using;

  • or irrelevant to the problem. In this case you should preferably have some argument as to why it is irrelevant. This argument may not be required in your answer (though it may not hurt to give it), but you probably at least sketch it for yourself to convince yourself that you are right in ignoring the corresponding data.

  • Irrelevance can also include the fact that the corresponding data is negligible in the context of your problem. But that usually demands some argument to convince the reader that it is indeed the case.

Does the data you ignore correspond to such a case?

$\endgroup$
  • $\begingroup$ I rounded off the number 4.95 to 5.Also 0.5 is not a word,it is half of a word, which does not make any sense.It is not possible that half of the word is in main memory and half is on disk. $\endgroup$ – farheen Mar 23 '15 at 11:33
  • $\begingroup$ BTW This is an assignment question. $\endgroup$ – farheen Mar 23 '15 at 11:34
  • 1
    $\begingroup$ When you are rounding, you should explain why it is justified (see my 3rd point about ignoring data). So, according to you, half a memory reference makes no sense. Since, given any number of memory references, you can always divide them in groups of 100, in which referencing the disk makes no sense, you have just proved that, since the computer makes sense, it never references the disk. So my suggestion is to save on hardware and energy by removing the disk entirely. Do you feel comfortable with that reasonning, or is there a catch somewhere? $\endgroup$ – babou Mar 23 '15 at 12:01
  • 1
    $\begingroup$ @farheen I know you did not mean to say this. I am not trying to confuse you either (though I could be doing so unwittingly). I am trying to make you discover on your own what may be misleading in your reasonning. A first point is that you are working with probabilities, not with actual samples, as you did in your first solution ... which is why it may be more intuitive but less correct, and led you to make unwarranted approximations. If you had chosen samples of 10000 referances, you would not have problems with "incomplete words". But reasonning should not depend on sample size. $\endgroup$ – babou Mar 24 '15 at 9:29
  • 1
    $\begingroup$ @farheen Actually, when working with samples, you misinterpret the figures. They do not have to be integers. Your $0.05$ is not the size of the data you fetch on disk, but the probability that, out of 100 references, one will be fetched from the disk. All the time you are working with probabilities only. So you would be better off just accepting it, and use the approach of your second solution. The problem with the second solution is that it ignores virtual memory miss that require accessing the disk ... and you give no explanation for that. $\endgroup$ – babou Mar 24 '15 at 9:38
1
$\begingroup$

Actually I was not sure about the formula, that's why I posted the question with the work I have done so far. I am posting the right solution so that a student like me can benefit from it in the future The formula for my question is: average access time = (cache hit time x cache hit rate) + (cache miss rate)(RAM hit time x RAM hit rate)+ (cache miss rate)(RAM miss rate)(disk hit time)

$\endgroup$
  • $\begingroup$ That seems OK to me. But an answer like a fish: it will only make one meal. Explaining the answer is like teaching to fish: it will make many meals. Regarding your last concern (erased by D.W. because we are not supposed to have straight question like that in answers), that is precisely what you should have asked in your initial question, and can still ask there, while referring to this answer of yours. ... And if you find the answer by yourself, you can add it here, in your answer. $\endgroup$ – babou Mar 26 '15 at 12:45
  • $\begingroup$ @D.W there was a question in my answer.why it is not there now? $\endgroup$ – farheen Mar 27 '15 at 15:31
  • $\begingroup$ @babou can you explain it to me why disk hit rate is not necessary to be multiplied?to my understanding disk hit rate should also be multiplied as we have multiplied hit rate for cache and RAM. $\endgroup$ – farheen Mar 27 '15 at 15:35
  • $\begingroup$ This problem is about a program executing in virtual memory. Any word you are interested in is somewhere in this virtual memory, and the whole virtual memory corresponds to some space on the disk, though parts that are loaded on RAM or in the cache may not (yet) be up to date. Hence, by definition, there cannot be a miss when looking for a word on disk. The RAM is contains a selected part of the virtual memory that can be accessed faster, and the cache a smaller part that can be accessed even faster than RAM. Actually, this is a simplified view of virtual memory, to give you a general idea. $\endgroup$ – babou Mar 27 '15 at 16:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.