Anomalia di Belady

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].

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. Ipotizzando 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].

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].

• Abraham Silberschatz, Peter Baer Galvin, Greg Gagne, Sistemi Operativi, concetti ed esempi, settima edizione, Pearson edizioni, febbraio 2006.

• Pubblicazione del 1969 di Belady: An anomaly in space-time characteristics of certain programs running in a paging machine

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