Anomalia de Belady
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Un exemple de l'anomalia de Belady. Usant tres marcs de pàgina, es produeixen 9 errors de pàgina. Incrementant a quatre marcs de pàgina, produeix 10 errors de pàgina. Els errors de pàgina es mostren en vermell. |
En emmagatzematge informàtic, l'anomalia de Bélády demostra que és possible que es produeixin més errors de pàgina quan s'incrementen el nombre de marcs de pàgina i es fa servir l'algorisme de reemplaçament FIFO. László Bélády ho va demostrar el 1969.
En els sistemes d'emmagatzematge informàtic habituals, la informació es carrega en trossos de mida fixa. Cada tros s'anomena pàgina. El processador només pot carregar un nombre de pàgines determinat alhora. Requereix un marc per a cada pàgina que pot carregar. Un error de pàgina es produeix quan la pàgina no es troba, i pot haver de ser carregada del disc a la memòria.
Quan es produeix un error de pàgina i tots els marcs són plens, se n'ha d'alliberar un per a fer espai per a la nova pàgina. Un algorisme senzill per a fer-ho és el FIFO: la pàgina que porti més temps al seu marc és la que ha de ser eliminada. Fins que l'anomalia de Bélády va ser demostrada, l'algorisme FIFO era assumit com a acceptable