The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+37 votes

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$
in Operating System by Boss (16.3k points)
edited by | 5.9k views
why are we not taking 2 memory access in case of no page fault(one for page table other for memory)
Admins, Please verify options

given memory access time(1 unit) includes that already.

5 Answers

+50 votes
Best answer
$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 Active (1k points)
edited by
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..
+20 votes
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 Boss (16.9k points)
Why probability of a page fault is multiplied by page fault service time when there is a bit p(300)?

and why not a probability of a page fault is multiplied by page fault service time when no dirty bit is there 1-p(100)?

and why we are not mulipling 2 when there is no page fault because then we will be accessing memory twice one for page table and one for acutal data?

Please can you answer my these questions
you can think like ,whether it is page fault or not you have to acess mm once to get the required data  so m term is existing thre with probability 1 note that this memory acess time include page table acess time as well ,now you may have to do page fault service with probabilty p so p*ps is added to m.
Value of P after solving your quadratic equation 200p2 + 100p - 2 =0  is p = 0.01925824(0.0193 round off)  how did you get 0.0194 ?
thankyou so much
+5 votes

Answer would be 0.0194

by Active (2.3k points)
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.

–1 vote
replacing a dirty page by default include page fault service time also ?
–3 votes

Answer should be (c) 0.514

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)
by evaluating, we will get p = 0.514

by Active (1.3k points)
you evaluate it wrong....p=0.0194 and p= -0.514
answer is p=0.0194, please check your calculation.

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
49,845 questions
54,785 answers
80,451 users