Anomalie Belady
În informatică, anomalia Belady este un fenomen care apare în unele algoritmi de înlocuire a paginii de memorie pentru care frecvența defecțiunilor de pagină poate crește odată cu numărul de cadre alocate proceselor. Algoritmii FIFO suferă de acest lucru cu unele combinații de solicitări de pagină [1] .
Descoperirea
În 1969 Belady, Nelson și Shedler au identificat secvențe de referințe care, atunci când sunt aplicate folosind algoritmi de înlocuire FIFO cu o anumită cantitate de memorie disponibilă, produc defecte de pagină de două ori mai mari decât o cantitate mai mică. De asemenea, ei fac ipoteza că două sunt o limită generală.
În 2010 , Fornai și Ivanyi arată că șirurile pot fi construite astfel încât acest raport să poată fi arbitrar mare [2] .
Soluții
Deoarece numai algoritmii FIFO sunt afectați de această anomalie, este suficient să folosiți așa-numiții algoritmi de stivă pentru a gestiona paginarea. Cercetarea către acest tip de soluții a avut un impuls deosebit chiar după descoperirea lui Nelson și Shadler, orientându-se inițial către definirea algoritmului optim (OPT) [3] , definit doar în formă teoretică dat fiind imposibilitatea de a prezice succesiunea referințe.
Deoarece nu este posibil să se implementeze OPT pe sisteme reale, cercetarea sa concentrat asupra algoritmului LRU ( Cel mai recent folosit ), care alege în schimb pagina „victimei” dintre cele utilizate mai mult înapoi în timp. Având în vedere faptul că chiar și această din urmă abordare este excesiv de costisitoare, au fost identificate aproximări precum algoritmul de a doua șansă și algoritmul de a doua șansă îmbunătățit , ambele bazate pe utilizarea biților de validitate [4] .
Notă
- ^ Silberschatz, 2006 , p. 322 .
- ^ Anomalia FIFO este nelimitată , pe arxiv.org . Accesat la 3 septembrie 2010 .
- ^ Silberschatz, 2006 , p. 323 .
- ^ Silberschatz, 2006 , pp. 326-329 .
Bibliografie
- Abraham Silberschatz, Peter Baer Galvin, Greg Gagne, Sisteme de operare, concepte și exemple , ediția a șaptea, edițiile Pearson, februarie 2006.
