Given the following stream of page references, calculate the number of page faul

Question

Given the following stream of page references, calculate the number of page faults with different types of page replacement algorithms. Assume that all frames are initially free. Assume that there are three frames. Reference page list: 1 2 3 4 1 2 5 1 2 3 4 5 2 1 2 Find the miss rate for FIFO, LRU, and OPT (optimal) page replacement policies, as well as the final configuration of the three frames for each type of policy. Is it true that if we increase the number of frames from 3 to 4, the number of page faults always decreases (or stays the same) using FIFO page replacement? What about the OPT page replacement?

Explanation / Answer

FIFO with 3 Frames:

1 2 3 ->3PF

4 2 3 -> 4PF

4 1 3 -> 5

4 1 2 -> 6

5 1 2-> 7

5 1 2

5 1 2

5 3 2 ->8

5 3 4->9

5 3 4

2 3 4->10

2 1 4 -> 11

11 Page faults and miss rate is 7/15=0.46

LRU with 3 Frames:

1 2 3 ->3PF

1 2 4 ->4PF

1 2 4

1 2 4

1 5 4 -> 5

1 5 4

1 2 4 ->6

1 3 4 ->7

1 3 5->8

1 3 2->9

1 3 2

1 3 2

9 Page Faults and miss rate 6/15=0.4

OPTIMAL with 3 Frames:

1 2 3 ->3PF

1 2 4 ->4PF

1 2 4

1 2 4

1 2 5 ->5

1 2 5

1 2 5

3 2 5 ->6

4 2 5 ->7

4 2 5

4 2 5

1 2 5 ->8

1 2 5

8 Page Faults and miss rate is 7/15=0.46

FIFO with 4 frames:

1 2 3 4 ->4PF

1 2 3 4

1 2 3 4

5 2 3 4 ->5PF

5 1 3 4 ->6

5 1 2 4 ->7

5 1 2 3 ->8

4 1 2 3 ->9

4 5 2 3 ->10

4 5 2 3

4 5 1 3 ->11

4 5 1 2 ->12

12 Page Faults. Generally if frames increases number of page faults decreases. But in FiFO this may not happen. This is called Balady’s Anamoly.

OPTIMAL with 4 Frames:

1 2 3 4 ->4PF                4 2 3 5    

1 2 3 4                           4 2 3 5 ->3

1 2 3 4                          1 2 3 5 ->4

1 2 3 5 ->1PF              4 Page Faults

1 2 3 5

1 2 3 5

1 2 3 5

4 2 3 5

Related Questions

Navigate

• Browse (All)
• Browse G
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.