Béládys anomali
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Ett exempel på Béládys anomali. Med tre sidramar uppstår nio sidfel. Att öka till fyra sidramar gör att tio sidfel uppstår. Sidfel är i rött . Detta kan ses som ett resultat av ett "Penny Wise, Pound Foolish" beteende. | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
![{\displaystyle {\ce {->[{} \atop {\text{Time}}]}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/5bbe595e28fc03e4a78bd8a926bc0e17cb542c5f)
Inom datorlagring är Béládys anomali fenomenet där ett ökat antal sidbilder resulterar i en ökning av antalet sidfel för vissa minnesåtkomstmönster. Det här fenomenet är vanligt förekommande när man använder algoritmen för ersättning av sidan först in först ut ( FIFO ) . I FIFO kan eller kanske inte sidfelet ökar när sidramarna ökar, men i optimala och stackbaserade algoritmer som LRU , när sidramarna ökar, minskar sidfelet. László Bélády demonstrerade detta 1969.
Bakgrund
I vanlig datorminneshantering laddas information i bitar av viss storlek. Varje bit kallas en sida . Huvudminnet kan endast innehålla ett begränsat antal sidor åt gången. Det kräver en ram för varje sida den kan ladda. Ett sidfel uppstår när en sida inte hittas och kan behöva laddas från disken till minnet.
När ett sidfel uppstår och alla ramar är i bruk måste man rensas för att göra plats för den nya sidan. En enkel algoritm är FIFO: den sida som har varit längst i ramarna är den som rensas. Tills Béládys anomali påvisades trodde man att en ökning av antalet sidramar alltid skulle resultera i samma antal eller färre sidfel.
Béládys anomali är obegränsad
Bélády, Nelson och Shedler konstruerade referenssträngar för vilka FIFO-sidersättningsalgoritmen producerade nästan dubbelt så många sidfel i ett större minne än i ett mindre och de formulerade gissningen att 2 är en generell gräns.
2010 visade Fornai och Iványi att avvikelsen faktiskt är obegränsad och att man kan konstruera en referenssträng till vilket godtyckligt sidfelsförhållande som helst.
externa länkar
- Béládys papper från 1969: En anomali i rum-tidsegenskaper hos vissa program som körs i en personsökarmaskin
- FIFO-anomali är obegränsad. arXiv : 1003.1336
- Lösningar för tävling för Internetproblemlösning – Problem L – Bibliotekarie