Operating System

Question

Consider a paging system which stores its two-level page table in memory and its 16 most recently referenced entries in a TLB. If, a memory access takes 80 nsec, a TLB lookup takes 20 nsec and a page swap time takes 5000 nsec, how long does a data item take to access if the TLB hit rate is 95% and the page fault rate is 10% ?

Comments

is the answer 596?

---

I think this should be the approach:

1] Lets consider average M.M access time

= page hit rate * ( page access time from M.M)

   + page fault rate * (1 page access that resulted in fault + swap the page inside

                                  + re-read the page)

= 0.9(80) + 0.1( 80 + 5000 + 80)

= 588ns

2] Lets consider overall scenario:

Average access time

= TLB hit * ( TLB access time + 1 M.M access )

   + TLB miss * ( TLB access time + 3 M.M accesses )

= 0.95( 20 + 588 ) + 0.05( 20 + 3 * 588)

= 20 + 1.1 * 588

= 666.8 ns

========================================================

Another approach using Habib's answer:

1)  When no page fault occurs:  108 ns

2) When page fault occurs:

Consider average number of memory access per instruction(or per whatever)

= TLB hit (1 mem access) + TLB miss(3 mem access)

= 0.95(1) + 0.05(3)

=1.1

Now, additonal time required

= Probablity of page fault * avg. no. of M.M accesses per instruction * (Swap the page inside + re-read the page)

= 0.1 * 1.1 * (5000 + 80)

= 558.8 ns

Now, coming to overall scenario,

Avg access time

= time in step 1  + additonal time required as in step 2

= 108 + 558.8

= 666.8 ns

---

@srestha @Habibkhan can you please tell what is wrong in my approach

 

First i will look into TLB now 95% time page is present so i will directly read the page data 0.95x(20+80)

5% cases there is TLB miss now i will go in MM and PT is 2level  so 0.05x{(20+80+80) now after seeing 2 levels its found that 90 % page is present in MM so i have to read just data 0.05x{(20+80+80)+0.9x80

10% cases there is page fault in that too , MM 2level PT should have been read first so            0.05(20+80+80+0.9x(80)+0.1*5000)

0.95x(20+80)+0.05{(20+80+80+0.9x(80)+0.1*5000)=

132.6 ans

Answer 1

TLB hit rate is 95%

page fault rate is 10%

memory access takes 80 nsec

TLB lookup takes 20 nsec 

page swap time takes 5000 nsec

A). Average memory access time = AMAT =>

=> Probabilty of no Page fault (....................)  +  Probabilty of Page Fault (.....................)

=> $0.90 * \left ( 0.95 * ( 20 + 80) + 0.05 * (20 + 80 + 80 + 80) \right ) + 0.10* (0.95 *(20 + 80 ) + 0.05 * (20 + 80 + 80 +80) + 5000)$

=> 97.2 + 510.8 

=> 608 ns

---

OR

---

B). Average memory access time = AMAT =>

=> $\left ( 0.95 * 20 + 0.05 * (20 + 160) \right ) + \left ( 80 \right ) + 0.1 * 5000$

=> 19 + 9 + 80 + 500

=> 608 ns

---

OR

---

C). Average memory access time = AMAT => 

=> TLB hit (................)  + TLB miss (...................)

=> $0.95 * \left ( 20 + 0.90 * 80 + 0.10 * (80 + 5000) \right ) + 0.05 (20 + 80 + 80 + 0.90* 80 + 0.10(80 + 5000))$

=> 570 + 38 

=> 608 ns

PS:--> In Last Method, (80 + 5000) is done because 5000 ns is just like disk access time as given in the question. If it had been given that page fault service time is 5000 ns, then use only 5000 ns inplace of (5000 + 80), as PFST includes memory access time also.

Comments

Yes I agree with @Kapilp..608 ns should be the correct answer.

---

@kapll why page fault is included in the starting only?
to access the memory we first need TLB to convert LA to PA and then access the word from memory...
while accessing if page fault occurs there we should take it into consideration..isnt it?

---

Nice explaination @Kapil :)

---

@sudsho, you can check now !! i have tried to provide all possible methods.

---

@Kapil, why your middle solution is giving 607 instead of 608  ??

I think, It should also give 608 ns only.

(0.95∗20+0.05∗160)+(80)+0.1∗5000

Please recheck it ..

I think, it should be,

        (20+0.05∗160)+(80)+0.1∗5000 

??

---

what was the use of this statement in the question

"16 most recently referenced entries in a TLB"

---

yes @vijaycs...for middle one ur procedure is correct...

---

@vijaycs, why removing 0.95 ?

It is TLB hit rate, right ..

---

@Kapil,

Either do that or do like 

(0.95∗20+0.05∗(20 +160)+(80)+0.1∗5000

both are same ... 

Isn't it ??

---

yes both ways it is correct...if u expand  p(t+m)+(1-p)(t+km)..means normal ways how we convert to PA or expand it then we can solve it as mentioned by vijay..

why this line was mentioned "16 most recently referenced entries in a TLB"???
what was it for?

---

@Kapil

in 1st case why u take mm access first and then tlb access

and

in 3rd case why u take

tlb access separately than mm access

$0.95 * \left ( {\color{Blue} 20} + 0.90 * 80 + 0.10 * (80 + 5000) \right ) + 0.05 ({\color{Blue} 20} + 80 + 80 + 0.90* 80 + 0.10(80 + 5000))$

means when we do tlb access, then obviously we also do cache or main memory access .rt?

---

@Srestha, for the 1st case, u have to go through TLB and page table to know if there is a PF or not .

Hence, i have considered that time before 5000.

For the third case, yes it can be tlb hit or miss , PF can occur, but either way you have to check tlb. If it is a TLb hit then check for page fault and if tlb miss, then check page table and check for page fault.

@vijaycs, yes, i missed one time . check now :)

