imported>Müllt-Renner am 14. Mai 2024 um 15:26 Uhr

2024-05-14T15:26:51Z

Neue Seite

'''FIFO-Anomalie''' (engl. ''[[Laszlo Belady|Bélády]]’s anomaly'') bezeichnet ein in der [[Informatik]] auftretendes [[Phänomen]], das bei Anwendung der [[First In – First Out|FIFO-Ersetzungsstrategie]] für [[Virtuelle Speicherverwaltung]] in [[Computer]]-Systemen auftreten kann.

== Erklärung ==
Eine FIFO-Anomalie tritt auf, wenn bei der virtuellen Speicherverwaltung in Computer-Systemen mit größerem [[Arbeitsspeicher|Hauptspeicher]] mehr [[Seitenfehler]] auftreten als in Systemen mit kleinerem Hauptspeicher. Das liegt an der [[First In – First Out|FIFO]]-Strategie, die den ältesten Speicherblock als ersten überschreibt, selbst wenn dieser der am häufigsten genutzte ist.

Ein Beispiel der FIFO-Anomalie: Mit drei Seitenrahmen treten neun Seitenfehler auf. Die Erhöhung auf vier Seitenrahmen verursacht zehn Seitenfehler. Seitenfehler sind in rot dargestellt.

{| class="wikitable"
|-----
! 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
|}

{| class="wikitable"
|-----
! 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|Least-recently-used]]-Strategie (LRU) („am längsten ungenutzt“) FIFO vorzuziehen, da LRU-Speicherseiten, die kürzlich benutzt wurden, nicht ersetzt werden. 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“. Hier 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.

== Literatur ==
* {{Literatur|Autor = L. A. Belady, R. A. Nelson, G. S. Shedler |Titel = An Anomaly in Space-time Characteristics of Certain Programs Running in a Paging Machine|Sammelwerk = Commun. ACM|Band = 12|Nummer = 6|Jahr = 1969-06-01|Seiten = 349–353|DOI = 10.1145/363011.363155|ISSN = 0001-0782}}

[[Kategorie:Speicherverwaltung]]
[[Kategorie:Betriebssystemtheorie]]

FIFO-Anomalie - Versionsgeschichte

imported>Müllt-Renner am 14. Mai 2024 um 15:26 Uhr