22.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 | 22.2k views
0
+7
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.
+9
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.

A simple approach to this question:

1. TLB hit:

1.1 no page fault : access the instruction

1.2 page fault : service the page fault

2. TLB miss:

Access 2 levels of paging and then:

2.1 no page fault : access the instruction

2.2 page fault : service the page fault

so, average instruction execution time =

$0.9[0 + 0.0001(8*10^6) + 0.9999(400)] + 0.1[0 + 300 + 0.0001(8*10^6) + 0.9999(400)] = 1229.96 ns$

instruction execution time = 100ns + 2[150ns] = 400ns
by (137 points)
reshown

How?

see first the CPU will fetch the instruction:
Here arises 2 cases.
Case I:The instruction is  present in the main memory.
Here for instruction memory accesses will be perforrmed.

for 1 memory access avg access time:

X=TLB hit(TLB access time+memory access time for the word)+TLB miss(TLB access time+memory access for first level of page table+memory access for 2nd level of page table+memory access for the word)

X=0.9(0+150)+0.1(0+150+150+150)=135+45=180ns.
we require 2 memory access/instruction  there fore for each instruction 2X=360ns necessary for memory access.

Case II:The instruction is  not present in the main memory.

then we need

Y=page fault service time +time to access memory 2 times=8 *10^6+2X

finally.......

the time required:
The CPU time required per instruction+0.9999(time taken when instruction is present in the memory)+0.0001(time taken when instruction is not persent in the memory).

100ns+0.9999(2X)+0.0001(8 *10^6+2X)=1260ns

by Junior (787 points)

I was also confused by this question and was not able to understand as per the concepts that I have understood so far, after struggling it with some time (a-lot of time) I was able to break it down to pieces and was able to come to logical explanation, hope it will be helpful to fellow aspirant.

Please refer the the snapshot attached.

ago by (163 points)

I was also confused by this question and was not able to understand as per the concepts that I have understood so far, after struggling it with some time (a-lot of time) I was able to break it down to pieces and was able to come to logical explanation, hope it will be helpful to fellow aspirant.

Please refer the the snapshot attached.

ago by (163 points)