17,391 views

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

1. $0.194$
2. $0.233$
3. $0.514$
4. $0.981$

nicely explained….
What is the correct answer? I am so confused 0.0194 is not an option.
edited

@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.

$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.$$
by

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

is this correct?
Upvoted for calling it Sridharacharya formula and not quadratic formula! :p
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
by

thankyou so much
awesomeeeee explanation!!!
But given option is A) 0.914

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

edited by
best one.

just one modification.

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

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?

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

by

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