edited by
22,505 views
72 votes
72 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$
edited by

4 Answers

Best answer
86 votes
86 votes
$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.$$
edited by
36 votes
36 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
32 votes
32 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

 

edited by
–2 votes
–2 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

Answer:

Related questions

62 votes
62 votes
11 answers
4
Ishrat Jahan asked Oct 29, 2014
28,939 views
Consider a hash function that distributes keys uniformly. The hash table size is $20$. After hashing of how many keys will the probability that any new key hashed collide...