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

How are you getting p=0.514 I think you added -99 with -√(99²+8*200) and divided with 400 bue that will make p in negative so p=0.514 is out of the question bro

---

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

here for faulty page also we need to access main memory to check if page is faulty or not ,

and when page is not faulty then we need to access page table and main memory so why above method is not used, Someone plz expalin..

---

• A page fault occurs only after the page table lookup, when the valid/invalid bit for that page = 0 (i.e., page not in memory). The CPU must have already accessed the page table (which itself is in memory) before knowing a fault occurred. So don't consider memory access for pageTable.

• 2nd thing is, we generally ignore memory access where page fault occurred because page service time is very large compare to memory access and can be ignored, so only consider page service time when fault occurred.

@Sudhanshu_Tiwary

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

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

---

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

---

no it wont be becoz page fault service time includes everything

Answer 2

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

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?

---

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)

Here, why are we again using MM time with page fault service time ? Doesn't page fault service time also contains memory access time ? Shouldn't it be like following :

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

---

🤣🤣🤣🤣😂😂😂

Answer 3

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 4

In a demand paging system, the Effective Memory Access Time (EMAT) is calculated by weighing the time taken for a "Page Hit" against a "Page Fault." Think of it like getting a Pizza: a Hit is like finding pizza already in your fridge (1 min), whereas a Fault means the fridge is empty and you must order delivery. However, if the fridge is full of old food (a Dirty Page), you must spend extra time cleaning it out (300 mins) before the new pizza fits; otherwise, you just put the new pizza in a Clean empty spot (100 mins).

Because the "Dirty" or "Clean" work only happens if there is a fault (p), we use a nested probability equation. First, we separate the hit (1-p) from the fault p, and then inside the fault condition, we split the probability again based on whether it involves a dirty page (p) or a clean page (1-p). Using the given values where Memory Access is 1, Clean Fault is 100, Dirty Fault is 300, and EMAT is 3, the consolidated equation is:

EMAT = (1 - p)1 +(p)( (1 - p)100 +p300) = 3

This simplifies to the quadratic equation 200p^2 + 99p - 2 = 0, which, when solved using the quadratic formula, gives a page fault probability of p approx 0.0194.

 

Answer 5

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

=> 200p^2 +100p - 2 = 0

=> p= 0.192

 

Comments

why not (1-p) (1)   +   (p) (1 + (p)(100 + 300) + (1-p) (100) ) = 3

Answer 6

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.