retagged by
11,072 views
41 votes
41 votes
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.
retagged by

6 Answers

Best answer
61 votes
61 votes

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}$

edited by
22 votes
22 votes

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

 

edited by
5 votes
5 votes
Average number of page frames => 3.2

Total Page Faults => 5
4 votes
4 votes

 

 

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:

Related questions

10 votes
10 votes
2 answers
1
Kathleen asked Sep 13, 2014
3,474 views
Draw the precedence graph for the concurrent program given belowS1 parbegin begin S2:S4 end; begin S3; parbegin S5; begin S6:S8 end parend end; S7 parend; S9
7 votes
7 votes
2 answers
2
go_editor asked Apr 24, 2016
3,285 views
Let $S$ be the set of all integers and let $n 1$ be a fixed integer. Define for $a,b \in S, a R b$ iff $a-b$ is a multiple of $n$. Show that $R$ is an equivalence relat...
24 votes
24 votes
4 answers
4
Kathleen asked Sep 13, 2014
5,356 views
A computer system has $6$ tape devices, with n processes competing for them. Each process may need $3$ tape drives. The maximum value of n for which the system is guarant...