Algoritmo FIFO
El algoritmo FIFO reemplaza las páginas de la forma que el primero que entra es el primero que sale. Asocia a cada página el instante en el que se trajo a la memoria, así cuando se tenga que reemplazar una página, se elige la más antigua.
En la imagen vemos 19 páginas entrando en una memoria de tres frames. El resultado obtenido fueron 15 fallos de página.
A pesar de que es un algoritmo fácil de comprender y programar, su rendimiento no siempre es bueno. Un ejemplo claro es cuando la página puede contener una variable cuyo valor inicial se asignó hace tiempo pero que se utiliza constantemente por lo que puede prescindir de páginas que accede con frecuencia.
Algoritmo FIFO
1. FIFO
Se sustituye la página residente que lleve más tiempo en
memoria
Fácil de implementar (cola FIFO de páginas)
Problema: al no tener en cuenta la historia del uso de una
página dada, FIFO puede prescindir de páginas a las que se
accede con frecuencia
Padece la anomalía de
Belady
(fenómeno paradójico
consistente en que aumenta el número de fallos de páginas
cuando se asignan más páginas reales al proceso)
Propiedad de pila
: para cualquier punto en la cadena de
referencia, el conjunto de páginas en N marcos de página es
un subconjunto del que se formaría en N+1 marcos de página
Algoritmo Óptimo
El Algoritmo Óptimo, también conocido como OPT se originó luego del descubrimiento de la Anomalía de Belady en la búsqueda de un algoritmo mucho más óptimo. El algoritmo elige la página de la memoria que vaya a ser referenciada más tarde, las páginas se rotulan con el número de instrucciones que se ejecutarán antes de que se haga la primera referencia a ella y, cuando se presenta un fallo de página, se reemplaza la que más instrucciones falten para referenciarla para así ir aplazando lo más que se pueda los fallos de página. Por desgracia, este algoritmo es irrealizable, ya que no hay una forma de predecir qué páginas referenciará un proceso en el futuro.
Como es un algoritmo que no se puede poner en práctica, se ejecuta en simuladores en los cuales se demuestra que es un muy buen algoritmo que reduce mucho las fallas y que se encuentra entre los algoritmos con mejor eficiencia por lo que es el algoritmo utilizado para estudios comparativos.
Algunos algoritmos de
reemplazo
Básicos
FIFO
OPTIMO
LRU – least recently used
Aproximaciones LRU
LRU con bits de referencia adicionales
LRU de segunda oportunidad o del reloj
LRU de segunda oportunidad mejorado
De conteo
LFU – less frequently used
MFU – most frequently used
25
Algoritmo FIFO
1. FIFO
Se sustituye la página residente que lleve más tiempo en
memoria
Fácil de implementar (cola FIFO de páginas)
Problema: al no tener en cuenta la historia del uso de una
página dada, FIFO puede prescindir de páginas a las que se
accede con frecuencia
Padece la anomalía de
Belady
(fenómeno paradójico
consistente en que aumenta el número de fallos de páginas
cuando se asignan más páginas reales al proceso)
Propiedad de pila
: para cualquier punto en la cadena de
referencia, el conjunto de páginas en N marcos de página es
un subconjunto del que se formaría en N+1 marcos de página
ejercicios de FIFo
https://www.youtube.com/watch?
ejercicios de FIFo
https://www.youtube.com/watch?
Algoritmo de reemplazo óptimo
2. Óptimo
Escoger como víctima la página que más tarde en
volver a ser accedida
Es el algoritmo que presenta la frecuencia de
fallos de página más baja de todos
No implementable (requiere presciencia)
Útil como referencia de comparación
No hay comentarios.:
Publicar un comentario