GATE CSE 1998 | Question: 2.18, UGCNET-June2012-III: 48

Question

If an instruction takes $i$ microseconds and a page fault takes an additional $j$ microseconds, the effective instruction time if on the average a page fault occurs every $k$ instruction is:

• A. $i + \dfrac{j}{k}$

• B. $i +(j\times k)$

• C. $\dfrac{i+j}{k}$

• D. $({i+j})\times {k}$

Comments

Effective $m_{acc}$ time=  $(1-p) *m_{acc} + (p)*P_{faults}$ Here $P_{faults}$ means time needed to service Page fault.

---

simple aptitude que, no knowledge of OS required here

---

let say this happens:

(i + i + i + i + ... + i + i) k times + j(1 page fault after every k instructions)

= ki + j

for a single instruction average time divide the whole by k, as average = sum of all observation/total observations.

Answer 1

Page fault rate $=\dfrac{1}{k}$
Page hit rate $=1-\dfrac{1}{k}$
Service time $=i$
Page fault service time $= i+j$

Effective memory access time,

$\quad =\dfrac{1}{k}\times (i+j)+\left(1-\dfrac{1}{k}\right)\times i$

$\quad=\dfrac{(i+j)}{k}+i-\dfrac{i}{k}$

$\quad=\dfrac{i}{k}+\dfrac{j}{k}+i-\dfrac{i}{k}$

$\quad=i+\dfrac{j}{k}$

So, option (A) is correct.

Comments

n = no of instructions

EIT =  ( n(i) + (n/k)j )/ n

= n[i + j/k] n

= i + j/k

---

Given that, on average page fault occurs every k instructions

after every k instruction → 1 page fault occurs

then, after 1 instruction → 1/k page fault occurs

i.e probability that for a given instruction page fault would occur is 1/k

this is the page fault rate (in terms of instructions ‘k’)

---

finally after 2 yrs of preparation understood this easy question 😂

Answer 2

Lets take a example

no of instruction =6

i=4(Normal instrction execution time)

j=2(Additional time incase of page fault)

k=3(Page fault occurs on every k^th instruction)

Total time required=4+4+(4+2)+4+4+(4+2)=28

Average time=28/6=4.66

Now substitute the i,j,k values in options 

i+j/k=4+2/4=4.66

so A is the answer

Comments

Good One

Thanks

---

smart

Answer 3

Here, given that On an average page fault occurs at every 'k' seconds. So, probability of getting a page fault is (1/k).

 

Effective Instruction Time = Normal instruction execution Time + Average Page Fault Service Time

i.e. Avg Page Fault Service Time = prob. of getting page fault * page fault service time =(1/k )* j

 

so its "i + (1/k)*j".

Answer 4

One more way could be. Let us we have 100 instruction then page fault will occur 100/k times. So

Total execution time  = 100*i +  (100/k)*j

So avg execution time  = (Total execution time)/(Total number of instruction) = i + (j/k).

 

Answer is (A) Part.

Answer 5

Consider k instructions: 

instruction #	1	2	3	...	k
time	i	i	i	...	i+j

Effective instruction time = (i*k + j)/k = i + j/k.

Answer 6

1 instruction takes i ms.

k instructions will take k*i ms.

1 page fault in every k instructions. Page Fault Service Time is j ms.

So,

Total time required to execute k instructions is (k*i+j) ms.

 

so here ,

Effective instruction time = (k*i+j)/k

i.e, i + j/k