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

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