GATE IT 2007 | Question: 58

Question

A demand paging system takes $100$ time units to service a page fault and $300$ time units to replace a dirty page. Memory access time is $1$ time unit. The probability of a page fault is $p$. In case of a page fault, the probability of page being dirty is also $p$. It is observed that the average access time is $3$ time units. Then the value of $p$ is

• A. $0.194$
• B. $0.233$
• C. $0.514$
• D. $0.981$

Comments

nicely explained….

---

What is the correct answer? I am so confused 0.0194 is not an option.

---

@ramcharantej, 

for this Dirty Page, Page Fault (MISS) will not occur, so it will be a HIT.

This sentence seems illogical to me. Page fault has already happened as clearly mentioned in the question “In case of a page fault, the probability of page being dirty...”

So, after page fault, if the main memory has NO free frames available then page replacement is done.

Now, if the page being replaced (aka Victim Page) turns out to be a Dirty Page then we will have to simply write it in disk first before freeing it up from memory...that’s where Dirty page replacement is done. 

Please Correct me if I’m wrong.

Answer 1

$p(p \times 300 + (1-p) \times 100) + (1-p) \times 1 = 3$

$\implies p(300p + 100 - 100p) + 1-p=3$

$\implies 200p^2 + 99p - 2=0$

After solving this equation using Sridharacharya formula:  $\frac{-b+\sqrt{b^2-4ac}}{2a}$, we get

$$p \approx 0.0194.$$

Comments

option A

---

None of the option matches for this question

Equation is =

3= 1*(1-p) + p*( (1-p)*100 + p*(300+100) )

that gives p= .019

---

@Laxmi. The quadratic equation is not solved correctly. If you solve it will be 0.0194.

@Prateeksha-Kehsari In case of a page fault, service time is 100 and if page is dirty 300 for replacing it. So, page fault service time for a dirty page is 300 or 300+100=400?

---

@Arjun it's 300 only

Dirty page replacement includes PLACING the required page as well in memory. Separately need not to be considered.

And yes ans is 0.0194

---

@Arjun Sir I can't understand. Please explain..  Thank you!!

---

@prateeksha :Dirty page replacement already includes page fault service time .You need not include it again. So in case of dirty read, Time will be just 300 only and not (300+100).

Do that and you will get exactly 0.0194

---

Yes.

100: Time to load a page to memory
300: Time to replace a dirty page

Replace means 300 should include the page load time. I couldn't find any reference for this, if possible please check and confirm. But it must be like this.

---

Arjun Sir-- It is 300 not 400... Replacement includes replacing it with new page and saving it

---

Solving the above equation gives answer 0.514.

---

i cannot understand the fact that it is given effective memory access time as  3 time units. So that means after the page has been replaced we would need to access it. So shouldn't the quadratic be :

(1-p)*1 + p * ( 1 + (1-p) * 100 + p * (300) ) = 3

---

when in doubt refer standard books- for page fault, service time includes the memory access time.

---

option A says 0.194 and answer calculated here is 0.0194.

Am I missing something?

---

page fault service time does not include last memory access time right? ie PST includes time till instruction is restarted but we still need to access memory once again to get the desired data.

So, this (1-p)*1 + p * ( 1 + (1-p) * 100 + p * (300) ) = 3  should be correct.

here we need to add 1 time unit as after page fault is serviced we have to access the memory again to get the desired word/data. Please let me know whether I am correct or wrong.

---

@Arjun Sir 

I think @rahulkr is right.

http://web.cs.ucla.edu/~ani/classes/cs111.08w/Notes/Lecture%2016.pdf

After the page is loaded in memory the instruction is restarted which will then access the memory again.

What do you think?

---

according to question the equation can be satisfied by option c (approx)

---

Arjun Sir, why we are considering simultaneous access of main memory and disk here?

can't we write p(p * 300 + (1-p) * 100) +  1 = 3?

---

Page fault service time include 3 three major component:-

1. Service the page-fault interrupt.

2. Read in the page.

3. Restart the process.

Just read it in Operating System concepts by Galvin- 9th Edition.

---

why are we not taking 2 memory access in case of no page fault(one for page table other for memory)

---

In case of page fault it should be 400 time units.Question says 300 is time to replace dirty page.It did not say that 300 is time to service in case of dirty page.

While handling page fault,we bring page from logical to physical space.Now in physical if no space then we use replacement algorithm and that algorithm should take care of this dirty page part.So 300 is just a time to handle one step in page dault service time.

So total should be 100+300=400 is the service time for page fault in case page to be replaced is dirty

---

i also think  that 300 refers time to replace a dirty page only and to load desired logical page into physical memory requires page  fault service time given to be 100 so total time would take 400

---

@ kaluti @ rahul Sharma 5

no, it will be 300 only bcoz, see in question it is saying it takes 300 units of time to replace a dirty page.  so here the dirty page will be replaced by the required page. so it includes both the thing writing back along with replacement. it is not saying that 300-time units have been taken in writing back, so we can't take this addition 100 units of time.

---

@bharti why will it include both the times? There is no hint regarding the same in the question also

---

@ Rahul sharma

what  does control  do after  seeing the dirty bit .  it  updates the data in memory  and then it brings the required  block .

so I want to say that  their is nowhere mentioned  in question  that 300 time units has  taken in writing back only  .... it includes  the whole things what is done after seeing the dirty bit .

---

Same doubt!!

---

Dirty bit replacement is 300 and page fault service time is 100.There is a difference between these two times ,clearly it means page fault service time is not considering the case when page is dirty.

Now we cannot say that this 300 is to replace the page,that is put old page back to memory and bring new page.

Page fault service time has all the steps(Sending trap to OS, bring the new page from LAS to PAS,updating page tables,then signaling CPU to restart the instruction)

