¿Alguna vez te has preguntado cómo los sistemas operativos deciden qué información mantener en la memoria y cuál reemplazar? Los algoritmos de sustitución de página son una pieza fundamental en esta toma de decisiones.
En este post, te desvelaré los misterios detrás de estos algoritmos y te mostraré cómo funcionan en la práctica. Desde lo básico, como FIFO y LRU, hasta las sofisticadas técnicas de segunda oportunidad y envejecimiento, exploraremos cada uno de ellos con ejemplos claros y detallados.
Hablemos acerca de los algoritmos de sustitución de página. El contenido de este tema está basado en el SISTEMAS OPERATIVOS : Stallings, William y las clases del Maestro José Luis Elvira. También quiero compartirle mis conocimientos y apuntes de la universidad, gracias a las enseñanzas de la Profesora Mirella.
¿Qué es un algoritmo de sustitución de página?
Los algoritmos de sustitución de página son técnicas que se enfocan en minimizar el número de fallos de página.
Toma en cuenta que un fallo de página ocurre cuando un programa necesita una página que no está en le memoria principal (RAM) y sistema operativo debe cargarla desde el disco.
Existen varios algoritmos de sustitución de página:
- Algoritmo Óptimo
- Algoritmo FIFO (First-In, First-Out)
- Algoritmo LRU (Least Recently Used)
- Segunda Oportunidad
- Reloj (CLOCK)
- NRU
- Working Set
- WS Clock
- Envejecimiento
Vamos a ver a profundidad de qué trata cada uno y su funcionamiento mediante ejemplos. Y para aclarar:
- En la mayoría de los ejemplos se utilizarán 4 marcos de memoria (espacios disponibles)
- Una secuencia de referencia a páginas (datos que los programas necesitan para cargar en memoria)
- El fallo será denominado como F.
Algoritmo Óptimo
El algoritmo óptimo se enfoca en reemplazar la página que se usará en un futuro lejano.
Este algoritmo en la teoría funciona, pero en la práctica no. Porque es imposible saber con certeza qué páginas se usarán en el futuro.
Ejemplo con 4 Marcos de Memoria
Vamos a usar la siguiente secuencia (2, 3, 2, 1, 5, 2, 4, 5, 3, 2, 5, 2) y con un marco de memoria de 4.
Los pasos a seguir son:
- La memoria está vacía al inicio.
- Cuando llega una nueva página, se carga un marco libre.
- Si no hay marcos libres, el algoritmo óptimo reemplaza la página que se usará en el futuro más lejano.
Diagrama
| Referencia | Marco 1 | Marco 2 | Marco 3 | Fallo de Página (F) | Explicación |
| 2 | 2 | F | Marco 1: 2 (nuevo) | ||
| 3 | 2 | 3 | F | Marco 2: 3 (nuevo) | |
| 2 | 2 | 3 | La página 2 ya está en memoria. | ||
| 1 | 2 | 3 | 1 | F | Marco 3: 1 (nuevo) |
| 5 | 2 | 3 | 5 | F | Reemplazo: La página 1 no se usará pronto, pero la 2 y 3 sí. Se reemplaza 1. |
| 2 | 2 | 3 | 5 | La página 2 ya está en memoria. | |
| 4 | 2 | 3 | 4 | F | Reemplazo: La página 5 no se usará pronto, pero la 2 y 3 sí. Se reemplaza 5. |
| 5 | 2 | 3 | 5 | F | Reemplazo: La página 4 no se usará pronto, pero la 2 y 3 sí. Se reemplaza 4. |
| 3 | 2 | 3 | 5 | La página 3 ya está en memoria. | |
| 2 | 2 | 3 | 5 | La página 2 ya está en memoria. | |
| 5 | 2 | 3 | 5 | La página 5 ya está en memoria. | |
| 2 | 2 | 3 | 5 | La página 2 ya está en memoria. |
Lo que nos da un total de 6 fallos de página.
Explicación del diagrama
- Primera referencias (2,3,2,1):
- Las páginas 2, 3 y 1 se cargan en los marcos disponibles.
- Cuando llega la página 5, no hay marcos libros. El algoritmo óptimo decide reemplazar la página 1 porque no se usara pronto.
- Referencia posteriores (2, 4, 5, 3, 2, 5, 2):
- Cada vez que no hay marco libres, el algoritmo elige la página que se usará en el futuro lejano.
- Un ejemplo: cuando llega a la página 4, se reemplaza la página 5 porque no se usará pronto.
Algoritmo FIFO
Quiero invitarte a cumplir este reto: Realiza este mismo ejercicio, pero con 4 Marcos de Memoria
El algoritmo FIFO (First In, First Out) usa a los marco de página como si fuera un buffer circular. Las páginas son expulsadas de la memoria y son traídas de nuevo de forma repetida. Algo similar a lo que es Round Robin.
La ventaja de este algoritmo su fácil implementación. Pero tiene un débil rendimiento.
Ejemplo con 4 Marcos de Memoria
Utilizando 4 marcos de memoria y la siguiente secuencia: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5.
Los pasos son los siguientes:
- La memoria está vacía al principio.
- Cuando llega una nueva página, se carga en un marco libre.
- Si no hay marco libres, se reemplaza la página que lleva más tiempo en memoria (La primera que entró).
Diagrama
| Referencia | Marco 1 | Marco 2 | Marco 3 | Marco 4 | Fallo de Página (F) |
|---|---|---|---|---|---|
| 1 | 1 | – | – | – | F |
| 2 | 1 | 2 | – | – | F |
| 3 | 1 | 2 | 3 | – | F |
| 4 | 1 | 2 | 3 | 4 | F |
| 1 | 1 | 2 | 3 | 4 | – |
| 2 | 1 | 2 | 3 | 4 | – |
| 5 | 5 | 2 | 3 | 4 | F (Reemplaza 1) |
| 1 | 5 | 1 | 3 | 4 | F (Reemplaza 2) |
| 2 | 5 | 1 | 2 | 4 | F (Reemplaza 3) |
| 3 | 5 | 1 | 2 | 3 | F (Reemplaza 4) |
| 4 | 4 | 1 | 2 | 3 | F (Reemplaza 5) |
| 5 | 4 | 5 | 2 | 3 | F (Reemplaza 1) |
Para este caso tenemos 10 fallos de página.
Explicación del diagrama
- Cada vez que una página no está en memoria, ocurre un fallo de página (F). Por lo que el sistema operativo deberá cargarla.
- Cuando la memoria está llena, el algoritmo FIFO reemplaza la página que lleva más tiempo en memoria (la primera que entró).
Algoritmo LRU
El algoritmo LRU (Least Recently Used) se encarga de reemplazar la página que no se ha utilizado durante más tiempo. Una de las ventajas de este algoritmo son los resultados que produce porque son muy cercanos en la práctica.
Sin embargo, tiene dos problemas:
- El sistema operativo debe mantener un registro de cada acceso a la memoria para saber cuándo fue la última vez que se usó una página (Es costoso a nivel de recursos).
- Mantener una pila o una lista de páginas ordenadas por su último uso puede llegar a ser complicado y te consume mucha memoria.
Ejemplo: Algoritmo LRU con 4 Marcos de Memoria
Vamos a usar un ejemplo con una secuencia de referencias a páginas y 4 marcos de memoria.
La secuencia de referencias: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5
Pasos a seguir:
- La memoria está vacía al principio.
- Cuando llega una nueva página, se carga en un marco libre.
- Si no hay marcos libres, el algoritmo LRU reemplaza la página que no se ha usado durante más tiempo.
Diagrama
| Referencia | Marco 1 | Marco 2 | Marco 3 | Marco 4 | Fallo de Página (F) | Explicación |
|---|---|---|---|---|---|---|
| 1 | 1 | – | – | – | F | Marco 1: 1 (nuevo) |
| 2 | 1 | 2 | – | – | F | Marco 2: 2 (nuevo) |
| 3 | 1 | 2 | 3 | – | F | Marco 3: 3 (nuevo) |
| 4 | 1 | 2 | 3 | 4 | F | Marco 4: 4 (nuevo) |
| 1 | 1 | 2 | 3 | 4 | – | La página 1 ya está en memoria. |
| 2 | 1 | 2 | 3 | 4 | – | La página 2 ya está en memoria. |
| 5 | 1 | 2 | 3 | 5 | F | Reemplazo: La página 4 es la menos recientemente usada. Se reemplaza 4. |
| 1 | 1 | 2 | 3 | 5 | – | La página 1 ya está en memoria. |
| 2 | 1 | 2 | 3 | 5 | – | La página 2 ya está en memoria. |
| 3 | 1 | 2 | 3 | 5 | – | La página 3 ya está en memoria. |
| 4 | 4 | 2 | 3 | 5 | F | Reemplazo: La página 1 es la menos recientemente usada. Se reemplaza 1. |
| 5 | 4 | 2 | 3 | 5 | – | La página 5 ya está en memoria. |
En resumen, el total de fallos de página: 6
Explicación del Diagrama
- Primeras referencias (1, 2, 3, 4):
- Las páginas 1, 2, 3 y 4 se cargan en los marcos disponibles.
- Cuando llega la página 5, no hay marcos libres. El algoritmo LRU decide reemplazar la página 4 porque es la menos recientemente usada.
- Referencias posteriores (1, 2, 3, 4, 5):
- Cada vez que no hay marcos libres, el algoritmo elige la página que no se ha usado durante más tiempo.
- Por ejemplo, cuando llega la página 4, se reemplaza la página 1 porque es la menos recientemente usada.
Algoritmo de Segunda Oportunidad
El algoritmo de segunda oportunidad es una variante del FIFO que agrega un bit de referencia a cada página. Este bit ayuda a identificar si una página ha sido usada recientemente, lo que permite evitar reemplazar páginas que aún son útiles.
Debes tomar en cuenta estos factores para entender su funcionamiento:
- Bit de referencia:
- Cada página tiene un bit de referencia (0 o 1).
- Cuando una página se carga en memoria o se referencia, su bit de referencia se establece en 1.
- Reemplazo de páginas:
- Cuando hay que reemplazar una página, el algoritmo revisa la página más antigua (como en FIFO).
- Si el bit de referencia de esa página es 0, se reemplaza.
- Si el bit de referencia es 1, se le da una segunda oportunidad: el bit se restablece a 0, y la página se mueve al final de la cola (como si fuera una página nueva).
- Ventaja:
- Evita reemplazar páginas que se están usando activamente, ya que su bit de referencia será 1.
- Es más eficiente que FIFO, pero no tiene en cuenta la frecuencia de uso de las páginas (a diferencia de LRU).
Ejemplo con 4 Marcos de Memoria
Vamos a usar un ejemplo con una secuencia de referencias a páginas y 4 marcos de memoria.
Secuencia de referencias: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5
Pasos a seguir:
- La memoria está vacía al principio.
- Cuando llega una nueva página, se carga en un marco libre y su bit de referencia se establece en 1.
- Si no hay marcos libres, el algoritmo revisa la página más antigua:
- Si su bit de referencia es 0, se reemplaza.
- Si su bit de referencia es 1, se le da una segunda oportunidad: el bit se restablece a 0 y la página se mueve al final de la cola.
Diagrama
| Referencia | Marco 1 | Marco 2 | Marco 3 | Marco 4 | Bit de Referencia | Fallo de Página (F) | Explicación |
|---|---|---|---|---|---|---|---|
| 1 | 1 (1) | – | – | – | 1 | F | Marco 1: 1 (nuevo), bit = 1 |
| 2 | 1 (1) | 2 (1) | – | – | 1 | F | Marco 2: 2 (nuevo), bit = 1 |
| 3 | 1 (1) | 2 (1) | 3 (1) | – | 1 | F | Marco 3: 3 (nuevo), bit = 1 |
| 4 | 1 (1) | 2 (1) | 3 (1) | 4 (1) | 1 | F | Marco 4: 4 (nuevo), bit = 1 |
| 1 | 1 (1) | 2 (1) | 3 (1) | 4 (1) | 1 | – | La página 1 ya está en memoria, bit = 1 |
| 2 | 1 (1) | 2 (1) | 3 (1) | 4 (1) | 1 | – | La página 2 ya está en memoria, bit = 1 |
| 5 | 5 (1) | 2 (0) | 3 (0) | 4 (0) | 1 | F | Reemplazo: La página 1 tiene bit = 1, se le da segunda oportunidad. |
| Se reemplaza la siguiente página más antigua con bit = 0 (página 2). | |||||||
| 1 | 5 (1) | 1 (1) | 3 (0) | 4 (0) | 1 | F | Reemplazo: La página 3 tiene bit = 0, se reemplaza. |
| 2 | 5 (1) | 1 (1) | 2 (1) | 4 (0) | 1 | F | Reemplazo: La página 4 tiene bit = 0, se reemplaza. |
| 3 | 5 (1) | 1 (1) | 2 (1) | 3 (1) | 1 | F | Reemplazo: La página 5 tiene bit = 1, se le da segunda oportunidad. |
| Se reemplaza la siguiente página más antigua con bit = 0 (página 1). | |||||||
| 4 | 4 (1) | 1 (0) | 2 (1) | 3 (1) | 1 | F | Reemplazo: La página 1 tiene bit = 0, se reemplaza. |
| 5 | 4 (1) | 5 (1) | 2 (1) | 3 (1) | 1 | F | Reemplazo: La página 2 tiene bit = 1, se le da segunda oportunidad. |
| Se reemplaza la siguiente página más antigua con bit = 0 (página 3). |
En resumen, el total de fallos de página es 10
Explicación del Diagrama
- Primeras referencias (1, 2, 3, 4):
- Las páginas 1, 2, 3 y 4 se cargan en los marcos disponibles, y sus bits de referencia se establecen en 1.
- Referencias posteriores (1, 2, 5, 1, 2, 3, 4, 5):
- Cuando no hay marcos libres, el algoritmo revisa la página más antigua.
- Si su bit de referencia es 1, se le da una segunda oportunidad: el bit se restablece a 0 y la página se mueve al final de la cola.
- Si su bit de referencia es 0, se reemplaza.
Algoritmo de Reloj (CLOCK)
El algoritmo CLOCK utiliza una lista circular de páginas en memoria y un puntero que apunta a la página más antigua. Cada página tiene un bit de referencia que indica si ha sido usada recientemente (1) o no (0).
Entiende su funcionamiento:
- Bit de referencia:
- Cada página tiene un bit de referencia (0 o 1).
- Cuando una página se carga en memoria o se referencia, su bit de referencia se establece en 1.
- Puntero:
- Un puntero apunta a la página más antigua en la lista circular.
- Cuando hay que reemplazar una página, el algoritmo comienza a buscar desde la posición del puntero.
- Reemplazo de páginas:
- Si el bit de referencia de la página actual es 0, se reemplaza.
- Si el bit de referencia es 1, se le da una segunda oportunidad: el bit se restablece a 0, y el puntero avanza a la siguiente página.
- Si todas las páginas tienen su bit en 1, el algoritmo las pone a 0 y comienza una nueva pasada.
Ejemplo con 4 Marcos de Memoria
Vamos a usar un ejemplo con una secuencia de referencias a páginas y 4 marcos de memoria.
Secuencia de Referencias: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5
Pasos a seguir:
- La memoria está vacía al principio.
- Cuando llega una nueva página, se carga en un marco libre y su bit de referencia se establece en 1.
- Si no hay marcos libres, el algoritmo CLOCK busca una página para reemplazar, comenzando desde la posición del puntero.
Diagrama
| Referencia | Marco 1 | Marco 2 | Marco 3 | Marco 4 | Bit de Referencia | Puntero | Fallo de Página (F) | Explicación |
|---|---|---|---|---|---|---|---|---|
| 1 | 1 (1) | – | – | – | 1 | 1 | F | Marco 1: 1 (nuevo), bit = 1 |
| 2 | 1 (1) | 2 (1) | – | – | 1 | 1 | F | Marco 2: 2 (nuevo), bit = 1 |
| 3 | 1 (1) | 2 (1) | 3 (1) | – | 1 | 1 | F | Marco 3: 3 (nuevo), bit = 1 |
| 4 | 1 (1) | 2 (1) | 3 (1) | 4 (1) | 1 | 1 | F | Marco 4: 4 (nuevo), bit = 1 |
| 1 | 1 (1) | 2 (1) | 3 (1) | 4 (1) | 1 | 1 | – | La página 1 ya está en memoria, bit = 1 |
| 2 | 1 (1) | 2 (1) | 3 (1) | 4 (1) | 1 | 1 | – | La página 2 ya está en memoria, bit = 1 |
| 5 | 5 (1) | 2 (0) | 3 (0) | 4 (0) | 1 | 2 | F | Reemplazo: Puntero en Marco 1 (bit = 1). Se pone a 0 y avanza. |
| Puntero en Marco 2 (bit = 1). Se pone a 0 y avanza. | ||||||||
| Puntero en Marco 3 (bit = 1). Se pone a 0 y avanza. | ||||||||
| Puntero en Marco 4 (bit = 1). Se pone a 0 y avanza. | ||||||||
| Puntero en Marco 1 (bit = 0). Se reemplaza la página 1 por la 5. | ||||||||
| 1 | 5 (1) | 1 (1) | 3 (0) | 4 (0) | 1 | 2 | F | Reemplazo: Puntero en Marco 2 (bit = 0). Se reemplaza la página 2 por la 1. |
| 2 | 5 (1) | 1 (1) | 2 (1) | 4 (0) | 1 | 3 | F | Reemplazo: Puntero en Marco 3 (bit = 0). Se reemplaza la página 3 por la 2. |
| 3 | 5 (1) | 1 (1) | 2 (1) | 3 (1) | 1 | 4 | F | Reemplazo: Puntero en Marco 4 (bit = 0). Se reemplaza la página 4 por la 3. |
| 4 | 4 (1) | 1 (1) | 2 (1) | 3 (1) | 1 | 1 | F | Reemplazo: Puntero en Marco 1 (bit = 1). Se pone a 0 y avanza. |
| Puntero en Marco 2 (bit = 1). Se pone a 0 y avanza. | ||||||||
| Puntero en Marco 3 (bit = 1). Se pone a 0 y avanza. | ||||||||
| Puntero en Marco 4 (bit = 0). Se reemplaza la página 5 por la 4. | ||||||||
| 5 | 4 (1) | 5 (1) | 2 (1) | 3 (1) | 1 | 2 | F | Reemplazo: Puntero en Marco 2 (bit = 0). Se reemplaza la página 1 por la 5. |
En resumen, hay un total de fallos de página: 10
Explicación del Diagrama
- Primeras referencias (1, 2, 3, 4):
- Las páginas 1, 2, 3 y 4 se cargan en los marcos disponibles, y sus bits de referencia se establecen en 1.
- Referencias posteriores (1, 2, 5, 1, 2, 3, 4, 5):
- Cuando no hay marcos libres, el algoritmo CLOCK busca una página para reemplazar, comenzando desde la posición del puntero.
- Si el bit de referencia es 1, se le da una segunda oportunidad: el bit se restablece a 0, y el puntero avanza.
- Si el bit de referencia es 0, la página se reemplaza.
Algoritmo NRU
El algoritmo NRU (Not Recently Used) utiliza dos bits para cada página:
- Bit de referencia (R): Indica si la página ha sido accedida recientemente (1) o (0).
- Bit de modificación (M): Indica si la página ha sido modificada (1) o no (0).
El algoritmo clasifica las páginas en cuatro categorías y selecciona una página para reemplazar, basándose en estas categorías. La idea es que es mejor reemplazar una página que no ha sido usada ni modificada recientemente.
Funcionamiento:
- Inicialización:
- El sistema operativo pone en 0 los bits de referencia de todas las páginas periódicamente (por ejemplo, en cada tic de reloj).
- Si una página es referenciada o modificada, su respectivo bit se establece en 1.
- Categorías de páginas:
- La página se divide en cuatro categorías:
- No referenciadas, modificadas (R=0, M=0): Páginas que no han sido usadas ni modificadas recientemente.
- No referenciadas, modificadas (R=0, M=1): Páginas que no han sido usadas recientemente, pero fueron modificadas.
- Referenciadas, no modificadas (R=1, M=0): Páginas que han sido usadas recientemente, pero no modificadas.
- Referenciadas, modificadas (R=1, M=1): Páginas que han sido usadas y modificadas recientemente.
- La página se divide en cuatro categorías:
- Reemplazo de páginas:
- El algoritmo selecciona una página para reemplazar en el siguiente orden de prioridad:
- Categoría 1 (R=0, M=0).
- Categoría 2 (R=0, M=1).
- Categoría 3 (R=1, M=0).
- Categoría 4 (R=1, M=1).
- El algoritmo selecciona una página para reemplazar en el siguiente orden de prioridad:
Ejemplo con 4 Marcos de Memoria
Vamos a usar un ejemplo con una secuencia de referencias a páginas y 4 marcos de memoria.
Secuencia de Referencias: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5
Pasos:
- Inicialmente, todas las páginas tienen R=0 y M=0.
- Cuando una página es referenciada, su bit R se establece en 1.
- Cuando una página es modificada, su bit M se establece en 1.
Diagrama
| Referencia | Marco 1 | Marco 2 | Marco 3 | Marco 4 | Bit R | Bit M | Fallo de Página (F) | Explicación |
|---|---|---|---|---|---|---|---|---|
| 1 | 1 | – | – | – | 1 | 0 | F | Marco 1: 1 (nuevo), R=1, M=0 |
| 2 | 1 | 2 | – | – | 1 | 0 | F | Marco 2: 2 (nuevo), R=1, M=0 |
| 3 | 1 | 2 | 3 | – | 1 | 0 | F | Marco 3: 3 (nuevo), R=1, M=0 |
| 4 | 1 | 2 | 3 | 4 | 1 | 0 | F | Marco 4: 4 (nuevo), R=1, M=0 |
| 1 | 1 | 2 | 3 | 4 | 1 | 0 | – | La página 1 ya está en memoria, R=1, M=0 |
| 2 | 1 | 2 | 3 | 4 | 1 | 0 | – | La página 2 ya está en memoria, R=1, M=0 |
| 5 | 5 | 2 | 3 | 4 | 1 | 0 | F | Reemplazo: Página 1 (R=1, M=0) es reemplazada por 5. R=1, M=0 para 5. |
| 1 | 5 | 1 | 3 | 4 | 1 | 0 | F | Reemplazo: Página 2 (R=1, M=0) es reemplazada por 1. R=1, M=0 para 1. |
| 2 | 5 | 1 | 2 | 4 | 1 | 0 | F | Reemplazo: Página 3 (R=1, M=0) es reemplazada por 2. R=1, M=0 para 2. |
| 3 | 5 | 1 | 2 | 3 | 1 | 0 | F | Reemplazo: Página 4 (R=1, M=0) es reemplazada por 3. R=1, M=0 para 3. |
| 4 | 4 | 1 | 2 | 3 | 1 | 0 | F | Reemplazo: Página 5 (R=1, M=0) es reemplazada por 4. R=1, M=0 para 4. |
| 5 | 4 | 5 | 2 | 3 | 1 | 0 | F | Reemplazo: Página 1 (R=1, M=0) es reemplazada por 5. R=1, M=0 para 5. |
En resumen, hay un total de fallos de página: 10
Explicación del Diagrama
- Primeras referencias (1, 2, 3, 4):
- Las páginas 1, 2, 3 y 4 se cargan en los marcos disponibles, y sus bits de referencia se establecen en 1.
- Referencias posteriores (1, 2, 5, 1, 2, 3, 4, 5):
- Cuando no hay marcos libres, el algoritmo NRU selecciona una página para reemplazar basándose en las categorías.
- En este ejemplo, todas las páginas tienen R=1 y M=0, por lo que se reemplazan en orden FIFO.
Ejercicios Prácticos
Ahora que has adquirido el conocimiento prohibido de estos algoritmos, te invito a ponerlo en práctica. A continuación, encontrarás algunos ejercicios prácticos que te ayudarán a afianzar tus conocimientos.
- Ejercicio de FIFO:
- Descripción: Dada una secuencia de referencias a páginas: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5 y un tamaño de marco de página de 3, simula el algoritmo FIFO.
- Instrucciones:
- Crea una tabla para llevar el registro de los marcos de página.
- Para cada referencia, determina si hay un fallo de página y qué página se reemplaza.
- Cuenta el número total de fallos de página.
- Ejercicio de LRU:
- Descripción: Usa la misma secuencia de referencias a páginas: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5 y un tamaño de marco de página de 3, pero esta vez simula el algoritmo LRU.
- Instrucciones:
- Crea una tabla para llevar el registro de los marcos de página.
- Para cada referencia, determina cuál es la página menos recientemente usada y reemplázala si es necesario.
- Cuenta el número total de fallos de página.
- Ejercicio de Segunda Oportunidad:
- Descripción: Dada una secuencia de referencias a páginas: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5 y un tamaño de marco de página de 3, simula el algoritmo de Segunda Oportunidad.
- Instrucciones:
- Crea una tabla para llevar el registro de los marcos de página y un bit de referencia para cada página.
- Para cada referencia, verifica el bit de referencia y decide si la página tiene una segunda oportunidad o debe ser reemplazada.
- Cuenta el número total de fallos de página.
- Ejercicio de Envejecimiento:
- Descripción: Usa la misma secuencia de referencias a páginas: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5 y un tamaño de marco de página de 3, simula el algoritmo de Envejecimiento.
- Instrucciones:
- Crea una tabla para llevar el registro de los marcos de página y un contador de envejecimiento para cada página.
- Para cada referencia, actualiza los contadores de envejecimiento y decide qué página reemplazar basándote en los valores de los contadores.
- Cuenta el número total de fallos de página.
Conclusión
Los algoritmos de sustitución de página son esenciales para la gestión eficiente de la memoria en los sistemas operativos. Desde los más simples como FIFO hasta los más avanzados como el algoritmo de envejecimiento, cada uno tiene sus ventajas y desventajas dependiendo del contexto en el que se utilicen. Comprender cómo funcionan estos algoritmos no solo te permitirá entender mejor el comportamiento de tu sistema operativo, sino también optimizar el rendimiento de las aplicaciones que desarrolles o utilices.