Page Fault Algorithms

Using the page reference sequence 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5 determine the number of page faults which will occur for FIFO, Optimal, and LRU page replacement algorithms. Assume that three page frames are available and that they are initially empty?

FIFO

In Memory			Time	Request	Swap-in	Swap-out	Note
How much frames? (Example is 3)
-	-	-		1	1
1	-	-		2	2
1	2	-		3	3
1	2	3		4	4	1
4	2	3		1	1	2
4	1	3		2	2	3
4	1	2		5	5	4
5	1	2		1
5	1	2		2
5	1	2		3	3	1
5	3	2		4	4	2
5	3	4		5

Optimal(最短時間不會用到的)

In Memory			Time	Request	Swap-in	Swap-out	Note
How much frames? (Example is 3)
-	-	-		1	1
1	-	-		2	2
1	2	-		3	3
1	2	3		4	4	3
1	2	4		1
1	2	4		2
1	2	5		5	5	4
1	2	5		1
1	2	5		2
3	2	5		3	3	1
3	4	5		4	4	2
3	4	5		5

LRU(替換最久時間未用到的)

In Memory			Time	Request	Swap-in	Swap-out	Note
How much frames? (Example is 3)
-	-	-		1	1
1	-	-		2	2
1	2	-		3	3
1	2	3		4	4	1
4	2	3		1	1	2
4	1	3		2	2	3
4	1	2		5	5	4
5	1	2		1
5	1	2		2
3	1	2		3	3	5
3	4	2		4	4	1
3	4	5		5	5	2