this 300 time is just one of many steps done by page fault service time.Now while at the time of page replacement if page is dirty you take 300 and all the other steps time i.e 100 should also be considered.I dont see any reason to use 300 as a page fault service time when it is dirty.It should be 400

---

shouldn't it be p(1+ p * 300 + (1-p) * 100) + (1-p) * 1 = 3

because after accessing memory with 1 time unit we will come to know thats its a page fault ?

---

I understood that dirty page replacement takes 300 unit time. and this time includes dirty bit update time in sec memory and page service time. But does this includes memory access time also?

p(p * 300 + (1-p) * 100) + (1-p) * 1 = 3

here in first section[(p(p * 300 + (1-p) * 100)] why haven't you added memory access time 'm' or 1?

Service time or dirty page replacement time doesn't include memory access time . right?

---

shouldn't it be p(1+ p * 300 + (1-p) * 100) + (1-p) * 1 = 3

I am having same doubt. Why  1 Memory access time not taken? Because only after accessing memory we came to know it is a page fault.

---

If we find dirty bit to be set to the page we replace then before replacing  that write it to the secondary  memory and then bring the desired logical page into physical frame so dirty page replacement includes the page replacement time

---

@Kaluti , i think you are referring to valid/invalid bit, thatsnot dirty bit.

instead of memory access, we will find whether page is in memory or not by seeing valid/ invalid bit.

therefore we dont need to add memory access time when there is page fault.

but i have another doubt, even for finding valid/invalid bit which is in page table and page table is in main memory, therefore for finding valid/invalid bit also we need memory access.

---

Are we neglecting memory access time here ?

---

p ( p(300+100) + (1-p)(100)) + (1-p) *2 = 3

is this correct?

---

Same doubt to me also...please reply someone and explain it..

---

Upvoted for calling it Sridharacharya formula and not quadratic formula! :p

Answer 2

Given  page fault service time =100 ( if there is no dirty page)

         page fault service time =300 (if there is dirty page in which we have to copy and then load page so it take more time compare to no dirty page replacement)

probability of page fault =p

probability of being dirty is =p

so total page fault service time(ps) = p(300)+ 1-p(100) = 200p+100

now given mat =3 so

mat(3) = p*ps +m, which comes from (p(ps+m)+(1-p)m)

=p(200p+100)+1= 200p^2+100p+1

so p=0.0194

Comments

thankyou so much

---

awesomeeeee explanation!!!

---

But given option is A) 0.914

Answer 3

Generally when average access time to access main memory is calculated by doing address translation then we call it Effective memory access time (TLB, Page Table, O.S) and when it involves caching of data then main memory access, we call it Average memory access time (cache, C.O).

Note:- whenever they mention page fault service time they trying to say the collective time "page replacement time if there is page fault + again the memory access time to read the replaced page or desired page" So here 100-time unit includes all this, similarly for 300-time unit. It is the collective time of "dirty page replacement time if the page is dirty + again main memory access to read the desired page".

The only standard formula to calculate Effective memory access time is

EMAT = p (TLB + M) + (1-p) (TLB + K*M + M) where k is the no. of levels of page table.

Simplified formula:-

EMAT= TLB + M.M + (1-p) (k * M)

If we talk about only page fault in main memory (not TLB)

=P∗(TIME to access main memory)  + (1−P)*( M.M + time to service page fault & access the page)

Simplified formula:-

EMAT= M.M + (1-p) (page service time)

If there are TLB and Page fault both (Note:- TLB hit can also lead to page fault in main memory for various reasons like dirty page or write access on write-protected page)

= (Virtual address to Physical address translation) + (Fetch the word from the memory)

={p (TLB) + (1-p) (TLB + K*M) }   + {(P∗M  + (1−P)*( M + page fault service time))}

Simplified formula:-

=TLB + (1-p) (k*M) + M + (1-P)(page service time).

We can extend this concept to cache memory also...

---

Now coming back to the question

Using extended formula:-

EMAT= (1-p) * M.M  + P {(1-p)*(M + service time) + p(M + dirty page time)

3 = (1-p) * 1  + P {(1-p)*(1 + 100) + p(1 + 300)

3 = 1-p+101p-101$p^{2}$+301$p^{2}$

 200$p^{2}$+100p-2=0

P=0.0194

Using simplified formula:-

EMAT= M.M + p{ (1-p)*Service + p*Dirty}           Note:- we can't further simplify this formula because service time and dirty page time both are disjoint(They do not have anything in common like p(A+B)+(1-p)(A+B+C)).

3= 1+ p{(1-p)*100+p*300}

200$p^{2}$+100p-2=0

P= 0.0194

 

Comments

best one.

just one modification.

2nd equation must be :-   (1-p)(1) + (p)(100+200p) =3

---

Suraj123 the approach you r suggesting will give approximate answer but this is the actual formula with little bit simplification for accurate answer.

Hope u understand.

---

Why are we not taking 2 memory access in case of no page fault?(one for page table access and other for memory)

Am I missing any concept?

Answer 4

Answer should be (c) 0.514
Explanation-

memory access time A=1 time unit
probability of miss=p
so,probability of hit=(1-p)

now in the case of miss i.e. page fault the probability of being dirty page=p
dirty page replace time=300 time units
so,dirty page access time B=p*300 time units.

now, probability of not being dirty page=(1-p).
this (1-p) is for servicing a page fault and it takes 100 time unit
here the access time C=(1-p)*100 time units

finally, average access time=(1-p)*A+p*(B+C)
so,(1-p)*1+p*[(1-p)*100+p*300]=3
by evaluating, we will get p = 0.514

Comments

you evaluate it wrong....p=0.0194 and p= -0.514

---

answer is p=0.0194, please check your calculation.