The Gateway to Computer Science Excellence
+40 votes
6.5k 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$
in Operating System by Boss (16.3k points)
edited by | 6.5k views
0
why are we not taking 2 memory access in case of no page fault(one for page table other for memory)
+2
Admins, Please verify options
0
@prayas

given memory access time(1 unit) includes that already.
+1
Can someone clarify how can a page be dirty when there is a page fault? Page fault means that the page is not in the main memory, right? And dirty page means that the page is in the main memory, and has been modified since it was copied from the secondary memory. How can these two properties be satisfied at the same time?
+2

@ This means suppose Page fault occurs and there is no free frame in Main memory then the page which we want to replace is dirty it's probability is 'p' , Which implies it will take more time in page fault service since OS will also have to write back to secondary memory and then bring the required page to MM.

0

@sags.sharma Got it. Thanks!

5 Answers

+52 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
+2

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

+1
according to question the equation can be satisfied by option c (approx)
+2
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?
+1
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.
0
why are we not taking 2 memory access in case of no page fault(one for page table other for memory)
+1
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
0
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
+3
@ 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.
0
@bharti why will it include both the times? There is no hint regarding the same in the question also
0
@ 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 .
0
Same doubt!!
+1
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
+4

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 ?

+1
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?
+1

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.

+1
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
0

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

0
Are we neglecting memory access time here ?
0
p ( p(300+100) + (1-p)(100)) + (1-p) *2 = 3

is this correct?
0
Same doubt to me also...please reply someone and explain it..
+23 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 (17k points)
+1
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
0
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.
0
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 ?
0
thankyou so much
+7 votes

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

 

by Active (3.5k points)
edited by
0
best one.

just one modification.

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

 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 ?
by
–3 votes

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

by Active (1.3k points)
+1
you evaluate it wrong....p=0.0194 and p= -0.514
+2
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
50,647 questions
56,466 answers
195,381 comments
100,310 users