Operating System

Question

Consider a Memory Management System where TLB hit rate is 90% whose access time is 1 cycle. The hit ratio for cache is 80% and if access time is 1 cycle. The page fault rate when there is a miss in both TLB and cache is 2%. Main memory access time is 20 cycles. Hard drive access time is 500 cycles. The page tables are always kept in Memory. The TLB accesses and cache acesses are sequential. The average memory access time when the cache is virtually addressed is __________ cycle. (Upto 2 decimal places)

Comments

?????

---

Ok I have rectified and acknowledged my mistake .But who has downvoted my answer..Mistake may happen from anyone..No one is 100 % perfect.

---

So ans will be 5.4 Cycles Right ??

Answer 1

Given , page fault service time = 500 cycles

           page fault rate             =  2%  =  0.02

          TLB access time          =  1 cycle

          TLB hit rate                  =  90 %  = 0.9

         Cache access time        =  1 cycle

         Cache hit rate                = 80 %  =  0.8

         Main memory access time  = 20 cycles

Let us break the solution into subproblems .

Case 1 : Page fault does not occur

This has further cases :

a) TLB hit occurs :

In this case , page tables need not be accessed hence we check that there may be cache hit or cache miss , so again 2 cases within it.

So effective time when TLB hit occurs = TLB hit rate*  [TLB access time + Cache hit rate(Cache access time) +

                                                             Cache miss rate * (Cache access time + Main memory access time) ]

                                                        =  0.9 * [1 + 0.8*1 + 0.2*(1 + 20) ]

                                                        =  0.9 * [1 + 0.8 +  4.2]

                                                        =  0.9 * 6

                                                        =  5.4 cycles          ............(1)

Now 

b) TLB miss occurs :

So in this case the page tables access time which are in main memory are also going to be counted .Since nothing is given about level of paging so we assume we have 1 level of paging only , so 1 main memory access time is required since page tables are stored in main memory. 

So effective time when TLB miss occurs = TLB miss rate*  [TLB access time + 1 main memory access time(due to page table)                             + Cache hit rate(Cache access time) + Cache miss rate * (Cache access time + Main memory access time) ]

                                                           = 0.1 * [ 1 + 20 + 0.8 + 0.2 * 21 ]

                                                           = 0.1 * [ 1 + 20 + 5]

                                                           = 0.1 * 26

                                                           = 2.6 cycles                                                     ...............(2)

So combining (1) and (2) ,

 Effective time if page fault does not occur  =  5.4 + 2.6

                                                               =  8 cycles                                                   .................(3)

Now we come to case 2) 

Case 2  : Page fault occurs :

If page fault occurs , then in addition to what have we done in earlier steps , we also require page fault service time

So time required in this case :  Page fault service time + effective time calculated in case a) [as we come to know later that page fault has occured , so we have accessed TLB , page tables , cache memory , main memory as required and as the case may be before knowing that page fault has occured ]

So ,

Time required in case page fault occurs     =     500 + 8  

                                                              =     508 cycles                    ...............(4) 

But page fault occurs only 2 % of the time.Hence,

Effective time required         =      Page hit rate * time calculated in case 1 + page fault rate(or miss rate) * time found in case 2

                                          =      0.98 * 8   +   0.02 * 508

                                          =      7.84   +    10.16

                                          =      18 cycles

Hence no of cycles required effectively  = 18 cycles

Comments

@Kapil. Mistake in my calculation? Could you plz point out?

---

@Ram.

Dont go with those horror formulaes :P :P.   You wont get those and even I dont get them.

Just consider step by step  considering avg access time at each level of memory. That will give you same asnwer.

---

@Sushant Gokhale

In your solution you have done this step : 

Avg TLB access time

= TLB hit ratio * ( TLB access time + Avg M.M access time )

  + TLB miss ratio * ( TLB access time + Page table access + Avg M.M access time)

 

I am not able to understand because if there's a TLB Hit then it is guaranteed that we are getting a frame no. from the TLB Entry. So we will be just accessing the main memory after that. But your stated formula says that after TLB Hit there is a chance of page fault (as you are using Avg M.M access time) but this is not possible.

 

I think everything you have stated is right except this part where I think this should be :

Avg TLB access time

= TLB hit ratio * ( TLB access time + M.M access time(for accessing data from M.M) )

  + TLB miss ratio * ( TLB access time + Avg M.M access time)

( Now regarding the page table access time, I am not considering it as it is not given in the question whether it has single level paging or n-level paging. Usually in Page fault questions page table access time is included in M.M access time. But still if you want to consider single level paging then in that case page table access time should be used in Avg M.M access time calculation part )

Answer 2

Here Cache is read before Tlb and after miss in both it is taken from hard drive, So I guess the Solution will be

Cache(hit) * cache Time + Cache(miss) { Tlb(hit) [ tlb time + memory time] + tlb(miss) [ 20+ .02*500 ] }   

??