Belady-Anomalie

Belady-Anomalie

FIFO-Anomalie (Belady‘s Anomalie) bezeichnet ein in der Informatik auftretendes Phänomen, das bei Anwendung der FIFO-Ersetzungsstrategie für Virtuelle Speicherverwaltung in Computer-Systemen auftreten kann.

Erklärung

Man spricht von einer FIFO-Anomalie, wenn bei der virtuellen Speicherverwaltung in Computer-Systemen mit größerem Hauptspeicher mehr Seitenfehler auftreten, als in Systemen mit kleinerem Hauptspeicher. Das liegt daran, dass die FIFO Strategie den neusten Speicherblock als erstes überschreibt, auch wenn dieser vielleicht der am häufigsten genutzte ist.

Ein Beispiel der FIFO-Anomalie. Mit 3 Seitenrahmen treten 9 Seitenfehler auf. Die Erhöhung auf 4 Seitenrahmen verursacht 10 Seitenfehler. Seitenfehler sind in rot dargestellt.

Seitenanfragen 3 2 1 0 3 2 4 3 2 1 0 4
Neueste Seite 3 2 1 0 3 2 4 4 4 1 0 0
    3 2 1 0 3 2 2 2 4 1 1
Älteste Seite     3 2 1 0 3 3 3 2 4 4
Seitenanfragen 3 2 1 0 3 2 4 3 2 1 0 4
Neueste Seite 3 2 1 0 0 0 4 3 2 1 0 4
    3 2 1 1 1 0 4 3 2 1 0
      3 2 2 2 1 0 4 3 2 1
Älteste Seite       3 3 3 2 1 0 4 3 2

Vermeidung

In der Regel ist die Least recently used-Strategie (LRU) („gerade am wenigsten verwendet“) FIFO vorzuziehen, da LRU Speicherseiten, die kürzlich benutzt wurden, nicht ersetzt. LRU kann aber zu FIFO degenerieren, d.h., wenn in Folge Speicherseiten angefordert werden, die nicht zusammenhängen, verhält sich LRU genau wie FIFO.

Eine weitere Strategie zur Vermeidung der FIFO-Anomalie ist der "Second-Chance-Algorithmus". Hierbei wird jede Speicherseite, bei einem Zugriff, mit einem Zugriffsbit markiert und ein zyklischer Zeiger setzt das Zugriffsbit wieder auf 0. Ein zweiter Zeiger, der hinter dem ersten Zeiger liegt, prüft, ob in der Zwischenzeit ein erneuter Zugriff stattgefunden hat und gibt der Speicherseite gegebenenfalls eine neue Chance. Findet der zweite Zeiger den Eintrag unmarkiert vor, so wird die Speicherseite entfernt.


Wikimedia Foundation.

Игры ⚽ Нужно сделать НИР?

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Anomalie De Belady — L anomalie de Belady est une anomalie de comportement observée en informatique pour l algorithme de remplacement des lignes de cache Fifo. Augmenter le nombre de voies de la mémoire cache peut accroître le taux de défauts de cache. Ce phénomène n …   Wikipédia en Français

  • Anomalie de belady — L anomalie de Belady est une anomalie de comportement observée en informatique pour l algorithme de remplacement des lignes de cache Fifo. Augmenter le nombre de voies de la mémoire cache peut accroître le taux de défauts de cache. Ce phénomène n …   Wikipédia en Français

  • Anomalie de Belady — L anomalie de Belady est une anomalie de comportement observée en informatique pour l algorithme de remplacement des lignes de cache FIFO. Augmenter le nombre de voies de la mémoire cache peut accroître le taux de défauts de cache. Ce phénomène n …   Wikipédia en Français

  • FIFO-Anomalie — (Belady s Anomalie) bezeichnet ein in der Informatik auftretendes Phänomen, das bei Anwendung der FIFO Ersetzungsstrategie für Virtuelle Speicherverwaltung in Computer Systemen auftreten kann. Erklärung Man spricht von einer FIFO Anomalie, wenn… …   Deutsch Wikipedia

  • Kachelverwaltung — Als Paging (vgl. engl. page Speicherseite) oder deutsch Kachelverwaltung bezeichnet man die Methode der Arbeitsspeicher Verwaltung per Seitenadressierung durch Betriebssysteme. Dabei wird häufig aus Effizienzgründen die sogenannte Memory… …   Deutsch Wikipedia

  • Thrashing — Als Paging (vgl. engl. page Speicherseite) oder deutsch Kachelverwaltung bezeichnet man die Methode der Arbeitsspeicher Verwaltung per Seitenadressierung durch Betriebssysteme. Dabei wird häufig aus Effizienzgründen die sogenannte Memory… …   Deutsch Wikipedia

  • Working Set — Als Paging (vgl. engl. page Speicherseite) oder deutsch Kachelverwaltung bezeichnet man die Methode der Arbeitsspeicher Verwaltung per Seitenadressierung durch Betriebssysteme. Dabei wird häufig aus Effizienzgründen die sogenannte Memory… …   Deutsch Wikipedia

  • Workingset — Als Paging (vgl. engl. page Speicherseite) oder deutsch Kachelverwaltung bezeichnet man die Methode der Arbeitsspeicher Verwaltung per Seitenadressierung durch Betriebssysteme. Dabei wird häufig aus Effizienzgründen die sogenannte Memory… …   Deutsch Wikipedia

  • Memoire virtuelle — Mémoire virtuelle En informatique, le mécanisme de mémoire virtuelle a été mis au point dans les années 1960. Il est basé sur l utilisation d une mémoire de masse (type disque dur ou anciennement un tambour), pour le but, entre autres, de… …   Wikipédia en Français

  • Mémoire Virtuelle — En informatique, le mécanisme de mémoire virtuelle a été mis au point dans les années 1960. Il est basé sur l utilisation d une mémoire de masse (type disque dur ou anciennement un tambour), pour le but, entre autres, de permettre à des… …   Wikipédia en Français

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”