# GATE2004-47

31.2k views

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
0
8
indeed a nice question
1
@Arjun sir, Is it possible that for a memory address translation there can be more than one page fault(only for more than one page table)?

as we know page fault is accessing a page that is marked invalid in page table.and suppose there are two page tables and when we try to access page of $PT1$ which is marked invalid and after restoring this page there is again a page fault for $PT2$. Is it possible?
0
I think access will be like this

Find page in Page Table 1 , if not found , then search it in Page Table2, if not found then only bought it from main memory
0
but @srestha if a page is not present in page table $1$, then How will you know which page to acess at inner level bcz from only outer level pages will have entries for those pages.OR it is possible that those page which have entries at outer level page may not be present at inner levels?

But I have one doubt here --if we have page fault at level-1 then what is the techniqe for storing the pages.

we store only that page or along with it we also restore all those page to which this outer level page is referring to.If it is latter case then only at level-1 can cause page fault and subsequent access to page tables can not lead to page fault otherwise we can get multiple level of page faults for  the same address translation.
11
Let p be the probability of a page fault (0 s p 5 1). We would expect p to
be close to zero—that is, we would expect to have only a few page faults. The
effective access time is then
effective access time = (1 - p) x ma + p x page fault time.
To compute the effective access time, we must know how much time is
needed to service a page fault. A page fault causes the following sequence to
occur:
1. Trap to the operating system.
2. Save the user registers and process state.
3. Determine that the interrupt was a page fault. '
4. Check that the page reference was legal and determine the location of the
page on the disk.
5. Issue a read from the disk to a free frame:
a. Wait in a queue for this device until the read request is serviced.
b. Wait for the device seek and /or latency time.
c. Begin the transfer of the page to a free frame.
6. While waiting, allocate the CPU to some other user (CPU scheduling,
optional).
7. Receive an interrupt from the disk I/O subsystem (I/O completed).
8. Save the registers and process state for the other user (if step 6 is executed).
9. Determine that the interrupt was from the disk.
10. Correct the page table and other tables to show that the desired page is
now in memory.
11. Wait for the CPU to be allocated to this process again.
12. Restore the user registers, process state, and new page table, and then
resume the interrupted instruction.

for an instruction probability of having page fault = 1/10000
Hence, probability of having not a page fault = 9999/10000

If TLB hit occurs then memory Access time = 150 +150 = 300(two operand are there) and
if TLB miss occurs then Memory Access Time = Access Page Table1 + Page table2 + Two memory Access =150 + 150 + 150 + 150 = 600

Hit ratio of TLB = 90 %

Memory Access Time = 9999/10000 ( 0.90*300 + 0.10*600 ) + 1/10000( 8000000 + .90*300 + .10*600 )
= 329.967 + 800.033
= 1130 ns

Total Time of execution is = CPU Time + Memory Access Time
Total Time of execution is = 100 ns + 1130 ns = 1230ns
1

second method

0
for two memory references you have to access both page tables twice right, you wrote as if visiting page table 1 and 2 once,gave you the frames numbers of both the memory references which isnt possible upto my knowledge.
0

What does the question actually mean by "average instruction takes 100 ns and two memory access"?

Average Instruction execution time

= Average CPU execution time + Average time for getting data(instruction operands from memory for each instruction)

=   Average CPU execution time
+ Average address translation time for each instruction
+ Average memory fetch time for each instruction
+ Average page fault time for each instruction

= $100+2\Big(0.9 (0) + 0.1 (2 \times 150)\Big) + 2\times 150 + \dfrac{1}{10000} \times 8 \times 10^6$

(Page Fault Rate per 10,000 instruction is directly given in question.Two memory accesses per instruction and  hence we need 2 $\times$ address translation time for average instruction execution time)

[ TLB access time assumed as 0 and 2 page tables need to be accessed in case of TLB miss as the   system uses two-level paging ]

= $100 + 60 + 300 + 800$

= $1260 ns$

edited
7
Never happens. A page table is always in main memory and never swapped out.
1

A page table is always in main memory and never swapped out.

Means while loading new process ..ALL required page tables in all levels are loaded..so page fault happens only for pages corresponding to process and identified by valid bit in Page table..

1
Yes. There is no OS mechanism to handle nested Page Faults.
0
@arjun since it is 2 level paging then why you didn't multiply it with 3 because it'll take 3 memory readings??
0
sir, I have a doubt.. why didn't you multiply 800 with 2?b'coz that also part of accessing the byte from memory right?
2

0

= 100+2(0.9(0)+0.1(2×150))+2×150+1/10000×8×10^6

here it should be 10^-3

0

