Find a page frame with the smallest counter. In case of tie, FIFO is to be adopted. No. of page frames available is 4.
Initially, 4 page faults for references 1 2 3 4.
Frame 1 2 3 4
Page 1 2 3 4
Count 1 1 1 1
Then, when 5 comes, all frames have equal count (=1), so we use FIFO to replace page 1. Now faults=5
Frame 1 2 3 4
Page 5 2 3 4
Count 2 1 1 1
Next, 3 and 4 comes, already there. So no fault. Then 1 comes. faults = 6. We replace page 2 (frames 2 3 and 4 have equal count of 1 so we apply FIFO).
Frame 1 2 3 4
Page 5 1 3 4
Count 2 2 1 1
Then 6 comes. faults = 7. We replace 3.
Frame 1 2 3 4
Page 5 1 6 4
Count 2 2 2 1
Then 7 comes. faults = 8. We replace 4.
Frame 1 2 3 4
Page 5 1 6 7
Count 2 2 2 2
Next, 8 comes. Again faults. No. of faults = 9. We replace 5.
Frame 1 2 3 4
Page 8 1 6 7
Count 3 2 2 2
Next 7 and 8 comes. already there, so no fault. Then 9 comes. It faults. No. of faults = 10. We replace 1.
Frame 1 2 3 4
Page 8 9 6 7
Count 3 3 2 2
Next 7 8 and 9 does not fault. Then comes 5. It faults. No. of faults = 11. We replace 6.
Frame 1 2 3 4
Page 8 9 5 7
Count 3 3 3 2
Then comes 4. Faults = 12. We replace 7.
Frame 1 2 3 4
Page 8 9 5 4
Count 3 3 3 3
Next 5 and 4 comes. No fault. Then comes 2. It faults. Faults = 13. We replace 8.
Frame 1 2 3 4
Page 2 9 5 4
Count 4 3 3 3
Therefore, total faults = 13.