Hola, tenemos una duda teorica sobre si los algoritmos Second chance y NRU sobre de la anomalia de Belady.
Gracias
Saludos.
En respuesta a Nahir Marisol Toledo Olivera
Re: Consulta teorica sobre anomalia de Belady
de Manuel Freire -
Hola,
No entendí muy bién qué estás preguntando pero supongo que va por el lado de si hay o no anomalia de Belady en Second chance y NRU. La respuesta corta es si pero menos que en FIFO.
Un subconjunto de los algoritmos de reemplazo son los algoritmos basados en stack entre los que está el LRU y algún otro no visto en el curso. Ese tipo de algoritmos cumplen una propiedad que en un instante dado las páginas que tenés cargadas si tenés N frames son un subconjunto de las páginas que tendrías cargadas si tuvieras N+1 frames. Todos los que cumplen esta propiedad se puede probar que nunca van a sufrir la anomalía de belady.
Los que si la sufren son algoritmos basados en fifo o en aleatoriedad (los segundos podrían comportarse exactamente como FIFO por azar) sin embargo no todos las sufren con las mismas entradas, en especial el second chance no sufre en muchas que FIFO si.
Sin embargo por más que existan algoritmos que no sufran anomalía de belady en la práctica la facilidad de implementación de los otros genera que se usen algoritmos que si la sufren. La razón es que a veces preferible pagar el precio de la anomalía (que no se da necesariamente, simplemente puede darse y en estos en cuestión son casos bastante rebuscados) que los recursos necesarios para implementar LRU.
Espero que haya servido.
Saludos!
En respuesta a Manuel Freire
Re: Consulta teorica sobre anomalia de Belady
Buenas noches, en el teórico de anomalía de Belady para FIFO, con la secuencia dada(1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5), me da que para 3 frames hay 10 fallos de página y para 4 frames hay 8 fallos de págna.
¿esto es correcto?
Desde ya muchas gracias por la respuesta.
Saludos.
En respuesta a Mathias Ignacio Nieres Moreira
Re: Consulta teorica sobre anomalia de Belady
de Alexis Alfonso -
No, fijate bien. Marco con F los fallos y los números son las páginas que si están cargadas.
Para 3 frames, la secuencia seria
FFFFFFF12FF5 = 9 fallos
y para 4 frames:
FFFF12FFFFFF = 10 fallos
En respuesta a Alexis Alfonso
Re: Consulta teorica sobre anomalia de Belady
Pah, a mi me queda así para 3 frames:
1-fallo
Fifo=1
Frames=[1,-,-]
2-fallo
Fifo=2,1
Frames=[1,2,-]
3-fallo
Fifo=3,2,1
Frames=[1,2,3]
4-fallo
Fifo=4,3,2
Frames=[4,2,3]
1-fallo
Fifo=1,4,3
Frames=[4,1,3]
2-fallo
Fifo=2,1,4
Frames=[4,1,2]
5=fallo
Fifo=5,2,1
Frames=[5,1,2]
1
Fifo=1,5,2
2-
Fifo=2,1,5
3-fallo
Fifo=3,2,1
Frames=[3,1,2]
4-fallo
Fifo=4,3,2
Frames=[3,4,2]
5-fallo
Fifo=5,4,3
Frames=[3,4,5]
¿Que parte estaría mal?
En respuesta a Mathias Ignacio Nieres Moreira
Re: Consulta teorica sobre anomalia de Belady
de Alexis Alfonso -
El problema es que cuando no ocurre un page fault estás cambiando el orden de la Fifo, cuando no deberías hacer nada.
Por ejemplo, en los accesos ..5,1.. haces
5=fallo
Fifo=5,2,1
Frames=[5,1,2]
1
Fifo=1,5,2
Y no se por qué la Fifo la cambias a 1,5,2.
En respuesta a Alexis Alfonso
Re: Consulta teorica sobre anomalia de Belady
Ta, mal yo. Lo usé como si fuera LRU.
Muchas gracias por hacerme notar eso.
Saludos!