@Arjun sir, you used $\Big(0.9 (0) + 0.1 (2 \times 150)\Big)$ for 2 level paging, but why is it not $2 \times \Big(0.9 (0) + 0.1 (150)\Big)$ sir ?

By writing $\Big(0.9 (0) + 0.1 (2 \times 150)\Big)$ aren't we assuming that if we find the Page Table Entry (PTE)  of the outer page table in TLB then we will also find the PTE of the inner page table in the TLB only ?

And moreover even if we dont find the outer PTE in the TLB isn't there a chance that we might find the inner page table's PTE in the TLB ?

0
0
I understand the solution. But i am unable to visualize the scenario plz help me to understand this.
0
Here in this question  , one instruction = two memory access given .

And page fault is given per instruction .

If page fault would also be given per memory access then we have to multiply by 2.

hope u got it..
0
Because the page faults are /instruction (per instruction), not /memory-ref.
0

@Arjun I feel you should not multiply 2 with TLB access time because the question is specific about only 2 memory accesses for a particular instruction , so  for one instruction only 1 TLB access should be assumed ,isn't it ?

2

@Arjun At least, according to several GATE questions, in case of multi-level paging, except the outer level page table, the other tables need not have all their pages in MM all the time.

That contradicts our calculations regarding multilevel paging numericals, as those questions need us to assume that the entire Page Table is in MM (just as this one does).

However, there have been theoretical questions (such as in GATE 2003)

https://gateoverflow.in/916/gate2003-26

here it has been implied that Single level paging incurs greater memory overhead than multilevel paging. How would you explain that without assuming that in case of Multi-level paging, we can "reduce the overhead"?

So, I guess it's an ASSUMPTION we make during these numericals, thate page tables are always in MM. And it does sound more practical to me that all the levels of Page Tables should ENTIRELY be in MM. But then how would you explain the memory overhead reduction?

0

please tell me how are you adding the page fault service time even if it is a tlb hit..

tlb hit + page fault (or page replacement) is an impossible scenario ..

so in answer ( 8 x 10^6 / 10000 ) should be replaced by ( 8 x 10^6 / 10000 ) x 0.1

isnt it,,,? what am i missing?

0
1260 option itself is not present in the question
0
0
But the correct answer is 1230 according to gate solution
0
Which IIT released the GATE solution for 2004?

I think here we are overcomplicating things and question is simple but we need to understand it carefully.

page fault rate is one in every 10,000 instructions.

Page fault service time=8ms.

So, on an average time lost due to page fault per instruction=$\frac{8ms}{10000}=800ns$

Now, to this compute Memory access time using TLB.

$EMAT=0.9(150)+0.1(3*150)=180ns$

Since, 2 Memory References are made, Hence total time=$360ns$

To this, $100ns$ of cpu time.

effective average instruction execution time=$800+360+100=1260ns$

0
I understood. Thanks
0
why time lost due to page fault is not included in multiplication of 2 i.e memory references. is time lost due to page fault is independent of no of memory accesses made. Help me in this regard....
0
See here it is given that page fault rate is 1 out of every 10000 instructions. So, Average instruction execution time must be atleast 800ns due to page fault.

So, I think in the final answer,it must be atleast this time-1260ns is average instruction execution time.
3
I think page fault is included once because if it's a page fault than it will be brought into main memory, Now 2nd time it will be in main memory only.
1
I think, due to principle of locality of refence the second page fault will not occure....

is it the case?
0
In this question page fault rate is given per instruction.That is why we are not calculating the effective memory access time?

If it were only given page fault rate and page fault service time ,do we need to calculate effective memory access time first then use it instead of regular memory access time ?

Effective memory access time=(1-p)*amt+(p)*pfs

Here

p=page fault rate

amt=regular memory access time

pfs=page fault service time

@Arjun
0

@Arjun sir

interpretating in this way is also valid compared to yours $?$

0
Understood but what does the question actually mean by 100 ns and two memory access?
0
Why (3*150)?
0
1260 option itself is not present in the question
0
1 for page table

+1 for memory content

+1 for after servicing page fault if it occurs

I think this problem has two parts---

1st:- We have to calculate Instruction execution time when Instruction is in Memory.

Execution Time in this case is---

TLB hit(time to execute instruction)+TLB miss(PageTable access + time to execute instruction)

=TLB hit(time to execute instruction)+TLB miss(2*MemoryAccessTime + time to execute instruction)

=TLB hit(CPU time+2*MemoryAccessTime)+TLB miss(2*MemoryAccessTime + (CPU time+2*MemoryAccessTime))

=0.9(400)+0.1(700)

=430 ns

2nd-      Now we also have to include the fact that Instruction may not be in Mainmemory.Then we have to service page fault first             then we execute instruction like above case

