Evaluieren optimalen Ersetzungsalgorithmus für 5 Rahmen

Question

Frage:

Betrachten Sie die folgende Seite Referenz string: 1, 2, 3, 4, 2, 1, 5, 6, 2, 1, 2, 3, 7, 6, 3, 2, 1, 2, 3, 6.

Wie viele Seitenfehler würden für die optimalen Seitenersetzungsalgorithmen auftreten, unter der Annahme von fünf Frames? Denken Sie daran, dass alle Frames zu Beginn leer sind. Ihre ersten einzelnen Seiten kosten also jeweils einen Fehler.

Ich bin nicht ganz sicher, was passieren würde:

1 -> 1 
2 -> 1, 2 
3 -> 1, 2, 3 
4 -> 1, 2, 3, 4, 
2 -> What happens here?? 
1 
...etc (with the rest of the reference string) 

Answer 1

Es 7 Seitenfehler insgesamt sein wird.

1 -> 1 
2 -> 1, 2 
3 -> 1, 2, 3 
4 -> 1, 2, 3, 4 
2 -> 1, 2, 3, 4 (This is a hit 2 is already in the memory) 
1 -> 1, 2, 3, 4 
5 -> 1, 2, 3, 4, 5 (This is a miss but we have 5 frames.) 
6 -> 1, 2, 3, 6, 5 (4 will be replaced as it is not required in future) 
...