edited by
62,877 views
129 votes
129 votes

Consider a system with a two-level paging scheme in which a regular memory access takes $150$ $nanoseconds$, and servicing a page fault takes $8$ $milliseconds$. An average instruction takes $100$ nanoseconds 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?

  1. $\text{645 nanoseconds}$
  2. $\text{1050 nanoseconds}$
  3. $\text{1215 nanoseconds}$
  4. $\text{1230 nanoseconds}$
edited by

19 Answers

14 votes
14 votes

Average instruction execution time $= (100+0.9(2*150)+0.1(4*150)+\frac{8*10^{6}}{10^{4}})$ns

$\Rightarrow 1230$ns.

Explainations -

  • $2$ memory accesses if page is found in TLB.
  • $4$ memory accesses if page is not found in TLB. Additional $2$ memory accesses just because of 2 level page. 2 Memory accesses for 2 page tables would be there on TLB miss.

Answer is D.

edited by
10 votes
10 votes

We know that in demand paging EMAT is: P*S+(1-P)*M

P = Page Fault Rate (Whenever frame is not found in Main memory then bring from secondary mem to main mem)

S = Page Fault Service Time (Time to transfer data from sec mem to main mem)

(1-P) = No page fault (TLB Contain page->frame mapping OR TLB don't contain page->frame mapping)

So by understanding the above statements we can evaluate using the data given:

EMAT: = P*S+(1-P)*M + 100(avg exec time)

$10^{-4}$ * 8 * $10^{-3}$ + (1-$10^{-4}$)(TLB HIT + TLB MISS) + 100

800 + 0.9999(0.9*(2*150) + 0.1(6*150)) + 100

800 + 0.9999(270+90) + 100

800 + 359.964 + 100 = 1259.964 = 1260ns

edited by
4 votes
4 votes

Given  - 
memory access time (MA)= 150ns
TLB HIT Rate (ht) = 90%
No. Of Levels in paging scheme (k) = 2
Page Fault Service Time (Pf) = 8 milli sec
Page Fault Rate (Pr)= 1/10000


TLB search time= negligible = 0

page fault service time when pagefault  Pf*Pr = 800ns

Instruction Access time (IAT)= 100ns +2*(MA) = 400ns

(hierarchical way )

EAIT = TLB search time  + (TLB MISS * 2 level memory access time) + (page fault service time when pagefault) + Instruction Access time


EAIT= t + (1 - ht) (k*MA) + IAT + (Pr*Pf)
         = 0 + (1-0.9)(2*150) + 400 + (800)

       = 0 + (0.1)(2*150) + 400 + (800) = 30 + 400 + 800


          = 1230 ns

edited by
3 votes
3 votes

T(memory access avg) = .90(150) + .1(150+150+150) = 180 (150- level1, 150-level2 and 150-memory) 
T effective = 100+ 2* 180 + 1/10000* 8* 10^6 = 1260. 

Answer:

Related questions

66 votes
66 votes
9 answers
1
Kathleen asked Sep 18, 2014
23,682 views
The minimum number of page frames that must be allocated to a running process in a virtual memory environment is determined bythe instruction set architecturepage sizenum...
59 votes
59 votes
4 answers
2
go_editor asked Apr 24, 2016
19,517 views
Consider the following program segment for a hypothetical CPU having three user registers $R_1, R_2$ and $R_3.$\begin{array}{|l|l|c|} \hline \text {Instruction} & \text...
35 votes
35 votes
3 answers
3
52 votes
52 votes
10 answers
4