FIFO y LRU: 8 ejercicios de reemplazo de páginas
Ocho ejercicios resueltos de FIFO y LRU con trazas paso a paso: fallos, aciertos, víctimas y estado final. Modelos claros y opciones razonadas.
En estos ejercicios de FIFO y LRU, cada referencia debe dejar una fila comprobable. Obtener el mismo conjunto final de páginas no significa haber tenido los mismos fallos: los casos 1 y 2 permiten ver esa diferencia.
Hay ocho preguntas originales con cuatro alternativas, soluciones desplegables y trazas completas. Algunas comparan la misma secuencia bajo políticas o capacidades distintas. Los datos, secuencias y tablas son propios; no se reproducen preguntas oficiales ni se anticipa el formato de una convocatoria.
Modelo que se aplica
Todas las referencias corresponden a páginas válidas de un único proceso. Hay un número fijo de marcos y cada uno alberga una página. La memoria empieza vacía salvo en el caso 6, que da un estado inicial. Una página ausente genera un fallo y se carga a demanda; si queda hueco libre, no hace falta expulsar ninguna.
Contamos una vez cada referencia del enunciado. No añadimos referencias por la atención del fallo ni estudiamos accesos ilegales, permisos, TLB, páginas modificadas, prelectura o costes temporales. Son simulaciones abstractas de reemplazo; no describen la política de un kernel concreto ni implican que cualquier fallo real de página requiera leer del disco.
El capítulo 22 de Operating Systems: Three Easy Pieces, de Remzi y Andrea Arpaci-Dusseau, apartados 22.3 y 22.5, y las notas de Page Selection and Replacement de CS 537 sirven de referencia para las políticas.
| Política | Criterio de sustitución de este modelo | Orden de nuestras tablas |
|---|---|---|
| FIFO | Sale la que entró antes de las residentes; un acierto no cambia esa antigüedad | Entrada más antigua a más nueva |
| LRU exacto | Sale la residente cuyo último acceso es más antiguo; cada acceso actualiza la recencia | Uso menos reciente a más reciente |
F significa fallo y H acierto. «Sin expulsión» puede acompañar un fallo si hay un marco libre. El orden mostrado es el de la política: no representa posiciones físicas numeradas de RAM. La tasa de aciertos solicitada se calcula como aciertos divididos entre todas las referencias indicadas.
Ejercicio 1. Contar fallos con FIFO
Con tres marcos vacíos y FIFO, se referencia la secuencia 2, 4, 2, 6, 4, 8, 2, 4. ¿Cuántos fallos de página se producen, incluyendo las cargas iniciales?
A. 4 fallos.
B. 5 fallos.
C. 6 fallos.
D. 8 fallos.
Ver solución del ejercicio 1
Correcta: C. Hay 6 fallos y 2 aciertos. Los fallos ocurren en los pasos 1, 2, 4, 6, 7 y 8. Las tres primeras cargas no expulsan ninguna página porque todavía hay marcos libres. Aun así, cuentan como fallos.
En el paso 3 se acierta sobre 2, pero FIFO conserva el orden de entrada. En el 6 sale 2; en el 7 sale 4 y el último acceso a 4 vuelve a fallar. A y B dejan fallos fuera del recuento; D trata como fallos los dos accesos que sí encuentran su página.
Traza 1.1: FIFO, tres marcos
| Paso | Página | Resultado | Expulsada | Orden tras atender |
|---|---|---|---|---|
| 1 | 2 | F | Sin expulsión | 2 |
| 2 | 4 | F | Sin expulsión | 2, 4 |
| 3 | 2 | H | Sin expulsión | 2, 4 |
| 4 | 6 | F | Sin expulsión | 2, 4, 6 |
| 5 | 4 | H | Sin expulsión | 2, 4, 6 |
| 6 | 8 | F | 2 | 4, 6, 8 |
| 7 | 2 | F | 4 | 6, 8, 2 |
| 8 | 4 | F | 6 | 8, 2, 4 |
Ejercicio 2. Repetir la secuencia con LRU
Con tres marcos vacíos y LRU exacto, se referencia la secuencia 2, 4, 2, 6, 4, 8, 2, 4. ¿Cuántos fallos de página se producen, incluyendo las cargas iniciales?
A. 3 fallos.
B. 4 fallos.
C. 6 fallos.
D. 5 fallos.
Ver solución del ejercicio 2
Correcta: D. Hay 5 fallos y 3 aciertos. En el paso 6 se expulsa 2, pero en el paso 7 se expulsa 6: 4 se había usado más recientemente. Por eso el paso 8, que pide 4, es un acierto.
La opción C traslada el total FIFO del caso anterior. A cuenta solo las tres primeras páginas cargadas, aunque más tarde llegan referencias ausentes. B se queda un fallo por debajo. El conjunto final coincide con el de FIFO, pero eso no obliga a que coincida el historial de fallos: hay que recorrer todos los pasos.
Traza 2.1: LRU, tres marcos
| Paso | Página | Resultado | Expulsada | Orden tras atender |
|---|---|---|---|---|
| 1 | 2 | F | Sin expulsión | 2 |
| 2 | 4 | F | Sin expulsión | 2, 4 |
| 3 | 2 | H | Sin expulsión | 4, 2 |
| 4 | 6 | F | Sin expulsión | 4, 2, 6 |
| 5 | 4 | H | Sin expulsión | 2, 6, 4 |
| 6 | 8 | F | 2 | 6, 4, 8 |
| 7 | 2 | F | 6 | 4, 8, 2 |
| 8 | 4 | H | Sin expulsión | 8, 2, 4 |
Ejercicio 3. Un acierto no rejuvenece la entrada FIFO
Con tres marcos vacíos y FIFO, la secuencia es 7, 9, 7, 11, 7, 13. ¿Qué página se expulsa al atender la última referencia, 13?
A. La página 7.
B. La página 9.
C. La página 11.
D. La página 13.
Ver solución del ejercicio 3
Correcta: A. Sale 7, porque entró antes que 9 y 11. Los accesos de los pasos 3 y 5 no modifican su antigüedad de entrada en FIFO. Justo antes de pedir 13, el orden sigue siendo 7, 9, 11.
B responde a otra política, como comprobarás con LRU en el siguiente caso. C confunde la más nueva de las residentes con la más antigua. D elige la página que debe incorporarse: 13 no estaba residente para ser la víctima. Se producen cuatro fallos, pero solo el último necesita una expulsión.
Traza 3.1: FIFO y los aciertos sobre 7
| Paso | Página | Resultado | Expulsada | Orden tras atender |
|---|---|---|---|---|
| 1 | 7 | F | Sin expulsión | 7 |
| 2 | 9 | F | Sin expulsión | 7, 9 |
| 3 | 7 | H | Sin expulsión | 7, 9 |
| 4 | 11 | F | Sin expulsión | 7, 9, 11 |
| 5 | 7 | H | Sin expulsión | 7, 9, 11 |
| 6 | 13 | F | 7 | 9, 11, 13 |
Ejercicio 4. La página menos reciente no es la más antigua
Con tres marcos vacíos y LRU exacto, la secuencia es 7, 9, 7, 11, 7, 13. ¿Qué página se expulsa al atender la última referencia, 13?
A. La página 7.
B. La página 9.
C. La página 11.
D. La página 13.
Ver solución del ejercicio 4
Correcta: B. Sale 9. Antes del último acceso, los usos más recientes de las residentes fueron: 9 en el paso 2, 11 en el 4 y 7 en el 5. El menor de esos instantes corresponde a 9.
A conserva la decisión FIFO del caso anterior sin aplicar la actualización por uso. C escoge una página utilizada después que 9. D propone expulsar la recién solicitada, que aún no está cargada. No cuentes cuántas veces apareció cada página: LRU utiliza el último acceso, no la frecuencia acumulada.
Traza 4.1: LRU y los aciertos sobre 7
| Paso | Página | Resultado | Expulsada | Orden tras atender |
|---|---|---|---|---|
| 1 | 7 | F | Sin expulsión | 7 |
| 2 | 9 | F | Sin expulsión | 7, 9 |
| 3 | 7 | H | Sin expulsión | 9, 7 |
| 4 | 11 | F | Sin expulsión | 9, 7, 11 |
| 5 | 7 | H | Sin expulsión | 9, 11, 7 |
| 6 | 13 | F | 9 | 11, 7, 13 |
Ejercicio 5. Calcular la tasa sin excluir el arranque
Con tres marcos vacíos y LRU, se referencia 5, 6, 5, 7, 6, 5, 8, 5, 6, 8. ¿Cuál es la tasa de aciertos sobre las diez referencias, sin excluir el arranque en frío?
A. 40 %.
B. 60 %.
C. 66,67 %.
D. 75 %.
Ver solución del ejercicio 5
Correcta: B. Hay 6 aciertos de 10 referencias, de modo que la tasa es 60 %. Los cuatro fallos están en 1, 2, 4 y 7. La suma 6 + 4 reconstruye las diez referencias, sin eliminar las primeras cargas.
A es la tasa de fallos, 4/10. C y D no corresponden al cociente solicitado: podrían surgir al cambiar el denominador o quitar accesos sin autorización. La tasa describe esta secuencia y este modelo; no informa de nanosegundos, tráfico de disco ni rendimiento de un equipo.
Traza 5.1: LRU y tasa de aciertos
| Paso | Página | Resultado | Expulsada | Orden tras atender |
|---|---|---|---|---|
| 1 | 5 | F | Sin expulsión | 5 |
| 2 | 6 | F | Sin expulsión | 5, 6 |
| 3 | 5 | H | Sin expulsión | 6, 5 |
| 4 | 7 | F | Sin expulsión | 6, 5, 7 |
| 5 | 6 | H | Sin expulsión | 5, 7, 6 |
| 6 | 5 | H | Sin expulsión | 7, 6, 5 |
| 7 | 8 | F | 7 | 6, 5, 8 |
| 8 | 5 | H | Sin expulsión | 6, 8, 5 |
| 9 | 6 | H | Sin expulsión | 8, 5, 6 |
| 10 | 8 | H | Sin expulsión | 5, 6, 8 |
Ejercicio 6. Continuar desde un estado ya cargado
Este caso comienza con tres páginas residentes ordenadas de menos a más recientemente usada: 12, 3, 8. Se aplica LRU y se atiende solo la continuación 3, 14. ¿Cuál es el orden final de menos a más reciente?
A. 3, 8, 14.
B. 12, 3, 14.
C. 14, 3, 8.
D. 8, 3, 14.
Ver solución del ejercicio 6
Correcta: D. Primero 3 es un acierto y pasa al extremo más reciente: 12, 8, 3. Después 14 falla y sustituye a 12, dejando 8, 3, 14. Solo se cuentan los dos accesos nuevos: un acierto y un fallo.
A no actualiza la posición de 3 al acertar. B expulsa 8, aunque 12 era menos reciente. C invierte el criterio de lectura del orden final. Las páginas iniciales ya estaban cargadas: no añadas tres fallos anteriores a una continuación cuyo comienzo está expresamente fijado.
Traza 6.1: LRU con estado inicial dado
| Paso | Página | Resultado | Expulsada | Orden tras atender |
|---|---|---|---|---|
| 1 | 3 | H | Sin expulsión | 12, 8, 3 |
| 2 | 14 | F | 12 | 8, 3, 14 |
Ejercicio 7. Cambiar la capacidad y reiniciar el caso
Se ejecuta LRU sobre 1, 3, 1, 5, 3, 1, 5 dos veces independientes, ambas desde vacío: una con dos marcos y otra con tres. ¿Cuántos fallos se obtienen, respectivamente?
A. 6 y 3 fallos.
B. 3 y 6 fallos.
C. 6 y 6 fallos.
D. 5 y 3 fallos.
Ver solución del ejercicio 7
Correcta: A. Con dos marcos hay 6 fallos; solo acierta el paso 3. Con tres marcos hay 3 fallos, uno por cada página distinta de esta secuencia. Después de incorporar 5 en el paso 4, las tres páginas caben simultáneamente.
B invierte los resultados. C reutiliza el recuento de dos marcos sin rehacer el caso con tres. D omite un fallo de la ejecución pequeña. No amplíes una ejecución que ya comenzó: la pregunta compara dos arranques vacíos, manteniendo idéntica secuencia.
Traza 7.1: LRU, dos marcos
| Paso | Página | Resultado | Expulsada | Orden tras atender |
|---|---|---|---|---|
| 1 | 1 | F | Sin expulsión | 1 |
| 2 | 3 | F | Sin expulsión | 1, 3 |
| 3 | 1 | H | Sin expulsión | 3, 1 |
| 4 | 5 | F | 3 | 1, 5 |
| 5 | 3 | F | 1 | 5, 3 |
| 6 | 1 | F | 5 | 3, 1 |
| 7 | 5 | F | 3 | 1, 5 |
Traza 7.2: LRU, tres marcos
| Paso | Página | Resultado | Expulsada | Orden tras atender |
|---|---|---|---|---|
| 1 | 1 | F | Sin expulsión | 1 |
| 2 | 3 | F | Sin expulsión | 1, 3 |
| 3 | 1 | H | Sin expulsión | 3, 1 |
| 4 | 5 | F | Sin expulsión | 3, 1, 5 |
| 5 | 3 | H | Sin expulsión | 1, 5, 3 |
| 6 | 1 | H | Sin expulsión | 5, 3, 1 |
| 7 | 5 | H | Sin expulsión | 3, 1, 5 |
Ejercicio 8. Comparar políticas sin suponer una vencedora universal
Con dos marcos inicialmente vacíos se ejecuta la secuencia 4, 9, 4, 12, 9 por separado con FIFO y LRU. ¿Cuántos fallos produce FIFO y cuántos LRU, en ese orden?
A. 3 y 3 fallos.
B. 4 y 3 fallos.
C. 3 y 4 fallos.
D. 4 y 4 fallos.
Ver solución del ejercicio 8
Correcta: C. FIFO produce 3 fallos y LRU 4 fallos. En el paso 4, FIFO expulsa 4 y conserva 9; LRU expulsa 9 porque 4 se acaba de usar. Cuando vuelve a pedirse 9, FIFO acierta y LRU falla.
A pasa por alto ese último fallo LRU. B intercambia los recuentos. D atribuye a FIFO un fallo en el último acceso pese a que conserva 9. Este pequeño contraejemplo impide concluir que LRU siempre dé menos fallos que FIFO. Tampoco demuestra que FIFO sea mejor en cualquier secuencia.
Traza 8.1: FIFO, dos marcos
| Paso | Página | Resultado | Expulsada | Orden tras atender |
|---|---|---|---|---|
| 1 | 4 | F | Sin expulsión | 4 |
| 2 | 9 | F | Sin expulsión | 4, 9 |
| 3 | 4 | H | Sin expulsión | 4, 9 |
| 4 | 12 | F | 4 | 9, 12 |
| 5 | 9 | H | Sin expulsión | 9, 12 |
Traza 8.2: LRU, dos marcos
| Paso | Página | Resultado | Expulsada | Orden tras atender |
|---|---|---|---|---|
| 1 | 4 | F | Sin expulsión | 4 |
| 2 | 9 | F | Sin expulsión | 4, 9 |
| 3 | 4 | H | Sin expulsión | 9, 4 |
| 4 | 12 | F | 9 | 4, 12 |
| 5 | 9 | F | 4 | 12, 9 |
Clave y controles del recuento
La clave es CDABBDAC. Hay dos respuestas de cada letra, pero ninguna se deduce por la distribución: comprueba el estado antes de cada referencia.
En cada fila, la página solicitada debe quedar residente después de atenderla. Nunca puede haber más páginas residentes que marcos ni dos copias de una misma página en el estado mostrado. Un acierto conserva el conjunto de residentes, aunque LRU pueda cambiar su orden. Una expulsión requiere un fallo con los marcos ocupados.
Suma F y H: el resultado debe coincidir con el número de referencias. Después comprueba qué se pide: un total, una víctima, una tasa o un orden. En el caso 5, seis aciertos son 60 % sobre diez; en el 6, el orden final no es una lista de números de marco. Los casos 7 y 8 reinician cada ejecución desde vacío para poder compararlas.
Continuar el bloque de sistemas operativos
Los ocho ejercicios de planificación de procesos trabajan otra decisión: qué proceso ocupa la CPU y cuánto espera. Puedes usarlos junto a esta práctica para separar planificación de CPU y reemplazo de páginas.
El material de Técnico Medio de Sistemas de Valladolid incluye gestión de memoria y paginación en el apartado «47.2 Fundamentos, arquitectura, procesos, memoria y tendencias». Es un producto de pago cuya ficha detalla el alcance. Aquí ampliamos ese tema con cálculos de FIFO y LRU; no afirmamos que el material desarrolle estas mismas trazas ni que la convocatoria las vaya a preguntar.
Preguntas frecuentes
¿Las primeras cargas cuentan como fallos de página?
Sí en los casos que empiezan vacíos: si la página solicitada no está residente, se cuenta un fallo aunque quede un marco libre. El caso 6 comienza con páginas cargadas y solo cuenta su continuación.
¿FIFO cambia el orden cuando hay un acierto?
En este modelo no: el acierto no modifica el orden de entrada. La tabla del caso 3 conserva 7, 9, 11 antes de incorporar 13.
¿LRU es lo mismo que la página menos frecuente?
No. LRU compara la recencia del último acceso. En el caso 4 sale 9 porque su último uso es anterior al de las otras residentes.
¿Qué significan los órdenes de las tablas?
En FIFO van de entrada más antigua a más nueva. En LRU van de uso menos reciente a más reciente. Son órdenes de política, no posiciones físicas fijas de los marcos.
¿LRU obtiene siempre menos fallos que FIFO?
No. En la secuencia del caso 8, con dos marcos vacíos, FIFO tiene tres fallos y LRU cuatro. La conclusión se limita al recuento de esa secuencia; no es una medición de un sistema operativo real.
Otra práctica de trazas: búsqueda binaria
Para practicar el seguimiento de otro algoritmo, utiliza los ocho ejercicios resueltos de búsqueda binaria. Trabajan índices, intervalos y duplicados en listas ordenadas; es un problema distinto del reemplazo de páginas de esta guía.
