Hi 
Weiß jemand, wie Anomalie von Belady mit FIFO funktioniert?
Die Theorie nochmal aufgedröselt, und ich könnte es auch nicht besser beschreiben …
http://de.wikipedia.org/wiki/FIFO-Anomalie
Um die Anomalie zu sehen, müstest Du die Tabelle noch einmal machen, aber diesmal mit einem Rechner mit mehr Speicherseiten, z.B. 4. Unter unglücklichen Umständen würdest Du - so wie im Wikipedia Artikel gut ebschrieben - feststellen, dass mehr Seitenfehlöer auftreten, anstatt wie durch den größeren Hauptspeicher zu vermuten war - weniger.
Die Erklärung liefert ein kurzer Blick auf die Häufigkeit, mit der sich Seiten ändern. Aus Deinem Beispiel:
0 (4)
1 (4)
2 (4)
3 (3)
4 (2)
5 (3)
0,1 und 2 werden wie Du siehst relativ häufig gebraucht, 4 dagegen selten. 3 und 5 liegen irgendwo in der Mitte. Wenn nun 4 doch mal eingelagert werden muss, verdrängt 4 ohne Rücksicht auf die Benutzungshäufigkeit eine Seite, die früher eingelagert wurde, also wahrscheinlich öfters die 0,1 oder 2. Es wäre aber effizienter, wenn es 3 oder 5 erwischen würde, da diese weniger oft gebraucht werden.
Das Beispiel funktioniert besser, wenn Du eine Tabelle aufstellst mit mehr Gegensätzen, z.B. die 0,1,2 (5) Mal, die 3,4,5 (2) Mal. Dann wäre es am Effizientesten, wenn eine der weniger genützten Seiten eine andere ihrer Art aus dem Speicher ballern würde, statt eine der häufig genützten Seiten, aber darauf nimmt FIFO ja keine Rücksicht. Also erwischt es oft eine 0,1,2 Seite. Da diese häufig gleich wieder gebraucht wird, und die beim Einlagern genauso doof vorgeht, ballert sie bei ihrem Einlagern höchst wahrscheinlich eine andere häufig genützte Seite raus, statt eine wenig gebrauchte Seite. Das kann, wenn die Einlagerungsreihenfolge unglücklich ausfällt, richtige „Lawinen“ auslösen, bei denen sich die häufig benötigten Seiten gegenseitig aus dem Speicher werfen, statt weniger genützte Seiten zu verdrängen.
Alternatove Speicherverwaltungen versuchen deshalb, häufiger genützte Seiten zu bevorzugen, auch wenn sie schon relativ lang im Speicher stehen, während FIFO die am längsten im Speicher stehenden Seiten gnadenlos verdrängt.
Lösung, aber ich verstehe es irgendwie nicht. Vielen Dank im
Voraus!!!
Freund, sorry, aber das ist nun wirklich kein Zauberkunststück, und zum Hausaufgaben machen bin ich mir echt zu schade.
Beachte alledings, dass die tabelle, die Du anführst, in der 2. und 3. Zeile um je 1 Stelle nach links verrutscht ist, weil das Editorfenster hier führende Leerzeichen abschneidet.
Korrekt lautet die Tabelle:
0 1 2 3 1 0 3 5 1 0 2 4 3 5 2 4 5 2 1 0
---------------------------------------
0 0 0 3 3 3 3 3 1 1 1 1 3 3 3 4 4 4 4 4 (5)
x 1 1 1 1 0 0 0 0 0 2 2 2 5 5 5 5 5 1 1 (5)
x x 2 2 2 2 2 5 5 5 5 4 4 4 2 2 2 2 2 0 (5)
---------------------------------------------
(15)
In Klammer die Anzahl der Seitenfehler (Fett schreiben ist mir hier zu mühsam, aber das ist nichts anderes als die Anzahl der Male, wo in einer Zeile eine Zahl gegen eine andere getauscht wird). Das erstmalige Belegen einer ungenutzten Seite (x) mit einer Zahl zählt auch als Seitenfehler.
Und um den Belady zu zeigen, müsstest Du die selbe Zahlensequenz nehmen und mit 4 Zeilen (=Speicherstellen) arbeiten. Dann würdest Du eventuell sehen, dass mehr Seitenfehler auftreten als mit 3 Speicherzellen. Ob Belady auftritt oder nicht hängt von der Zahlenfolge ab. Im Wikipedia-Beispiel wurde eine „günstige“ gewählt, und da findest Du auch die tabellen für 3 und 4 Speicherzellen.
Alles klar?
Armin.