Memory Management and Virtual Memory GATE - 2004

Question

Consider a system with a two level paging scheme in which a regular memory access takes 150 ns, and servicing a page fault takes 8 ms. An average instruction takes 100 ns of CPU time, and two memory accesses. The TLB hit ratio is 90%, and the page fault rate is one in every 10,000 instructions. What is the effective average instruction execution time?

a) 645 ns

b) 1050 ns

c) 1215 ns

d) 1230 ns

Comments

I have found the answer in the solution provided by gateoverflow, but in that why is page fault access time is not multiplied by 2. because it says 2 memory accesses is taken.. please clarify someone. The answer calculated in that solution is 1260 but if we take 2*page fault access time then answer will change to 2060. Please clarify.

---

And the other solution says answer will be 1230. which is correct? I am confused.

---

@nishant279, 

Actually, the formula is

Page_fault_rate * ( Page_Service_Time + Memory Access Time) + ( 1 - Page_fault_rate )* ( Memory Access Time)

= ( Page_fault_rate *  Page_Service_Time ) + ( Page_fault_rate *  Memory Access Time ) + ( 1  *  Memory Access Time)  - ( Page_fault_rate * Memory Access Time) 

= Page_fault_rate *  Page_Service_Time +  ( Memory Access Time) 

Why Memory Access time multiplied by 2 in the answer?

Because there are 2 memory access required for an average instruction ==> for 1 instruction = 2 Memory references

Why Page fault service time didn't multiplied by 2?

Because there is only one page fault in every 10,000 instructions. ===> for 1 instruction = $\frac{1}{10^{4}}$ page fault

Answer 1

Given-

• Number of levels of page table = 2
• Main memory access time = 150 ns
• Page fault service time = 8 msec
• Average instruction takes 100 ns of CPU time and 2 memory accesses
• TLB Hit ratio = 90% = 0.9
• Page fault rate = 1 / 104 = 10-4

 

Assume TLB access time = 0 since it is not given in the question.

Also, TLB access time is much less as compared to the memory access time.

 

Effective Access Time Without Page Fault-

Effective memory access time without page fault

= 0.9 x { 0 + 150 ns } + 0.1 x { 0 + (2+1) x 150 ns }

= { 0.9 x 150 ns } + { 0.1 x 450 ns }

= 135 ns + 45 ns

= 180 ns

Effective Access Time With Page Fault-

Effective access time with page fault

= 10^-4 x { 180 ns + 8 msec } + (1 – 10^-4) x 180 ns

= 8 x 10^-4 msec + 180 ns

= 8 x 10^-7 sec + 180 ns

= 800 ns + 180 ns

= 980 ns

Effective Average Instruction Execution Time-

Effective Average Instruction Execution Time

= 100 ns + 2 x Effective memory access time with page fault

= 100 ns + 2 x 980 ns

= 100 ns + 1960 ns

= 2060 ns

resource- gatevidyalya

Comments

please note that there are other methods to solve this type of questions which give different answers after so much head banging on tons of questions on different resources. i have concluded this method is correct one. still its your choice to do it in your own way

---

True this topic of operating system seems to be very confusing :( . A lot of different approaches are there for same concepts , but I think this approach is the best one  , I am also getting same answere.

Answer 2

Here's mine,

Hence answer will be d) 1230 ns

Comments

answer is a- 645, your half approach is correct this helped a lot, thanks

Emat= tlb-hit(mat)+tlb-miss(page-fault*ps+ no page-fault*k*mat)

where, k= level of page.

now Eeit= 100+2*Emat

Answer 3

answer is a- 645, your half approach is correct this helped a lot, thanks

Emat= tlb-hit(mat)+tlb-miss(page-fault*ps+ no page-fault*k*mat)

where, k= level of page.=2
mat= mem. acc. time=150
ps= page service=8
put the values.

now Eeit= 100+2*Emat