webentwicklung-frage-antwort-db.com.de

Kann Beladys Anomalie nicht verstehen

Laut Beladys Anomaly haben wir also, wenn Sie eine FIFO -Seiten-Ersetzungsrichtlinie verwenden, beim Hinzufügen von mehr Seitenraum mehr Seitenfehler.

Meine Intuition sagt, dass wir weniger oder höchstens so viele Seitenfehler machen sollten, wie wir mehr Seitenraum hinzufügen.

Wenn wir uns eine Warteschlange FIFO als Pipe vorstellen, ist das Hinzufügen von mehr Seitenraum wie das Vergrößern der Pipe:

 ____
O____O  size 4

 ________
O________O  size 8

Warum würden Sie also mehr Seitenfehler bekommen? Meine Intuition besagt, dass Sie mit einer längeren Pipe etwas länger brauchen würden, um Seitenfehler zu bekommen (also mit einer unendlichen Pipe hätten Sie keine Seitenfehler) und dann genauso viele Seitenfehler und genauso oft wie bei einer kleineren Pfeife.

Was stimmt nicht mit meiner Begründung?

30

Der Grund, dass bei der Verwendung von FIFO die Anzahl der Seiten erhöht werden kann, kann die Fehlerrate in einigen Zugriffsmustern erhöhen. Der Grund dafür ist, dass kürzlich angeforderte Seiten länger in der Warteschlange FIFO verbleiben können.

Betrachten Sie das dritte Mal, dass "3" im Wikipedia-Beispiel hier angefordert wird: http://en.wikipedia.org/wiki/Belady%27s_anomaly

Seitenfehler sind mit einem "f" gekennzeichnet.

1:

Page Requests   3    2    1    0    3    2    4    3    2    1    0    4
Newest Page     3f   2f   1f   0f   3f   2f   4f   4    4    1f   0f   0
                     3    2    1    0    3    2    2    2    4    1    1
Oldest Page               3    2    1    0    3    3    3    2    4    4

2:

Page Requests   3    2    1    0    3    2    4    3    2    1    0    4
Newest Page     3f   2f   1f   0f   0    0    4f   3f   2f   1f   0f   4f
                     3    2    1    1    1    0    4    3    2    1    0
                          3    2    2    2    1    0    4    3    2    1
Oldest Page                    3    3    3    2    1    0    4    3    2

Im ersten Beispiel (mit weniger Seiten) gibt es 9 Seitenfehler.

Im zweiten Beispiel (mit mehr Seiten) gibt es 10 Seitenfehler.

Wenn Sie den FIFO-Speicher verwenden, ändert sich die Reihenfolge, in der Elemente entfernt werden, wenn Sie den Cache vergrößern. Dies kann in einigen Fällen die Fehlerrate erhöhen.

Beladys Anomalie sagt nichts über den allgemeinen Trend der Fehlerraten in Bezug auf die Cachegröße aus. Ihre Argumentation (über das Betrachten des Caches als Pipe) ist im Allgemeinen nicht falsch.

Zusammenfassend: Beladys Anomaly weist darauf hin, dass die Tatsache ausgenutzt werden kann, dass größere Cache-Größen dazu führen können, dass Elemente im Cache später in der Warteschlange FIFO angehoben werden, als kleinere Cache-Größen, um größere zu verursachen Cache-Größen für eine höhere Fehlerrate bei einem bestimmten (und möglicherweise seltenen) Zugriffsmuster.

32
Olhovsky

Diese Aussage ist falsch, weil sie übergeneralisiert ist:

Die Anomaly von Belady besagt, dass bei der Verwendung einer FIFO -Seiten-Ersetzungsrichtlinie beim Hinzufügen von mehr Seitenraum mehr Seitenfehler auftreten

Dies ist eine korrigierte Version:

"Beladys Anomalie gibt an, dass bei Verwendung einer FIFO - Seitenersetzungsrichtlinie beim Hinzufügen von mehr Seitenraum einige Speicherzugriffsmuster tatsächlich mehr Seitenfehler verursachen.

Mit anderen Worten ... Ob die Anomalie beobachtet wird, hängt vom tatsächlichen Speicherzugriffsmuster ab.

7

Beladys Anomalie tritt beim Seitenersetzungsalgorithmus nicht auf den Stapelalgorithmus auf. Dies bedeutet, dass die Seiten, bei denen die Anzahl der Frames geringer war, eine Untermenge der Seiten sein sollten, wenn der Frame mehr ist kann in FIFO manchmal vorkommen, sogar zufälliger Seitenaustausch, aber nicht LRU oder optimal.

1
Surajit