---

@Kapil

what is meaning of page fault?

page is not in memory.If page is not in memory, then after that how r u accessing it from tlb?

AMAT= Probabilty of no Page fault (TLB hit(TLB access time+ memory access)+TLB miss(TLB access time+memory access time+2 level memory access time))  +  Probabilty of Page Fault ( TLB hit(TLB access time+ memory access)+TLB miss(TLB access time+memory access time+2 level memory access time)+swap time )

when there is no page fault, why do we think about TLB miss?

and why u took swap time outside all cases.

---

Page fault are of many type here . one mean is when page not in page table ( corresponding frame for virtual no.) second on when entry match in TLB but that entry does not contaion that frame. 

---

@Kapil we can also do like : An access to TLB and Main Memory is always there whether TLB hit occurs or miss. and if TLB miss occurs we have $2$ extra memory references, because of Page table and in case of page fault, Page service is done.

So, $T_{avg} = 20 + 80 + 0.05*(80 + 80) + 0.1*5000 = 608ns$

---

Plz check my solution  @srestha @sudsho if any doubt still persist in your minds...

---

@mcjoshi, yes thats what we get after reducing the formula,

(0.95∗20+0.05∗(20 +160)+(80)+0.1∗5000 => (20+0.05∗160)+(80)+0.1∗5000

---

@Srestha, In case of tlb hit, PF can also occur if the address is not valid .

---

@Kapil can u tell me, which formula u r using?

plz tell how u calculated

---

@Srestha, there is no formula for these questions. okk !!! I can help u with , Try by tree method.

Try with what happens when tlb hits (Make a branch and proceed)

and what happens when tlb misses (make a branch and then proceed).

If u can do so, post it here. I think it can help you.

These expressions i have only derived from by making trees .

---

@Srestha, This question is from which test series or any book ?

---

madeeasy..

---

what is the role of the line

16 most recently referenced entries in a TLB

---

another doubt..@kapil if the question eas page fault service time 5000ns then what change do we need to make in the first process you described?

---

@uddipto

Entries are of no use here. Had it been access time per word, then it might be useful .

And for PFST, usually it covers everything from TLB search to atlast placing an entry in TLB.

It just made our life easier to not consider access time of everything, just a single value is fine. Here, it was access time, so it is just like other access times.

---

@Kapil

U took page fault access time=page swap time

rt?

but why ? Can u explain a bit

Answer 2

Given , page fault service time (here referred to as page swap time since 

           majority of page fault service time is in swap only , other task include like page replacement from

           the main memory , updation of page tables etc)      = 5000 ns

           page fault rate             =  10%  =  0.1

          TLB access time          =  20 ns

          TLB hit rate                  =  95 %  = 0.95

         Main memory access time  = 80 ns

Let us break the solution into subproblems .

Case 1 : Page fault does not occur

This has further cases :

a) TLB hit occurs :

So effective time when TLB hit occurs = TLB hit rate*  [TLB access time + Main memory access time ]

                                                        =  0.95 * [20 + 80]

                                                        =  0.95 * [100]

                                                        =  95 ns        ............(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 it is given that 2 level paging is used , so 2 main memory access times are required since page tables are stored in main memory. 

So effective time when TLB miss occurs = TLB miss rate*  [TLB access time + 2 main memory access time(due to page table)                            + 1 main memory access time to read the actual data / instruction ]

                                                           = 0.05 * [20 + 80 + 80 + 80]

                                                           = 0.05 * [260]

                                                           = 13  ns                                                    ...............(2)

So combining (1) and (2) ,

 Effective time if page fault does not occur  =  95 + 13

                                                               =   108 ns                                                   .................(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 , 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     =     5000 + 108

                                                              =     5108 ns                    ...............(4) 

But page fault occurs only 10 % 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.9 * 108  +   0.1 * 5108

                                          =      608 ns

                                     

Hence time required effectively  = 608 ns

Comments

@Habib. Consider following example:

lets consider a simple system where you simple access M.M and disk.

1 instruction $\equiv$ 100 page accesses in M.M (on average)

Page hit ratio of M.M = 95%, Page Fault ratio = 5%

1 page access in M.M takes 1 sec.

If page fault occurs, time taken just to bring the page inside M.M = 2 sec

Calculate the average access time.

==============================================================

My approach as above:

a) Pafe fault doesnt occur = 95 * 1sec

b) Page fault occurs = 5 * 3sec

Total = 110 sec

==============================================================

Your approach:

a) Pafe fault doesnt occur = 0.95 * 100 * 1sec = 95 sec

b) page fault occurs = 0.05 * [95 + 3] = 4.9 sec

Total = 99.5 sec

=============================================================

Did you get it what I am trying to say?

---

@ habib sir, arjun sir, kapil sir

PLzzzzzz plzzzzzzz tell me one thing, sometimes we assume that page fault service time includes everything and we just add page fault rate* page fault time, sometimes we add up the translation time like done in this question. Certainly everywhere different scheme is followe to calculatet  the answer and its confusing like anything. What to follow and why??

---

awesome answer @ habib sir. Thanx a ton.

Answer 3

EMAT=Effective memory access Time

EMAT=page fault rate(Service time+memory access Time) +hit rate(TLB hit(TLB access Time+memory acess Time)+TLB miss(TLB access Time+no. of page table*memory acess Time+ memory access Time));

page fault rate=10%

Service time=5000ns

memory access Time=80ns

0.1*(5000+80)+0.9(0.95(20+80)+0.05(20+80+80+80))=605.2