1111

Algoritmos de reemplazo de páginas
De Wikipedia, la enciclopedia libre
Saltar a navegación, búsqueda
En sistemas operativos que utilizan paginación para el manejo de memoria, los algoritmos de reemplazo de páginas son usados para decidir qué páginas pueden ser sacadas de memoria cuando se necesita cargar una nueva y ya no hay espacio.
|
[editar] Óptimo
Este algoritmo tiene como finalidadretirar la página que vaya a ser referenciada más tarde, por ejemplo si hay una página A que será usada dentro de 10000 instrucciones, y una página B que será usada dentro de 2800 instrucciones, se debería eliminar de la memoria la página A. Como se puede deducir, para esto el sistema operativo debería ver en cuánto tiempo será usada cada página en memoria y elegir la que está más distante. Elproblema de este método es que necesita conocimiento del futuro, por lo que es imposible su implementación. Es un algoritmo teórico. Se utiliza a los efectos comparativos con los algoritmos factibles de ser implementados para ver cuál se aproxima más a éste.
[editar] Primera en entrar, primera en salir (FIFO, First In, First Out)
En este método el sistema operativo sólo tiene que guardar en quéorden las páginas fueron cargadas, de modo que al necesitar hacer espacio pueda fácilmente elegir la primera página cargada. Se usa una cola, al cargar una página nueva se ingresa en el último lugar. Aunque las colas FIFO son simples e intuitivas, no se comportan de manera aceptable en la aplicación práctica, por lo que es raro su uso en su forma simple. Uno de los problemas que presentan es lallamada Anomalía FIFO o Anomalía de Belady. Belady encontró ejemplos en los que un sistema con un número de marcos de páginas igual a tres tenía menos fallos de páginas que un sistema con cuatro marcos de páginas. El problema consiste en que podemos quitar de memoria una página de memoria muy usada, sólo porque es la más antigua.
[editar] Segunda oportunidad
Es una pequeña modificación al algoritmoFIFO, que funciona bastante mejor que aquel. En este caso cuando una página debe ser sacada se toma la primera en la cola, y en vez de sacarla, consulta el valor de un bit de referencia. En caso de estar fijado (en 1) se cambia el bit a 0 y se lo coloca al final de la cola, actualizando su tiempo de carga como si recién hubiera llegado a la memoria. De esta forma, se le da una segunda oportunidad.Si el bit se encuentra sin fijar(en 0), la página se saca de memoria. Cada vez que la MMU accede a una página, fija su bit de referencia a 1. Para esto es necesario soporte para bit de referencia por hardware.
[editar] Reloj
Existe una variante de este algoritmo que sobre la misma idea presenta una mejora en la implementación. Es el algoritmo del reloj, que lo que hace es tener una listacircular, de forma que al llegar al último elemento de la lista, pasa automáticamente al primero. Los elementos no se mueven al final de la cola cuando son accedidos, simplemente se pone su bit de referencia a 1. Esto nos evita tener que hacer movimientos de punteros en el caso de implementarlo con una lista enlazada. De hecho, se puede implementar con un array perfectamente, ahorrando así memoria.[editar] No usada recientemente (Not Recently Used, NRU)
Este algoritmo favorece a las páginas que fueron usadas recientemente. Funciona de la siguiente manera: cuando una página es referenciada, fija el bit de referencia para esa página. Similarmente, cuando una página es modificada, fija su bit de modificación. Usualmente estas operaciones son realizadas por el hardware, aunque puede hacersetambién por software. En un tiempo fijo, el sistema operativo pone en 0 los bits de referencia de todas las páginas, de modo que las páginas con su bit de referencia en 1 son las que fueron referenciadas dentro del último intervalo de reloj. Cuando una página debe ser reemplazada, el sistema operativo divide las páginas en cuatro categorías:
* Categoría 0: no referenciada, no modificada
*...