GATE CSE 1992 | Question: 12-b

Question

Let the page reference and the working set window be $c\ c\ d\ b\ c\ e\ c\ e\ a\ d\ $ and $4$, respectively. The initial working set at time $t=0$ contains the pages $\{a,d,e\}$, where $a$ was referenced at time $t=0$, $d$ was referenced at time $t=-1$, and $e$ was referenced at time $t=-2$. Determine the total number of page faults and the average number of page frames used by computing the working set at each reference.

Comments

any one please explain how this procedure is working here ...

---

please explain @arjun_sir

---

Good read

https://web.stanford.edu/~ouster/cgi-bin/cs140-winter12/lecture.php?topic=thrashing

---

Please go through Page No. 13 and 14 of the PDF shared by @saurabh rai at the link http://www.cs.utexas.edu/users/witchel/372/lectures/16.PageReplacementAlgos.pdf

Answer 1

Window size of working set $= 4$

Initial pages in the working set window $=    \{  e, d, a\}$

$$\small \begin{array}{|c|c|c|c|}\hline \textbf{Incoming page}  &  \textbf{Time} & \textbf{Working set window} & \textbf{Hit/ Miss} & \textbf{Current window size} \\\hline  c  & 1 &  \{ e, d, a, c\} & \textbf{miss} & 4 \\\hline   c  & 2 &  \{ d, a, c\} & \text{hit} & 3 \\\hline d  & 3 &  \{ a, c,d\} & \text{hit} & 3 \\\hline b & 4 &  \{ c,d,b\} & \textbf{miss} & 3  \\\hline   c  & 5 &  \{ d, b, c\} & \text{hit} & 3 \\\hline e & 6 &  \{ d,b,c,e \} & \textbf{miss} & 4 \\\hline   c  & 7 &  \{ b, c,e\} & \text{hit} & 3 \\\hline   e & 8 &  \{c,e\} & \text{hit} & 2  \\\hline a & 9 &  \{c,e,a \} & \textbf{miss} & 3 \\\hline d & 10 &  \{c,e,a,d \} & \textbf{miss} & 4   \\\hline \end{array}$$

---

Total number of page faults $=\mathbf{ 5}$.

Average no. of page frames used by window set $= ( 4 + 3 + 3 + 3 + 3 + 4 + 3 + 2 + 3 + 4) / 10 = 32/10 = \mathbf{3.2}$

Comments

@flash12 The sequence hasn't been changed. In fact, the head of the queue is taken to be on the extreme right, i.e., $a$ is the most recently accessed page, and $e$ is the least recently accessed.

---

why we are using FIFO page replacement why not Optimal?

---

Because Optimal algorithms replaces the page which will not be referred for so long in future. (how can we predict the future?). Although it can not be practically implementable but it can be used as a benchmark. Other algorithms are compared to this in terms of optimality.

Answer 2

average frame requirement$=3.2,$page faults$=5$

 

Comments

@NIthIsh check now!

---

Thank you so much! @ sudsho

Answer 3

 

 

According to Operating system concepts ...

Thus after interval of every 4units for each page we will remove it from working set model. If page hit occurs we will update timestamp of that page,hence page which is not referenced after 4unit( in this  case) of time after its previous reference will be removed from working set .

Answer 4

Average number of page frames => 3.2

Total Page Faults => 5

Comments

no ans is 3 if working set size is 4

and ans is 5 if working set size is 3

---

The working set window starts with a size of 3 i.e. {a,d,e}. As the clock ticks 1, the window slides right by one and now looks at {a,d,e,c}. Now proceeding similarly we get the working sets as follows:

1st unit of time -> {a,d,e,c}, 2 -> {d,e,c}, 3 -> {c,d,b}, 4 -> {d,b,c,e}, 5 -> {b,c,e}, 6 -> {c,e}, 7 -> {e,a,c}, 8 -> {c,e,a,d}.

To find the average number of page frames, we do the foll:

Avg. No. of frames = (4 frames of size-3 + 3 frames of size-4 + 1 frame of size-2) / 8  = (4*3 + 4*3 + 2*1) / 8

 = 3.25 frames in average.

By observing the working set at each step we can find that there are 5 page faults in total.

---

it is one type of page replacement algo called as working set page replacement algoithm 
for more ref go to http://www.cs.utexas.edu/users/witchel/372/lectures/16.PageReplacementAlgos.pdf

Answer 5

The total number of page faults (Miss) = 5

Average no. of page frames used by window set = (4+3+3+3+3+4+3+2+3+4) /10

=32/10 =3.2

Answer 6

Total number of page faults would be 4.  Page fault occures for the frames 1,4,6,10.

How to calculate avg number of page frames?