So overall effective average instruction execution time would be

=P*(PageFaultServiceTime+InstructionExceTime when in memory)+(1-P)(InstructionExceTime when in memory)

=(1/10000)(8*106+430)+(9999/10000)(430)=1230ns

Please let me knw if there is any issue.

0
In second case, why are you not taking the time for address translation?
2

2nd case is not about address translation.It is about whether instruction is in mainmemory or not.depending on that we have two cases where you see we have InstructionExceTime when in memory which include full instruction execution along with translation(as calculated in case 1)

0
0
should not we consider page fault when there is tlb miss why we are considering it to be separate
0
chk once more

here page fault is calculated when tlb miss

but thing I notice, it is only calculating when the instruction not in main memory.rt?
0
yes page fault will be calculated when instruction will not be in main memory instead of tlb miss. That's why page fault will be with respect to instruction not with respect to memory access
0

=TLB hit(CPU time+2*MemoryAccessTime)+TLB miss(2*MemoryAccessTime + (CPU time+2*MemoryAccessTime))

When a  mis occur then we access two page tables,after that we got physical address,now we should do one more memory reference to read that memory and then we should add + (CPU time+2*MemoryAccessTime))

Can some one clarify on this?

0

this answer is not correct. Chk selected ans

effective average instruction execution time = CPU TIME + 2 (effective memory access time )

effective memory access time= logical address To physical address + fetch the bye from memory

=  t+(1-pt)(km)+m+pf(ps) (t =tlb access time ,pt =tlb hit, k= paging level, m= memory access time ,pf page fault,ps= page service )

=   0+(1-0.9)*(2*150ns)+150ns+(1/10000)(8ms)

=30ns+150ns+800ns=980ns

effective average instruction execution time= 100+2(980)=2060ns .. so ans is none of this ...

reshown by
0
Is page fault rate given per memory access or per instruction in question?
0
in every 10000 instruction......
0
if we does not consider 2 memory access time then why is this given ......
2
We have to consider two memory access for every instruction. But page fault rate is given every 10000 INSTRUCTIONS and not every 10000 memory accesses.
0
you mean we have to consider 2 memory access time for only tlb access and memory access not for page fault becoz it is every 10000 instruction ..
1
i got your point ...but answer is none of these :p :)

thank you!
0
Well, if you get 1260, you should chose 1230 here. Nowadays GATE is not giving Marks to All :(
0
yes sir.... :(
0
should we not get page fault only when there is TLB  miss?
3
This solution is absolutely right.... and none of the options are  correct...
0
memory access time should include page fault right?

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.

edited
1
4 memory accesses needs for page table(2 level paging * 2 memory access = 4 ) overhead. But 2 memory accesses needs for fetching actual data (what we want) hence it should be 6*150 instead of 4*150.

### 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
2
2 level page tables - so on tlb miss, we need 2+1 = 3 memory accesses. And an instruction has on average 2 memory operands. So, 3*2=6 memory accesses.
0
Yes, you're right 2 memory references for page table and 1 for reach to final frame number, i've missed the point, Thanks i have made the correction.

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
0
where have u taken tlb hit?
0

TLB search time is time when page is found in Tlb

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.

0
Which answer is correct.? What formula is exactly used?
0

@talha hashim

why is  1/10000* 8* 10^6 added only once as we are accessing the memory twice...?

0

@talha hashim

why is  1/10000* 8* 10^6 added only once as we are accessing the memory twice?

## Related questions

1
11.5k views
The minimum number of page frames that must be allocated to a running process in a virtual memory environment is determined by the instruction set architecture page size number of processes in memory physical memory size
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{Operation }& \text{Instruction size (in Words)} \\\hline \text{MOV $R_1,5000$} & \text{$R1$} \ ... text{2 clock cycles }\\\hline \end{array} The total number of clock cycles required to execute the program is $29$ $24$ $23$ $20$
A 4-stage pipeline has the stage delays as $150$, $120$, $160$ and $140$ $nanoseconds$, respectively. Registers that are used between the stages have a delay of $5$ $nanoseconds$ each. Assuming constant clocking rate, the total time taken to process $1000$ data items ... will be: $\text{120.4 microseconds}$ $\text{160.5 microseconds}$ $\text{165.5 microseconds}$ $\text{590.0 microseconds}$
A hard disk with a transfer rate of $10$ Mbytes/second is constantly transferring data to memory using DMA. The processor runs at $600$ MHz, and takes $300$ and $900$ clock cycles to initiate and complete DMA transfer respectively. If the size of the transfer is $20$ Kbytes, what is the percentage of processor time consumed for the transfer operation? $5.0 \%$ $1.0\%$ $0.5\%$ $0.1\%$