Existe varios algortimos que se gestionan en la memorial virtual entre ellos esta, el algoritmo de reemplazo
de páginas. La característica que se busca en este algoritmo es que, para una
patrón de accesos dado, permita obtener el menor número de fallos de página.se usa una cadena de referencia esto es, una lista de referencias a memoria. Estas cadenas
modelan el comportamiento de un conjunto de procesos en el sistema, y, obviamente, diferentes comportamientos llevarán a resultados distintos.
Para analizar a un algoritmo de reemplazo, si se busca la cantidad de fallos
de página producidos, además de la cadena de referencia, es necesario conocer la cantidad de páginas y marcos del sistema que se está modelando
ademas, existen otros algoritmo como:
Primero en entrar, primero en salir (FIFO). al cargar una página en memoria, se toma nota de en qué momento fue
cargada, y cuando sea necesario reemplazar una página, se elige la que haya
sido cargada hace más tiempo.
La principal ventaja de este algoritmo es, como ya se ha mencionado, la
simplicidad, tanto para programarlo como para comprenderlo. Su implementación puede ser tan simple como una lista ligada circular, cada elemento que
va recibiendo se agrega en el último elemento de la lista, y se “empuja” el
apuntador para convertirlo en la cabeza.
Reemplazo de páginas óptimo (OPT, MIN)
Si bien este algoritmo está demostrado como óptimo o mínimo, se mantiene
como curiosidad teórica porque requiere conocimiento a priori de las necesidades a futuro del sistema y si esto es impracticable ya en los algoritmos de
despachadores, lo será mucho más con un recurso de reemplazo tan dinámico
como la memoria.
Su principal utilidad reside en que ofrece una cota mínima: calculando el
número de fallos que se presentan al seguir OPT, es posible ver qué tan cercano
resulta otro algoritmo respecto al caso óptimo. Para esta cadena de referencia,
y con tres páginas, se tiene un total de nueve fallos.
Menos recientemente utilizado (LRU)
Este busca acercarse a OPT prediciendo cuándo será la
próxima vez en que se emplee cada una de las páginas que tiene en memoria
basado en la historia reciente de su ejecución. Cuando necesita elegir una página víctima, LRU elige la página que no ha
sido empleada hace más tiempo.
Cuando necesita elegir una página víctima, LRU elige la página que no ha
sido empleada hace más tiempo. sensiblemente más complejo que FIFO. Una implementación
podría ser agregar un contador a cada uno de los marcos, actualizarlo siempre
al hacer una referenciar a dicha página, y elegir como víctima a la página con
un menor conteo.
la desventaja que tiene este algoritmo es en presencia de
una gran cantidad de páginas, tiene que recorrerlas todas para buscar la más
envejecida.
Más frecuentemente utilizada (MFU)/Menos frecuentemente utilizada (LFU)
Estos dos algoritmos se basan en mantener un contador, tal como lo hace
LRU, pero en vez de medir el tiempo, miden la cantidad de referencias que se
han hecho a cada página.
El MFU parte de la lógica que, si una página fue empleada muchas veces,
probablemente vuelva a ser empleada muchas veces más; LFU parte de que una
página que ha sido empleada pocas veces es probablemente una página recién
cargada, y va a ser empleada en el futuro cercano.
Estos dos algoritmos son tan caros de implementar como LRU, y su rendimiento respecto a OPT no es tan cercana, por lo cual casi no son empleados.
Segunda oportunidad (o reloj)
El algoritmo de la segunda oportunidad trabaja también basado en un bit de referencia y un recorrido tipo FIFO. La
diferencia en este caso es que, al igual que hay eventos que encienden a
este bit (efectuar una referencia al marco), hay otros que lo apagan
porque puede implementarse
como una lista ligada circular, y el apuntador puede ser visto como una
manecilla. La manecilla avanza sobre la lista de marcos buscando uno
con el bit de referencia apagado, y apagando a todos a su paso.
No hay comentarios:
Publicar un comentario