TIFR CSE 2013 | Part B | Question: 14

Question

Assume a demand paged memory system where ONLY THREE pages can reside in the memory at a time. The following sequence gives the order in which the program references the pages.
         $1, 3, 1, 3, 4, 2, 2, 4$
Assume that least frequently used page is replaced when necessary. If there is more than one least frequently used pages then the least recently used page among them is replaced. During the program’s execution, how many times will the pages $1,2,3$ and $4$ be brought to the memory?

• A. $2,2,2,2$ times, respectively
• B. $1,1,1,2$ times, respectively
• C. $1,1,1,1$ times, respectively
• D. $2,1,2,2$ times, respectively
• E. None of the above

Answer 1

Page reference order: $1,3,1,3, 4,2,2,4$

First $2$ pages causes page fault. i.e., $1$ and $3$

Next $2$ pages no fault.

Next page i.e., $4$ fault occurs.

Now for page no. $2$ we have fault. We will replace less frequently used i.e., $4$

Next page is again $2$ so no. page fault.

Now page no. $1 2$ and $3$ all are used $2$ times so, we will replace page $1$ to accomodate page $4$ (least recently used is $1$)

So, page $1 2 3$ are brought once in memory and page $4$ is brought two times. So, answer is (B).

Comments

@ makhdoom ghaya pls expain this 

---

answer : B

---

Why 2 replaced 4 why don't it replace 1 as question stating replace with "lest recently" and 4 {most recently } and 1{lest recently} someone clarify this?

---

indirectly they are asking no. of page faults with respective page number

Answer 2

Step 1 :- Demand of page 1 , which is not present in memory.

1

Step 2 :- Demand of page 3 , which is not present in memory.

1

3

Step 3 :- Demand of page 1 , which is already present in memory.

Step 4 :- Demand of page 3 , which is already present in memory.

Step 5 :- Demand of page 4 , which is not present in memory.

1

3

4

Step 6 :- Demand of page 2 , which is not present in memory.

Here we don't have any free frame left in physical memory , so we have to remove some frame based on least frequently used page replacement algorithm.

page 1 : frequency =2 (used two times)

Page 3 : frequency=2  (used two times)

page 4 : frequency=1 (used one time)          // least frequently used so this wil be selected for replacement.

1

3

2

Step 7 :- Demand of page 2 , which is already present in memory.

Step 8 :- Demand of page 4 , which is not present in memory.

page 1 :- frequency =2 (used two times)

page 3 :-frequency =2 (used two times)

page 2 :-frequency =2 (used two times)

Here when everyone has same frequency so use help of least recently used page replacement algorithm. Here we can see page 1 is the least recently used page so replace this with page 4.

4

3

2

Now we can observe , which page is brought , how many number of times in main memory.

The pages $1,2,3$ and $4$ be brought to the memory $1,1,1,2 $ times, respectively.

Comments

got it sir.

---

Awesome! @ Rupendra Choudhary Job well done, bud! :)

---

This should definitely be the best answer.

Answer 3

So, answer is option (B)

     1   is brought once (1)

     2   is brought once (1)

     3   is brought once (1)

     4   is brought twice (2)

 

1	3	1	3	4	2	2	4
1	1			1	1		4
	3			3	3		3
				4	2		2