Algoritmo de reemplazo de páginas para niños

En los sistemas operativos que organizan la memoria de una forma especial llamada paginación, los algoritmos de reemplazo de páginas son como reglas que el sistema usa. Estas reglas sirven para decidir qué información antigua se debe quitar de la memoria cuando se necesita espacio para guardar algo nuevo. Imagina que la memoria de tu computadora es una estantería llena de libros (páginas). Si quieres poner un libro nuevo y no hay espacio, necesitas decidir cuál de los libros viejos vas a quitar. Los algoritmos de reemplazo de páginas ayudan a tomar esa decisión.

¿Cómo funcionan los algoritmos de reemplazo de páginas?

Cuando una computadora necesita usar un dato o programa, lo carga en su memoria principal. Esta memoria está dividida en bloques pequeños llamados "marcos de página". Si la memoria está llena y se necesita cargar algo nuevo, el sistema operativo debe elegir qué "página" (bloque de información) sacar para hacer espacio. Los algoritmos de reemplazo son las estrategias que usa para tomar esa decisión.

Algoritmo Óptimo: El ideal imposible

Este algoritmo es el "ideal" o "perfecto". Su objetivo es quitar la página que se usará más tarde en el futuro. Por ejemplo, si la página A se usará dentro de mucho tiempo y la página B se usará pronto, el algoritmo óptimo quitaría la página A.

El problema es que, para hacer esto, el sistema operativo necesitaría saber qué va a pasar en el futuro. Como eso es imposible, este algoritmo no se puede usar en la vida real. Sin embargo, es muy útil para comparar y ver qué tan buenos son los otros algoritmos que sí se pueden implementar.

FIFO: El primero en llegar, el primero en salir

FIFO significa "First In, First Out", que en español es "Primero en entrar, primero en salir". Este método es muy sencillo. El sistema operativo solo lleva un registro del orden en que las páginas fueron cargadas en la memoria.

Cuando necesita espacio, simplemente quita la página que lleva más tiempo en la memoria, es decir, la primera que entró. Es como una fila: el primero que llega es el primero en ser atendido. Aunque es fácil de entender, no siempre funciona bien en la práctica. A veces, quita páginas que se están usando mucho solo porque fueron las primeras en llegar.

Segunda Oportunidad (Reloj): Una mejora para FIFO

Este algoritmo es una versión mejorada del FIFO. Cuando una página debe ser quitada, el sistema no la saca de inmediato. Primero, revisa un "bit de referencia" que tiene esa página. Este bit es como una pequeña marca que indica si la página ha sido usada recientemente.

• Si el bit de referencia está en 1 (significa que fue usada), el sistema lo cambia a 0 y le da una "segunda oportunidad". La página se mueve al final de la lista, como si acabara de llegar.
• Si el bit de referencia está en 0 (significa que no fue usada recientemente), entonces la página se quita de la memoria.

Cada vez que la computadora usa una página, su bit de referencia se pone en 1. Esto ayuda a que las páginas que se usan con frecuencia no sean quitadas tan fácilmente.

CLOCK: El algoritmo del reloj mejorado

El algoritmo CLOCK es una forma más eficiente de implementar la "Segunda Oportunidad". En lugar de mover las páginas al final de una cola, usa una lista circular, como las manecillas de un reloj.

Cuando el sistema necesita quitar una página, avanza por la lista circular. Si encuentra una página con el bit de referencia en 1, lo cambia a 0 y sigue buscando. Si encuentra una página con el bit de referencia en 0, esa es la que quita. Esta forma de trabajar es más rápida porque no necesita mover las páginas en la lista, solo cambiar el bit y avanzar.

NRU: No usado recientemente

NRU significa "Not Recently Used", que es "No usado recientemente". Este algoritmo prefiere mantener en memoria las páginas que se han usado hace poco tiempo. Funciona así:

• Cada página tiene dos "bits": uno de referencia (si fue usada) y otro de modificación (si fue cambiada).
• De vez en cuando, el sistema operativo pone en 0 todos los bits de referencia. Así, las páginas que tienen su bit en 1 son las que se usaron en el último período de tiempo.
• Cuando necesita quitar una página, las clasifica en cuatro grupos:
  • Categoría 0: No usada, no modificada.
  • Categoría 1: No usada, modificada.
  • Categoría 2: Usada, no modificada.
  • Categoría 3: Usada, modificada.

El algoritmo NRU siempre busca quitar una página de la categoría más baja que no esté vacía. Las páginas de la Categoría 0 son las mejores para quitar, porque no se han usado ni cambiado. Las de la Categoría 3 son las peores para quitar, porque se están usando y además tienen cambios importantes.

LRU: El menos usado recientemente

LRU significa "Least Recently Used", que es "Menos usado recientemente". Este algoritmo intenta ser muy eficiente. Su idea es que las páginas que no se han usado en mucho tiempo son las que menos probabilidades tienen de ser usadas de nuevo pronto. Por lo tanto, son las mejores candidatas para ser quitadas.

Aunque suena muy bien en teoría, implementar LRU puede ser complicado y consumir muchos recursos de la computadora. Una forma de hacerlo sería llevar una lista de todas las páginas en memoria, ordenadas por la última vez que se usaron. Pero cada vez que se usa una página, habría que moverla en la lista, lo cual es lento. Otra forma sería poner una marca de tiempo en cada página cuando se usa, y luego buscar la que tenga la marca de tiempo más antigua.

Debido a su costo, a menudo se usan algoritmos que son similares a LRU pero más fáciles de implementar.

Envejecimiento (Aging): Una buena aproximación

El algoritmo de Envejecimiento es una mejora del NRU. No solo se fija si una página fue usada recientemente, sino también "cuánto" fue usada y "cuándo" fue usada.

Cada página tiene un contador. Cada cierto tiempo, el sistema hace dos cosas con este contador:

• Primero, lo divide por 2 (desplaza sus bits a la derecha).
• Luego, si la página fue usada en ese momento, le suma 1.

De esta manera, las páginas que se usan con más frecuencia o más recientemente tendrán un número más alto en su contador. Cuando se necesita quitar una página, se elige la que tenga el número más pequeño en su contador, porque eso significa que ha sido la menos usada o la más antigua en ser usada. Este algoritmo es una muy buena aproximación al algoritmo óptimo.

Véase también

En inglés: Page replacement algorithm Facts for Kids

• Algoritmos de caché