in CO and Architecture edited by
63,598 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}$
in CO and Architecture edited by
by
63.6k views

17 Comments

@Bikram Sir please explain
0
0
indeed a nice question
9
9
@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?
2
2
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
0
reshown by
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.
0
0
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
17
17

second method

2
2
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.
1
1

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

0
0
It is given TLB hit rate is 90% and page fault occurs every 1 in 10,000 instruction. Everything would be easy only if the page fault rate was given.

So lets try to convert it .

Remember, Page fault is taken into consideration only when TLB miss. For finding the page fault rate we need to find out how many time are we actually going to page table. In those ,10000 instruction we need to do 2 address translation per instruction ie total of 20000 instruction translation.

And out of those 20000 only 10% are TLB miss ie, 2000. So we can see for these 2000 tlb miss there is one page fault. And thus we have aur page fault rate. (1/2000)

Now solve normally you will get 1260ns.

Kindly let me know my mistake, if any.
8
8
@anurags228 bruh your approach is damn correct. We only consider page fault when there's a miss in the TLB cache. Can you please share the snapshot of your answer, as I got a bit stuck on this question even after knowing the concepts… 😅
0
0
@anshik

Page Fault rate=1/2000 = 5*10^-4

now,

100      +    2*(    0.9   (150)    +    0.1  (  5*10^-4   (     8*10^6    )+   0.9995(450)     )    )
1
1
Thank you :) @anurags228
0
0
thank you:) @anurags228
1
1
@anurags228

bro how u got 450 ?
0
0
Everyone is giving different answers. Literally confused. Someone pls say which one is the correct solution to this question.
0
0
Instead of 2*( Effective average Instruction execution time )

if i take 100  + 1*( Effective average Instruction execution time )

then im getting 1215 ns sec as my answer

and that is even matching with options too.
0
0

19 Answers

161 votes
161 votes
Best answer
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

 $=\underbrace{100}_{\text{Average CPU execution time}}+\underbrace{2\left(0.9 (0) + 0.1 (2 \times 150)\right)}_{\text{Average address translation time for each instruction}} + \underbrace{2\times 150}_{\text{Average memory fetch time for each instruction}} + \underbrace{\dfrac{1}{10000} \times 8 \times 10^6}_{\text{Average page fault time for each instruction}}$

(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 \textsf{ ns}$

PS: GATE question might have missed the time for second address translation in their calculation which might have made them give 1230 in option D instead of 1260.
edited by
by

4 Comments

it is a 2 level paging so it will need 3 memory access 1st will give entry in 2nd page table and second time it will give actual address so processor need to access memory 3rd time also so so you need to multiply it by 3 instead of 2 so ultimate answer will be 1290 ns … please correct me if i am wrong.

1
1

https://gateoverflow.in/333178/gate-2020-cse-question-53

sir if take a look on your answer for gate 2020 question then if will find that answer for this gate 2004 question is 1230.

please have a look sir

0
0

There is a subtle wrong assumption made in this answer:​​​​​​

  • T(Address translation), T(memory fetch), T(page fault service) are independent variables while they aren’t
  • But T(page fault) is dependent on T(Address Translation) // if T(Address translation) is 0 (where translation is via a TLB hit), T(page fault service) is 0

While T(Instr_exec) = T(CPU_time) + T(Addr_translation) + T(mem_fetch) + T(page fault service), it is incorrect to make a similar statement on their averages as the variables aren’t independent.

 

A better split is as follows:

E(T(instr_exec)) = E(T(CPU_time)) + 2 * E(T(mem_fetch)) // mem_fetch is addr translation and mem_access
E(T(mem_fetch)) = p(tlb_hit) * T(mem_access) + (1 – p(tlb_hit)) * E(T(mem_access_on_tlb_miss))

E(T(mem_access_on_tlb_miss)) = 2 * T(mem_access) + (1 – p(page falt)) * T(mem_access) + p(page_falt_rate) * T(page_falt_service) = 1250

This makes E(T(mem_fetch)) = 0.9 * 150 + 0.1 * 1250 = 260

E(T(instr_exec)) = 100 + 2 * 260 = 620

Please correct me if I’m wrong

 

0
0
113 votes
113 votes

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$

4 Comments

This is by far the best explanation!!
0
0

@Jhaiyam (3*150) because once we have TLB miss, we would go to the outer page table which is located in the main memory, hence one memory access, after that, we move to the inner page table (which is also in the main memory), hence second memory access. Now we have done our V to P translation so we would access the required page from the frame number we’ve got from the inner PT, hence the third memory access.

4
4
The most important point is, we need to consider only one page fault per instruction, rather than considering page fault for each memory access (i.e in EMAT).
1
1
31 votes
31 votes

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.

4 Comments

edited by
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
0

In the above answer,

 =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
0

@ rahul sharma 5

this answer is not correct. Chk selected ans

0
0
19 votes
19 votes

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
by

4 Comments

should we not get page fault only when there is TLB  miss?
0
0
This solution is absolutely right.... and none of the options are  correct...
3
3
memory access time should include page fault right?
0
0
Answer:

Related questions