Question
Access the page replacement simulator referenced in this section. This and other animations are available here: http://williamstallings.com/COA/Animation/Links.html.
What is the minimum number of page frames required in a system for which the following list of references will hit at least 50% of the time? You will need to copy and paste the list of references into the simulator.
19 4 3 5 9 9 1 7 6 16 8 8 4 3 10 8 19 15 1 15 8 2 10 7 11 18 17 15 19 9 16 15 19 1 8 6 5 17 5 19 12 12 4 2 14 9 17 20 18 1 18 12 13 11 20 6 17 14 9 7 9 3 13 20 2 15 8 15 20 7 7 10 20 19 1 19 18 5 7 18 13 11 17 12 20 10 18 9 13 3 6 14 5 13 2 19 3 19 6 7
Explanation / Answer
Checked using the simulator, the minimum number of page frsmes required is 6 using the optimal page replacement alogorithm for which the hit ratio is 50%.
Please find the simulator output below for 6 frames optimal algorithm.
* PT = Page Trace, PF = Page Frame
Number of Page Frames = 6
Total Number of References = 100
Number of Hits = 50
Number of Misses = 50 (Cold_start_Misses =6)
HitRatio = 0.5
PT PF 0 PF 1 PF 2 PF 3 PF 4 PF 5 Hit/Miss 19 19 Miss 4 19 4 Miss 3 19 4 3 Miss 5 19 4 3 5 Miss 9 19 4 3 5 9 Miss 9 19 4 3 5 9 Hit 1 19 4 3 5 9 1 Miss 7 19 4 3 7 9 1 Miss 6 19 4 3 7 6 1 Miss 16 19 4 3 7 16 1 Miss 8 19 4 3 7 8 1 Miss 8 19 4 3 7 8 1 Hit 4 19 4 3 7 8 1 Hit 3 19 4 3 7 8 1 Hit 10 19 4 10 7 8 1 Miss 8 19 4 10 7 8 1 Hit 19 19 4 10 7 8 1 Hit 15 19 15 10 7 8 1 Miss 1 19 15 10 7 8 1 Hit 15 19 15 10 7 8 1 Hit 8 19 15 10 7 8 1 Hit 2 19 15 10 7 2 1 Miss 10 19 15 10 7 2 1 Hit 7 19 15 10 7 2 1 Hit 11 19 15 11 7 2 1 Miss 18 19 15 11 18 2 1 Miss 17 19 15 17 18 2 1 Miss 15 19 15 17 18 2 1 Hit 19 19 15 17 18 2 1 Hit 9 19 15 17 9 2 1 Miss 16 19 15 17 16 2 1 Miss 15 19 15 17 16 2 1 Hit 19 19 15 17 16 2 1 Hit 1 19 15 17 16 2 1 Hit 8 19 15 17 8 2 1 Miss 6 19 15 17 6 2 1 Miss 5 19 5 17 6 2 1 Miss 17 19 5 17 6 2 1 Hit 5 19 5 17 6 2 1 Hit 19 19 5 17 6 2 1 Hit 12 19 12 17 6 2 1 Miss 12 19 12 17 6 2 1 Hit 4 4 12 17 6 2 1 Miss 2 4 12 17 6 2 1 Hit 14 14 12 17 6 2 1 Miss 9 14 12 17 6 9 1 Miss 17 14 12 17 6 9 1 Hit 20 14 12 17 6 20 1 Miss 18 18 12 17 6 20 1 Miss 1 18 12 17 6 20 1 Hit 18 18 12 17 6 20 1 Hit 12 18 12 17 6 20 1 Hit 13 18 13 17 6 20 1 Miss 11 11 13 17 6 20 1 Miss 20 11 13 17 6 20 1 Hit 6 11 13 17 6 20 1 Hit 17 11 13 17 6 20 1 Hit 14 11 13 17 14 20 1 Miss 9 11 13 17 9 20 1 Miss 7 11 13 7 9 20 1 Miss 9 11 13 7 9 20 1 Hit 3 11 13 7 3 20 1 Miss 13 11 13 7 3 20 1 Hit 20 11 13 7 3 20 1 Hit 2 11 13 7 2 20 1 Miss 15 11 13 7 15 20 1 Miss 8 8 13 7 15 20 1 Miss 15 8 13 7 15 20 1 Hit 20 8 13 7 15 20 1 Hit 7 8 13 7 15 20 1 Hit 7 8 13 7 15 20 1 Hit 10 8 13 7 10 20 1 Miss 20 8 13 7 10 20 1 Hit 19 19 13 7 10 20 1 Miss 1 19 13 7 10 20 1 Hit 19 19 13 7 10 20 1 Hit 18 19 13 7 10 20 18 Miss 5 5 13 7 10 20 18 Miss 7 5 13 7 10 20 18 Hit 18 5 13 7 10 20 18 Hit 13 5 13 7 10 20 18 Hit 11 5 13 11 10 20 18 Miss 17 5 13 17 10 20 18 Miss 12 5 13 12 10 20 18 Miss 20 5 13 12 10 20 18 Hit 10 5 13 12 10 20 18 Hit 18 5 13 12 10 20 18 Hit 9 5 13 12 10 20 9 Miss 13 5 13 12 10 20 9 Hit 3 5 13 12 10 20 3 Miss 6 5 13 12 10 6 3 Miss 14 5 13 12 14 6 3 Miss 5 5 13 12 14 6 3 Hit 13 5 13 12 14 6 3 Hit 2 5 13 12 2 6 3 Miss 19 5 13 12 19 6 3 Miss 3 5 13 12 19 6 3 Hit 19 5 13 12 19 6 3 Hit 6 5 13 12 19 6 3 Hit 7 5 13 12 19 6 7 Miss