Anomalia di Belady

Da Wikipedia, l'enciclopedia libera.
Picco dei page fault in presenza di 4 frame disponibili, maggiore di quando sono solo 3

In informatica l'anomalia di Belady è un fenomeno che si presenta in alcuni algoritmi di rimpiazzamento delle pagine di memoria per cui la frequenza dei page fault può aumentare con il numero di frame assegnati ai processi. Ne soffrono gli algoritmi FIFO con alcune combinazioni di richieste di pagina[1].

La scoperta[modifica | modifica wikitesto]

Nel 1969 Belady, Nelson e Shedler individuano successioni di riferimenti che, applicate utilizzando algoritmi di sostituzione FIFO con una certa quantità di memoria disponibile, producono due volte i page fault che con una quantità minore. Ipotizzano anche che due sia un limite generale.

Nel 2010, Fornai e Ivanyi dimostrano che si possono costruire stringhe tali che questo rapporto può essere arbitrariamente grande [2].

Soluzioni[modifica | modifica wikitesto]

Essendo solo gli algoritmi FIFO ad essere affetti da quest'anomalia, è sufficiente utilizzare i cosiddetti algoritmi a stack per gestire la paginazione. La ricerca verso questo genere di soluzioni ha avuto particolare impulso proprio dopo la scoperta di Nelson e Shadler, orientandosi inizialmente verso la definizione dell'algoritmo ottimale (OPT)[3], definito solo in forma teorica data l'impossibilità di prevedere la successione di riferimenti.

Siccome non è possibile implementare OPT su sistemi reali, la ricerca si è concentrata sull'algoritmo LRU (Least Recently Used), che invece sceglie la pagina "vittima" fra quelle utilizzate più indietro nel tempo. Dato il fatto che anche quest'ultimo approccio è eccessivamente dispendioso, si sono individuate approssimazioni come l'algoritmo con seconda chance e l'algoritmo con seconda chance migliorato, entrambi basati sull'utilizzo di bit di validità[4].

Collegamenti esterni[modifica | modifica wikitesto]

Note[modifica | modifica wikitesto]

  1. ^ Abraham Silberschantz, Peter Baer Galvin, Greg Gagne, Sistemi Operativi, concetti ed esempi, settima edizione, Pearson edizioni, febbraio 2006, p.322.
  2. ^ FIFO anomaly is unbounded. URL consultato il 3 settembre 2010.
  3. ^ Abraham Silberschantz, Peter Baer Galvin, Greg Gagne, Sistemi Operativi, concetti ed esempi, settima edizione, Pearson edizioni, febbraio 2006, p.323.
  4. ^ Abraham Silberschantz, Peter Baer Galvin, Greg Gagne, Sistemi Operativi, concetti ed esempi, settima edizione, Pearson edizioni, febbraio 2006, pp.326-329.


informatica Portale Informatica: accedi alle voci di Wikipedia che trattano di informatica