Algoritmos de Reemplazo de Páginas
1. FIFO (First-In, First-Out)
Descripción:
El algoritmo FIFO reemplaza la página que llegó primero a la memoria. Es simple y fácil de implementar, ya que solo necesita recordar el orden de llegada.
Función:
Cuando llega una nueva página y la memoria está llena, FIFO reemplaza la página que ha estado allí más tiempo, sin importar si se ha usado recientemente.
Ejemplo de Implementación:
Secuencia de referencias: [3, 2, 4, 1, 3, 2, 5]
Número de marcos: 3
| Paso | Referencia | Marcos de Página (Estado) | Acción |
|---|---|---|---|
| 1 | 3 | [3, -, -] | Agrega 3 |
| 2 | 2 | [3, 2, -] | Agrega 2 |
| 3 | 4 | [3, 2, 4] | Agrega 4 |
| 4 | 1 | [1, 2, 4] | Reemplaza 3 |
| 5 | 3 | [1, 3, 4] | Reemplaza 2 |
| 6 | 2 | [1, 3, 2] | Reemplaza 4 |
| 7 | 5 | [5, 3, 2] | Reemplaza 1 |
2. LFU (Least Frequently Used)
Descripción:
LFU reemplaza la página que ha sido utilizada menos veces en el pasado. La idea es que las páginas menos utilizadas probablemente no se necesitarán en el futuro cercano.
Función:
Cuando se necesita espacio, LFU elige la página con el menor contador de usos. Si varias páginas tienen el mismo contador, se usa FIFO entre ellas.
Ejemplo de Implementación:
Secuencia de referencias: [3, 2, 4, 1, 3, 2, 5]
Número de marcos: 3
| Paso | Referencia | Marcos de Página (Estado) | Contador de Usos | Acción |
|---|---|---|---|---|
| 1 | 3 | [3, -, -] | [1, 0, 0] | Agrega 3 |
| 2 | 2 | [3, 2, -] | [1, 1, 0] | Agrega 2 |
| 3 | 4 | [3, 2, 4] | [1, 1, 1] | Agrega 4 |
| 4 | 1 | [1, 2, 4] | [1, 2, 1] | Reemplaza 3 |
| 5 | 3 | [1, 3, 4] | [1, 2, 1] | Reemplaza 2 |
| 6 | 2 | [1, 3, 2] | [1, 1, 2] | Reemplaza 4 |
| 7 | 5 | [5, 3, 2] | [1, 1, 2] | Reemplaza 1 |
3. MFU (Most Frequently Used)
Descripción:
MFU reemplaza la página que ha sido utilizada más veces, bajo la suposición de que si se ha usado mucho, ya no será tan necesaria.
Función:
Cuando es necesario un reemplazo, MFU elige la página con el mayor contador de usos. Si varias tienen el mismo contador, se usa FIFO entre ellas.
Ejemplo de Implementación:
Secuencia de referencias: [3, 2, 4, 1, 3, 2, 5]
Número de marcos: 3
| Paso | Referencia | Marcos de Página (Estado) | Contador de Usos | Acción |
|---|---|---|---|---|
| 1 | 3 | [3, -, -] | [1, 0, 0] | Agrega 3 |
| 2 | 2 | [3, 2, -] | [1, 1, 0] | Agrega 2 |
| 3 | 4 | [3, 2, 4] | [1, 1, 1] | Agrega 4 |
| 4 | 1 | [1, 2, 4] | [1, 2, 1] | Reemplaza 3 |
| 5 | 3 | [1, 3, 4] | [1, 2, 1] | Reemplaza 2 |
| 6 | 2 | [1, 3, 2] | [1, 1, 2] | Reemplaza 4 |
| 7 | 5 | [5, 3, 2] | [1, 1, 2] | Reemplaza 1 |
4. Segunda Oportunidad
Descripción:
Este algoritmo mejora FIFO al dar una «segunda oportunidad» a las páginas que han sido usadas recientemente. Cada página tiene un bit de referencia que indica si ha sido utilizada.
Función:
Si una página es usada recientemente, su bit de referencia se pone en 1. Al reemplazar, el algoritmo da una segunda oportunidad a las páginas con el bit en 1, poniéndolo en 0 y avanzando al siguiente marco hasta encontrar una página con 0 en el bit de referencia.
Ejemplo de Implementación:
Secuencia de referencias: [3, 2, 4, 1, 3, 2, 5]
Número de marcos: 3
| Paso | Referencia | Marcos de Página (Estado) | Bits de Referencia | Puntero (Reloj) | Acción |
|---|---|---|---|---|---|
| 1 | 3 | [3, -, -] | [1, 0, 0] | ➔ posición 1 | Agrega 3 |
| 2 | 2 | [3, 2, -] | [1, 1, 0] | ➔ posición 2 | Agrega 2 |
| 3 | 4 | [3, 2, 4] | [1, 1, 1] | ➔ posición 3 | Agrega 4 |
| 4 | 1 | [1, 2, 4] | [1, 1, 0] | ➔ posición 1 | Reemplaza 3, agrega 1 |
| 5 | 3 | [1, 3, 4] | [1, 1, 0] | ➔ posición 2 | Reemplaza 2, agrega 3 |
| 6 | 2 | [1, 3, 2] | [1, 1, 1] | ➔ posición 3 | Reemplaza 4, agrega 2 |
5. Segunda Oportunidad Mejorada
Descripción:
Es una mejora de Segunda Oportunidad, que utiliza tanto el bit de referencia (para saber si fue usado) como el bit de modificación (para saber si fue modificado). Esto permite priorizar páginas no modificadas y no usadas.
Función:
El algoritmo clasifica las páginas en cuatro combinaciones de (Referencia, Modificación) y sigue el siguiente orden de prioridad para el reemplazo:
(0, 0): No usada ni modificada (primera prioridad).(0, 1): No usada pero modificada.(1, 0): Usada pero no modificada.(1, 1): Usada y modificada (última prioridad).
Ejemplo de Implementación:
Secuencia de referencias: [3, 2, 5, 1, 2, 3, 7, 6]
Número de marcos: 3
| Paso | Referencia | Marcos de Página (Estado) | Bits (Usado, Modificado) | Puntero (Reloj) | Acción |
|---|---|---|---|---|---|
| 1 | 3 | [3, -, -] | [(1, 0), (0, 0), (0, 0)] | ➔ posición 1 | Agrega 3 |
| 2 | 2 | [3, 2, -] | [(1, 0), (1, 0), (0, 0)] | ➔ posición 2 | Agrega 2 |
| 3 | 5 | [3, 2, 5] | [(1, 0), (1, 0), (1, 0)] | ➔ posición 3 | Agrega 5 |
| 4 | 1 | [1, 2, 5] | [(1, 0), (1, 0), (0, 0)] | ➔ posición 1 | Reemplaza 3, agrega 1 |
| 5 | 2 | [1, 2, 5] | [(1, 0), (1, 0), (1, 0)] | ➔ posición 2 | 2 ya está, bit en 1 |
| 6 | 3 | [1, 2, 3] | [(0, 0), (1, 0), (1, 0)] | ➔ posición 3 | Reemplaza 5, agrega 3 |