Memoria virtual — ejercicios tipo examen con fallos de página, trazas de FIFO, LRU y óptimo y conjuntos de trabajo (y los tres fallos que no conté en el simulacro)
En el simulacro de IC2 me tocó una traza de LRU con 3 marcos. La hice con cuidado, conté 6 fallos y me fui tan contento. Eran 9. ¿El motivo? Los tres primeros accesos los di por aciertos porque «los marcos estaban vacíos y la página entraba sin echar a nadie». Entrar sin víctima no quita que sea un fallo: la página no estaba en RAM y hubo que traerla del disco. Son los fallos obligatorios, y aquí los vas a contar siempre.
Este artículo es la práctica de la teoría de memoria virtual y reemplazo de páginas. Si vienes del Tema 9, gestión de memoria, aquí cerramos el bloque de memoria: fallo de página, algoritmos de reemplazo, anomalía de Belady, conjunto de trabajo e hiperpaginación, con preguntas en todos los formatos del examen. Antes de lanzarte, en la práctica guiada de memoria virtual tienes las trazas resueltas paso a paso.
Tabla de Contenidos
Cómo usar este artículo
- Haz el cuestionario sin mirar la teoría. Cada pregunta tiene su botón «Comprobar» y una explicación: léela también cuando aciertes, porque a veces explica por qué fallan las otras opciones.
- Las trazas, con papel. Dibuja la tabla (una columna por referencia, una fila por marco) antes de rellenar las casillas. Si te equivocas, compara tu tabla con la traza de la explicación.
- Las de desarrollo, por escrito. Escribe tu respuesta y después compárala con la respuesta modelo y con la lista «lo que se valora».
- Repasa con el chuletario del final antes del examen.
Las preguntas de múltiple respuesta penalizan como en el examen: cada casilla marcada mal resta. Si no estás seguro de una opción, mejor no marcarla.
Para comprobar una traza con otra cadena o con más marcos, el simulador de reemplazo de páginas la hace paso a paso con FIFO, LRU y el óptimo.
Cuestionario tipo test
31 preguntas: única, múltiple, verdadero o falso, huecos, relacionar, ordenar y respuesta corta. Van desde la definición de memoria virtual hasta el PFF, pasando por todos los algoritmos de reemplazo.
¿Qué permite, sobre todo, la memoria virtual?
- Ejecutar un proceso aunque solo una parte de sus páginas esté en la memoria principal
- Que cada proceso tenga para él solo toda la RAM del ordenador
- Que el programador decida qué partes van a la RAM y cuáles al disco
- Acceder al disco igual de rápido que a la RAM
Solución
Respuesta: Ejecutar un proceso aunque solo una parte de sus páginas esté en la memoria principal
Con memoria virtual el espacio lógico del proceso puede ser mayor que la RAM que tiene: el almacenamiento secundario hace de extensión de la memoria principal y el SO mueve páginas entre los dos sin que el programa se entere.
Sobre la memoria virtual, indica si es verdadero o falso:
- Un proceso puede tener unas páginas en la RAM y otras en el disco a la vez.
- Para empezar a ejecutarse, un proceso tiene que estar cargado entero en la RAM.
- La memoria principal se reparte entre los procesos que están en ejecución.
- El SO intenta dar siempre a cada proceso toda la RAM libre que haya.
- Es el programador quien marca en el código qué páginas se quedan en el disco.
Solución
- V — Un proceso puede tener unas páginas en la RAM y otras en el disco a la vez.
- F — Para empezar a ejecutarse, un proceso tiene que estar cargado entero en la RAM.
- V — La memoria principal se reparte entre los procesos que están en ejecución.
- F — El SO intenta dar siempre a cada proceso toda la RAM libre que haya.
- F — Es el programador quien marca en el código qué páginas se quedan en el disco.
La memoria virtual existe justo para que el proceso no tenga que estar entero en RAM. El SO reparte los marcos entre todos los procesos (no le da toda la RAM a uno) y decide él qué páginas están dentro y cuáles fuera; el programador no se ocupa de eso.
En la paginación por demanda, ¿cuándo se lee una página del disco?
- Cuando el proceso la referencia y no está en RAM (fallo de página)
- Al crear el proceso, todas de golpe
- Cuando falla la TLB
- Cada cierto tiempo, en el orden en que la CPU va a pedirlas
Solución
Respuesta: Cuando el proceso la referencia y no está en RAM (fallo de página)
Por demanda = no se carga una página hasta que hace falta. La primera referencia a cada página produce un fallo de página y es entonces cuando el SO la trae del disco. En la cadena de gcc del artículo, las páginas 0 y 6 no se leen nunca.
¿Qué bit de la entrada de la tabla de páginas indica si la página está en la memoria principal?
Solución
Respuesta: Bit de validez
El bit de validez (v/i, o bit de presencia): con v (1) la página está en un marco; con i (0) está en el disco y acceder a ella provoca un fallo de página.
Ordena lo que pasa cuando gcc pide una página que no está en RAM y sí hay un marco libre:
- Se repite la instrucción que provocó el fallo
- El SO toma un marco libre
- El SO comprueba que la referencia es válida y localiza la página en el disco
- Se lee la página del disco a ese marco
- La MMU ve el bit i en la tabla de páginas y lanza un trap
- Se actualiza la entrada: número de marco y bit de validez a v
Solución
Orden correcto:
- La MMU ve el bit i en la tabla de páginas y lanza un trap
- El SO comprueba que la referencia es válida y localiza la página en el disco
- El SO toma un marco libre
- Se lee la página del disco a ese marco
- Se actualiza la entrada: número de marco y bit de validez a v
- Se repite la instrucción que provocó el fallo
Primero salta el trap (la MMU no puede traducir), el SO busca la página, la mete en un marco libre, apunta el marco con v = 1 y vuelve a ejecutar la instrucción, que ahora sí encuentra la página. Si no hubiera marco libre, antes de leer habría que elegir víctima.
Ahora no hay marcos libres. Ordena los pasos para atender el fallo:
- Se lee la página nueva en el marco que ha quedado libre
- Si la víctima tiene M = 1, se escribe en el disco
- El algoritmo de reemplazo elige una página víctima
- Se actualiza la entrada de la página nueva y se repite la instrucción
- Se marca la víctima como inválida en su tabla de páginas
- Se produce el fallo de página
- El SO ve que no queda ningún marco libre
Solución
Orden correcto:
- Se produce el fallo de página
- El SO ve que no queda ningún marco libre
- El algoritmo de reemplazo elige una página víctima
- Si la víctima tiene M = 1, se escribe en el disco
- Se marca la víctima como inválida en su tabla de páginas
- Se lee la página nueva en el marco que ha quedado libre
- Se actualiza la entrada de la página nueva y se repite la instrucción
La diferencia con el caso anterior está en el medio: elegir víctima, guardarla si está sucia y marcarla como i (para que su dueño falle si vuelve a pedirla). Después se sigue igual: leer, actualizar y repetir.
El SO va a echar una página de un marco. ¿Qué le dice si tiene que escribirla antes en el disco?
- El bit de modificación (M)
- El bit de referencia (R)
- El bit de validez
- Los bits de protección
Solución
Respuesta: El bit de modificación (M)
El hardware pone M = 1 en cuanto se escribe en la página («página sucia»). Una víctima limpia (M = 0) se puede pisar sin más porque el disco ya tiene la misma copia; una sucia cuesta una escritura más.
¿Cómo se llama la técnica en la que el SO, cuando no tiene nada que hacer, escribe en el disco las páginas sucias y les pone M = 0?
Solución
Respuesta: Precleaning
Precleaning (prelimpieza): aprovecha los ratos ociosos para que, cuando haga falta una víctima, sea más probable encontrarla limpia y el fallo cueste un solo acceso a disco.
Marca los que son algoritmos de reemplazo de páginas:
- LRU
- Segunda oportunidad
- NFU
- Óptimo (OPT)
- Round Robin
- SRTF
- Mejor ajuste
- TLB
Solución
Respuesta: LRU · Segunda oportunidad · NFU · Óptimo (OPT)
Reemplazo de páginas: FIFO, óptimo, LRU y sus aproximaciones (segunda oportunidad o reloj, NRU, NFU, LFU, aging, WSClock). Cuidado con mezclarlos con los de la CPU (FCFS, SJF, SRTF, RR) o con los ajustes del Tema 9.
Relaciona cada algoritmo con la página que elige como víctima:
| FIFO | |
| Óptimo | |
| LRU | |
| LFU |
Definiciones:
- La que tiene el contador de usos más alto
- La que lleva más tiempo sin usarse
- La que se usó más recientemente
- La que tiene el contador de usos más bajo
- La que más tarde se va a volver a usar
- La que lleva más tiempo cargada en memoria
Solución
- FIFO → La que lleva más tiempo cargada en memoria
- Óptimo → La que más tarde se va a volver a usar
- LRU → La que lleva más tiempo sin usarse
- LFU → La que tiene el contador de usos más bajo
FIFO mira la llegada, LRU el último uso, el óptimo el próximo uso y LFU cuántas veces se ha usado (echa a la menos usada, no a la más).
¿Por qué ningún SO real implementa el algoritmo óptimo?
- Necesita saber qué páginas se van a pedir en el futuro
- Porque produce más fallos que LRU
- Porque sufre la anomalía de Belady
- Porque necesita un bit de modificación por página
Solución
Respuesta: Necesita saber qué páginas se van a pedir en el futuro
El óptimo echa la página que más tarde se volverá a referenciar, y eso exige conocer la cadena de referencias futura. Se usa como referencia para medir lo cerca que se queda un algoritmo real.
Sobre la anomalía de Belady:
- Consiste en que, con más marcos, un algoritmo puede dar más fallos de página.
- FIFO puede sufrirla.
- LRU puede sufrirla si la cadena es suficientemente larga.
- El algoritmo óptimo la sufre con 4 marcos o más.
Solución
- V — Consiste en que, con más marcos, un algoritmo puede dar más fallos de página.
- V — FIFO puede sufrirla.
- F — LRU puede sufrirla si la cadena es suficientemente larga.
- F — El algoritmo óptimo la sufre con 4 marcos o más.
La anomalía aparece en FIFO. LRU y el óptimo son algoritmos de pila: lo que tienen en memoria con n marcos está siempre contenido en lo que tendrían con n + 1, así que un marco más nunca empeora. En el artículo, FIFO pasa de 9 a 10 fallos al pasar de 3 a 4 marcos.
Para implementar LRU de forma exacta, ¿qué hace falta?
- Apuntar en cada acceso cuándo se usó cada página (contador o pila), y eso cuesta mucho
- Solo el bit de modificación
- Una cola con el orden de llegada
- Conocer las referencias futuras
Solución
Respuesta: Apuntar en cada acceso cuándo se usó cada página (contador o pila), y eso cuesta mucho
LRU exacto necesita, en cada acceso, guardar un instante (contador) o mover la página a la cima de una pila. Hacerlo por software sería lentísimo y por hardware es caro: por eso se usan aproximaciones con el bit R.
En el algoritmo de la segunda oportunidad, la aguja llega a una página con R = 1. ¿Qué pasa?
- Se le pone R = 0 y la aguja pasa a la siguiente
- Se elige como víctima porque es la más antigua
- Se escribe en el disco y se queda en memoria
- Se le pone M = 0
Solución
Respuesta: Se le pone R = 0 y la aguja pasa a la siguiente
Es FIFO con una pregunta extra: «¿te han usado desde la última vez?». Si R = 1, se le perdona (R pasa a 0) y se sigue; la víctima es la primera página que encuentra con R = 0.
En NRU, ¿de qué clase se prefiere sacar la víctima?
- R = 0 y M = 0
- R = 0 y M = 1
- R = 1 y M = 0
- R = 1 y M = 1
Solución
Respuesta: R = 0 y M = 0
NRU agrupa las páginas en cuatro clases por (R, M) y elige al azar dentro de la clase no vacía más baja: 0 (0, 0), 1 (0, 1), 2 (1, 0), 3 (1, 1).
Relaciona cada aproximación de LRU con lo que guarda por página:
| NFU | |
| Aging | |
| LFU | |
| Reloj |
Definiciones:
- La hora exacta de cada acceso
- Un registro que se desplaza y recibe el bit R por la izquierda
- Solo el bit R y una aguja que recorre los marcos en círculo
- Un contador que suma el bit R a intervalos regulares
- Un contador del número de referencias
Solución
- NFU → Un contador que suma el bit R a intervalos regulares
- Aging → Un registro que se desplaza y recibe el bit R por la izquierda
- LFU → Un contador del número de referencias
- Reloj → Solo el bit R y una aguja que recorre los marcos en círculo
NFU suma R a un contador cada tic (nunca olvida). Aging desplaza el registro a la derecha y mete R por la izquierda, así lo reciente pesa más. LFU cuenta referencias. El reloj solo necesita R. Guardar la hora exacta de cada acceso sería LRU exacto, no una aproximación.
Con aging y registros de 4 bits, tras un tic las páginas valen A = 0110, B = 1001 y C = 0011. ¿Cuál es la víctima?
- C
- B
- A
- Cualquiera de las tres: empatan
Solución
Respuesta: C
El bit de la izquierda es el tic más reciente, así que el registro se lee como un número: A = 6, B = 9, C = 3. Se echa a la de menor valor: C.
¿Qué necesita WSClock para cada página o en total?
- El bit de referencia
- El instante del último uso (U)
- La ventana de tiempo Δ
- El número de veces que se ha escrito
- Un contador de referencias
- El orden de llegada de todas las páginas
Solución
Respuesta: El bit de referencia · El instante del último uso (U) · La ventana de tiempo Δ
WSClock combina el reloj (lista circular y bit R) con el conjunto de trabajo: para cada página guarda cuándo se usó por última vez (U) y la compara con la ventana Δ.
¿Cómo se llama la tendencia de los procesos a concentrar sus accesos en unas pocas zonas de código y datos durante un tiempo?
Solución
Respuesta: Localidad
Localidad (de referencia). Gracias a ella la memoria virtual funciona: en cada momento un proceso solo necesita unas pocas páginas. Ojo, no es «segmentación».
Completa:
Un proceso pasa por distintas ____ mientras se ejecuta. Si la actual está entera en RAM, casi no tendrá ____. Las páginas de su localidad actual forman su ____.
Palabras:
- localidades
- marcos libres
- conjunto de trabajo
- fallos de página
- segmentos
- aciertos de TLB
Solución
Un proceso pasa por distintas localidades mientras se ejecuta. Si la actual está entera en RAM, casi no tendrá fallos de página. Las páginas de su localidad actual forman su conjunto de trabajo.
El conjunto de trabajo (working set) es la forma de medir la localidad actual: las páginas distintas referenciadas en la última ventana Δ.
El reloj virtual vale ahora 50, la ventana es Δ = 8 y una página se usó por última vez en U = 41. ¿Está en el conjunto de trabajo?
- No: 50 − 41 = 9 y 9 > 8
- Sí: 41 < 50
- Sí: 50 − 41 = 9 ≤ 8
- No se puede saber sin el bit M
Solución
Respuesta: No: 50 − 41 = 9 y 9 > 8
Una página está en el WS si reloj − U ≤ Δ. Aquí 50 − 41 = 9 > 8, así que se ha quedado fuera de la ventana.
Completa la definición de hiperpaginación:
La hiperpaginación aparece cuando hay ____ encadenados porque no hay suficientes ____ para todos los procesos; el sistema se arrastra porque se pasa el tiempo ____.
Palabras:
- segmentando
- procesos
- marcos
- paginando
- aciertos
- fallos de página
Solución
La hiperpaginación aparece cuando hay fallos de página encadenados porque no hay suficientes marcos para todos los procesos; el sistema se arrastra porque se pasa el tiempo paginando.
En inglés, thrashing. Cada proceso echa páginas que otro (o él mismo) necesita enseguida; la CPU se queda esperando al disco y su uso cae en picado.
Si se suma el tamaño del conjunto de trabajo de todos los procesos (D) y resulta mayor que el número de marcos disponibles, ¿qué debe hacer el SO?
- Suspender algún proceso y repartir sus marcos
- Admitir más procesos para aprovechar la CPU
- Cambiar FIFO por LRU
- Nada: es lo normal
Solución
Respuesta: Suspender algún proceso y repartir sus marcos
Con D > m la hiperpaginación está garantizada. La salida es bajar el grado de multiprogramación (el planificador a medio plazo suspende procesos) hasta que D quepa.
Con PFF (frecuencia de fallos de página), la tasa de fallos de un proceso baja por debajo del límite inferior. ¿Qué se hace?
- Se le quitan marcos
- Se le dan más marcos
- Se suspende el proceso
- Se cambia su algoritmo de reemplazo
Solución
Respuesta: Se le quitan marcos
PFF fija una banda: por encima del límite superior se le dan marcos; por debajo del inferior se le quitan. Si no hay marcos para dar, se suspende algún proceso.
¿Qué rasgos de un programa suelen aumentar los fallos de página?
- Estructuras enlazadas (listas, árboles) repartidas por la memoria
- Lenguajes interpretados con comprobación de tipos en tiempo de ejecución
- Funciones muy grandes
- Recorrer un array en el orden en que está guardado
- Usar la pila para las variables locales
- Lenguajes compilados con tipos estáticos
Solución
Respuesta: Estructuras enlazadas (listas, árboles) repartidas por la memoria · Lenguajes interpretados con comprobación de tipos en tiempo de ejecución · Funciones muy grandes
Lo que rompe la localidad dispara los fallos: saltar entre nodos enlazados, el código extra de un intérprete o funciones enormes que ocupan muchas páginas. Lo contiguo y lo que se recorre en orden ayuda.
Con la cadena 1, 2, 3, 4, 2, 1, 5 y 3 marcos, ¿cuántos fallos hay como mínimo, use el algoritmo que use?
- 5
- 3
- 7
- 4
Solución
Respuesta: 5
Los fallos obligatorios (primera referencia a cada página) no los evita nadie: aquí 1, 2, 3, 4 y 5 son 5 páginas distintas. Ningún algoritmo, ni el óptimo, baja de ahí.
En una traza con 3 marcos que contienen 4, 8 y 6, llega la página 9. Las próximas referencias son 6, 4, 6, 8. ¿Qué echa el algoritmo óptimo?
- 8
- 6
- 4
- 9
Solución
Respuesta: 8
Se mira hacia delante: 6 vuelve en la posición 1, 4 en la 2 y 8 en la 4. La víctima es la que más tarde vuelve: 8.
Mismos marcos (4, 8, 6). Los últimos usos fueron: 4 en t = 10, 8 en t = 12 y 6 en t = 7. Llega la 9. ¿Qué echa LRU?
- 6
- 8
- 4
- Depende de cuándo entró cada una
Solución
Respuesta: 6
LRU busca el último uso más antiguo: 7 < 10 < 12, así que sale la 6.
Sobre el coste de un fallo de página:
- Leer una página del disco es miles de veces más lento que un acceso a RAM.
- Con una víctima sucia, atender el fallo cuesta dos operaciones de disco.
- Un 1 % de fallos de página apenas se nota en el tiempo efectivo de acceso.
- Para que la memoria virtual no se note, la tasa de fallos tiene que ser diminuta.
Solución
- V — Leer una página del disco es miles de veces más lento que un acceso a RAM.
- V — Con una víctima sucia, atender el fallo cuesta dos operaciones de disco.
- F — Un 1 % de fallos de página apenas se nota en el tiempo efectivo de acceso.
- V — Para que la memoria virtual no se note, la tasa de fallos tiene que ser diminuta.
Con 100 ns por acceso y 8 ms por fallo, un fallo cada 1.000 accesos (0,1 %) ya hace la memoria 81 veces más lenta; un 1 % sería desastroso. Por eso p tiene que ser del orden de uno por millón.
¿Cómo se llama la zona del disco donde el SO guarda las páginas que no caben en la RAM?
Solución
Respuesta: Área de intercambio
El área de intercambio (swap): una partición o un archivo del disco que el SO usa como respaldo de la memoria virtual.
Un proceso tiene 3 marcos y su conjunto de trabajo, en esta fase, tiene 5 páginas. ¿Qué es lo más probable?
- Que falle muchas veces: su localidad no cabe
- Que no falle nunca: LRU lo resuelve
- Que la anomalía de Belady le dé menos fallos
- Que el SO le quite marcos
Solución
Respuesta: Que falle muchas veces: su localidad no cabe
Si |WS| > marcos asignados, el proceso no puede tener su localidad dentro y falla sin parar: es la semilla de la hiperpaginación. Lo razonable sería darle al menos 5 marcos (o suspenderlo).
En las de relacionar, confundir LRU con LFU. LRU mira cuándo se usó por última vez (recently); LFU, cuántas veces se ha usado (frequently).
Trazas y cálculos
Antes de rellenar las tablas, el método que mejor me funciona para no perderme en una traza:
- Escribe la cadena en una fila y debajo una fila por marco.
- En cada referencia, pregúntate primero: ¿está ya en algún marco? Si está, es acierto: copia la columna anterior (y, en LRU, apunta que se acaba de usar).
- Si no está, es fallo. Si queda un marco vacío, va ahí. Si no, aplica la regla del algoritmo: FIFO mira quién entró antes, LRU quién lleva más tiempo sin usarse y el óptimo quién tardará más en volver (mirando hacia delante en la cadena).
- Apunta la víctima debajo de la columna. Al final, cuenta las F: tienen que ser al menos tantas como páginas distintas.
En LRU, ayuda escribir al lado de cada marco el instante de su último uso y tacharlo cada vez que se vuelve a usar. En el óptimo, subraya en la cadena la siguiente aparición de cada página que hay en memoria.
Cinco ejercicios: una cadena con los tres algoritmos, una anomalía de Belady, el tiempo efectivo de acceso con fallos de página y dos de conjunto de trabajo.
onedrive pide sus páginas en este orden: 0, 3, 0, 1, 4, 0, 3, 2, 0, 4, 1, 3, y tiene 3 marcos (vacíos al principio). Para cada algoritmo, calcula los fallos, los aciertos y qué página sale en el primer reemplazo:
| Algoritmo | Fallos | Aciertos | Primera víctima |
|---|---|---|---|
| FIFO | |||
| LRU | |||
| Óptimo |
Solución
| Algoritmo | Fallos | Aciertos | Primera víctima |
|---|---|---|---|
| FIFO | 10 | 2 | 0 |
| LRU | 9 | 3 | 3 |
| Óptimo | 7 | 5 | 1 |
Traza (F = fallo, · = acierto, entre paréntesis la víctima):
FIFO: 0F 3F 0· 1F 4F(0) 0F(3) 3F(1) 2F(4) 0· 4F(0) 1F(3) 3F(2)
LRU: 0F 3F 0· 1F 4F(3) 0· 3F(1) 2F(4) 0· 4F(3) 1F(2) 3F(0)
Óptimo: 0F 3F 0· 1F 4F(1) 0· 3· 2F(3) 0· 4· 1F(0) 3F(1)
El primer reemplazo llega en t = 4 (página 4) con 0, 3 y 1 en memoria. FIFO echa la 0 porque entró la primera, aunque se acaba de usar en t = 2; LRU echa la 3, la que lleva más tiempo sin usarse (t = 1); el óptimo echa la 1, que no vuelve hasta t = 10 (la 0 vuelve en t = 5 y la 3 en t = 6). Los 5 fallos obligatorios (páginas 0, 1, 2, 3 y 4) los tienen los tres.
Con FIFO y la cadena 2, 6, 1, 4, 2, 6, 0, 2, 6, 1, 4, 0, calcula los fallos con 3 y con 4 marcos y di si aparece la anomalía de Belady (escribe sí o no):
| Marcos | Fallos | Aciertos |
|---|---|---|
| 3 | ||
| 4 | ||
| ¿Anomalía de Belady? |
Solución
| Marcos | Fallos | Aciertos |
|---|---|---|
| 3 | 9 | 3 |
| 4 | 10 | 2 |
| ¿Anomalía de Belady? | sí |
Marcas de fallo (F) y acierto (·):
3 marcos: F F F F F F F . . F F . → 9 fallos
4 marcos: F F F F . . F F F F F F → 10 fallos
Con un marco más hay un fallo más: es la anomalía de Belady. Con 4 marcos, FIFO aún tiene dentro 2 y 6 en t = 6 y echa la 2 al llegar la 0 justo antes de que se vuelva a pedir; con 3 marcos ese orden de salidas cambia y acierta la 2 y la 6 en t = 7 y t = 8.
Un acceso a memoria cuesta 100 ns. Atender un fallo cuesta 5 ms si la víctima está limpia y 10 ms si está sucia. Calcula el tiempo efectivo de acceso (en ns) en cada caso y, en el último, cada cuántos accesos puede haber como mucho un fallo para que el TEA no pase de 110 ns (víctimas limpias):
| Caso | Resultado |
|---|---|
| p = 0,001, víctimas limpias (ns) | |
| p = 0,001, la mitad sucias (ns) | |
| p = 0,000001, víctimas limpias (ns) | |
| Accesos por fallo, como mínimo |
Solución
| Caso | Resultado |
|---|---|
| p = 0,001, víctimas limpias (ns) | 5099.9 |
| p = 0,001, la mitad sucias (ns) | 7599.9 |
| p = 0,000001, víctimas limpias (ns) | 105 |
| Accesos por fallo, como mínimo | 499990 |
TEA = (1 − p) · 100 + p · servicio, con todo en ns (5 ms = 5.000.000 ns).
Caso 1: 0,999 · 100 + 0,001 · 5.000.000 = 99,9 + 5.000 = 5.099,9 ns.
Caso 2: si la mitad de las víctimas están sucias, el servicio medio es (5 + 10) / 2 = 7,5 ms: 99,9 + 7.500 = 7.599,9 ns.
Caso 3: 0,999999 · 100 + 0,000001 · 5.000.000 = 99,9999 + 5 ≈ 105 ns.
Caso 4: 100 + p · (5.000.000 − 100) ≤ 110 → p ≤ 10 / 4.999.900, es decir, como mucho un fallo cada 499.990 accesos.
El campus virtual referencia 5, 2, 5, 7, 2, 5, 1, 3, 1, 3, 5, 1 (t = 0, 1, 2…). Con una ventana Δ = 3, calcula |WS| en cada instante. Los demás procesos necesitan entre todos 6 marcos y hay 8 libres: ¿hay hiperpaginación en ese instante? (sí/no)
| t | Referencias en la ventana | |WS| | ¿Hiperpaginación? |
|---|---|---|---|
| 2 | 5, 2, 5 | ||
| 4 | 5, 7, 2 | ||
| 7 | 5, 1, 3 | ||
| 11 | 3, 5, 1 |
Solución
| t | Referencias en la ventana | |WS| | ¿Hiperpaginación? |
|---|---|---|---|
| 2 | 5, 2, 5 | 2 | no |
| 4 | 5, 7, 2 | 3 | sí |
| 7 | 5, 1, 3 | 3 | sí |
| 11 | 3, 5, 1 | 3 | sí |
El conjunto de trabajo son las páginas distintas de las últimas 3 referencias:
WS(t = 2) = {2, 5} → |WS| = 2; D = 2 + 6 = 8 ≤ 8
WS(t = 4) = {2, 5, 7} → |WS| = 3; D = 3 + 6 = 9 > 8
WS(t = 7) = {1, 3, 5} → |WS| = 3; D = 3 + 6 = 9 > 8
WS(t = 11) = {1, 3, 5} → |WS| = 3; D = 3 + 6 = 9 > 8
En t = 2 la página 5 se repite en la ventana (5, 2, 5) y solo cuenta una vez: caben. En los demás instantes D = 9 > 8: no caben todos y hay hiperpaginación.
El reloj virtual de un proceso vale 60 y la ventana es Δ = 10. Para cada página, calcula reloj − U y di si está en el conjunto de trabajo (sí/no):
| Página | Último uso (U) | reloj − U | ¿En el WS? |
|---|---|---|---|
| A | 55 | ||
| B | 49 | ||
| C | 50 | ||
| D | 38 | ||
| E | 60 |
Solución
| Página | Último uso (U) | reloj − U | ¿En el WS? |
|---|---|---|---|
| A | 55 | 5 | sí |
| B | 49 | 11 | no |
| C | 50 | 10 | sí |
| D | 38 | 22 | no |
| E | 60 | 0 | sí |
Una página está en el WS si reloj − U ≤ Δ:
A: 60 − 55 = 5 ≤ 10 → dentro
B: 60 − 49 = 11 > 10 → fuera
C: 60 − 50 = 10 ≤ 10 → dentro
D: 60 − 38 = 22 > 10 → fuera
E: 60 − 60 = 0 ≤ 10 → dentro
La C está justo en el borde (10 ≤ 10) y sí cuenta. B y D son las candidatas a víctima en WSClock.
En el tiempo efectivo de acceso, mezclar unidades. Pasa los milisegundos a nanosegundos (5 ms = 5.000.000 ns) antes de multiplicar por p; si no, el resultado sale mil o un millón de veces más pequeño.
En las tablas de conjunto de trabajo, tacha en la ventana las páginas repetidas antes de contar. |WS| es el número de páginas distintas.
Preguntas de desarrollo
Cuatro preguntas como las que caen en la parte escrita. Escribe tu respuesta en la caja y después despliega la respuesta modelo.
Explica qué es la memoria virtual y en qué consiste la paginación por demanda. ¿Qué gana el sistema con ellas y qué precio paga?
Solución
Respuesta modelo:
La memoria virtual es la técnica que permite ejecutar un proceso aunque no esté entero en la memoria principal: el almacenamiento secundario (el área de intercambio del disco) hace de extensión de la RAM y el SO mueve páginas entre los dos de forma transparente para el programador. Así el espacio lógico de un proceso puede ser mayor que la RAM física y en la memoria caben más procesos a la vez.
La paginación por demanda es la forma habitual de conseguirlo: una página no se lee del disco hasta que el proceso la referencia. La tabla de páginas lleva un bit de validez; si vale i, la MMU lanza un trap (fallo de página) y el SO trae la página en ese momento. Las páginas que nunca se usan no llegan a cargarse.
Lo que se gana: más grado de multiprogramación, arranques más rápidos y programas más grandes que la RAM. El precio: cada fallo de página cuesta milisegundos (miles de veces más que un acceso a RAM), así que la tasa de fallos tiene que ser muy baja, y hace falta un algoritmo de reemplazo cuando no quedan marcos libres.
Lo que se valora:
- Definición: el proceso no tiene que estar entero en RAM y el disco hace de extensión
- Transparente para el programador; espacio lógico mayor que la RAM
- Paginación por demanda: carga perezosa, bit de validez y fallo de página
- Ventajas: más procesos en memoria, arranque rápido
- Coste: el fallo de página es carísimo y obliga a reemplazar páginas
Lo fundamental es separar las dos ideas: la memoria virtual es el objetivo (no tener que caber entero) y la paginación por demanda, el mecanismo (cargar al primer uso).
Describe los pasos que sigue el SO para atender un fallo de página cuando no hay marcos libres. Explica el papel de los bits de validez, de referencia y de modificación.
Solución
Respuesta modelo:
1) El proceso referencia una página cuya entrada tiene el bit de validez a i; la MMU no puede traducir y lanza un trap al núcleo. 2) El SO comprueba que la dirección es legal y localiza la página en el área de intercambio. 3) Como no hay marcos libres, el algoritmo de reemplazo elige una víctima. 4) Si la víctima tiene el bit de modificación a 1, se escribe en el disco; si está a 0, la copia del disco ya vale y no se escribe. 5) Se marca la víctima como inválida en la tabla de páginas de su dueño. 6) Se lee la página nueva en el marco liberado. 7) Se actualiza su entrada (número de marco y bit de validez a v) y se repite la instrucción que falló.
El bit de validez dice si la página está en RAM (es el que provoca el fallo). El de referencia lo pone a 1 el hardware en cada acceso y lo usan las aproximaciones de LRU (reloj, NRU, aging) para saber qué se ha usado hace poco. El de modificación indica si la página se escribió: una víctima sucia cuesta dos operaciones de disco y una limpia, una, por eso los algoritmos prefieren las limpias y el SO practica el precleaning.
Lo que se valora:
- Trap por el bit de validez y comprobación de la referencia
- Elección de víctima por el algoritmo de reemplazo
- Escritura de la víctima solo si M = 1
- Invalidar la víctima, leer la nueva, actualizar la tabla y repetir la instrucción
- Papel de R en las aproximaciones de LRU y de M en el coste
El orden importa: la víctima se guarda (si está sucia) antes de leer la página nueva en su marco, y la instrucción se repite al final, no se continúa.
Compara los algoritmos FIFO, óptimo y LRU. ¿Qué es la anomalía de Belady y a cuál afecta? Explica cómo aproxima el algoritmo del reloj a LRU (puedes usar pseudocódigo).
Solución
Respuesta modelo:
FIFO echa la página que lleva más tiempo en memoria: es fácil (una cola) pero no tiene en cuenta el uso, así que puede echar una página muy usada. El óptimo echa la que más tarde se volverá a referenciar: da el mínimo de fallos posible, pero necesita conocer el futuro y solo sirve como referencia. LRU echa la que hace más tiempo que no se usa: se basa en la localidad (el pasado reciente predice el futuro cercano) y se acerca al óptimo, pero implementarlo exacto exige apuntar algo en cada acceso (contadores o una pila).
La anomalía de Belady es que, al dar más marcos a un proceso, el número de fallos aumente. Le pasa a FIFO; LRU y el óptimo son algoritmos de pila (lo que hay con n marcos está contenido en lo que habría con n + 1) y no la sufren.
El reloj (segunda oportunidad) es FIFO más el bit de referencia. Los marcos forman una lista circular y una aguja los recorre:
mientras true: si R[aguja] == 1 entonces R[aguja] = 0 y aguja = siguiente; si no, víctima = aguja, aguja = siguiente y terminar
Una página usada desde la última pasada se libra una vez; si sigue sin usarse, a la siguiente vuelta cae. Así se parece a LRU usando un solo bit por página.
Lo que se valora:
- Criterio de cada algoritmo (llegada, próximo uso, último uso)
- El óptimo no es implementable; sirve de referencia
- LRU exacto es caro: contadores o pila
- Anomalía de Belady: más marcos, más fallos; afecta a FIFO, no a LRU ni al óptimo
- Reloj: lista circular, bit R, se pone a 0 y se avanza; víctima con R = 0
Un ejemplo numérico ayuda mucho: con la cadena de gcc del artículo y 3 marcos, FIFO da 11 fallos, LRU 9 y el óptimo 7.
Define localidad y conjunto de trabajo. ¿Qué es la hiperpaginación, por qué se produce y cómo puede evitarla el SO?
Solución
Respuesta modelo:
La localidad es la tendencia de un proceso a concentrar, durante un tiempo, sus accesos en unas pocas páginas de código y datos (un bucle, una función, una estructura). El conjunto de trabajo WS(t, Δ) es el conjunto de páginas distintas referenciadas en las últimas Δ referencias: una forma de medir la localidad actual. Con un campo de último uso U, una página está en el WS si reloj − U ≤ Δ.
La hiperpaginación (thrashing) ocurre cuando los procesos no tienen marcos suficientes para su conjunto de trabajo: cada fallo echa una página que se va a necesitar enseguida, los fallos se encadenan, todos esperan al disco y el uso de la CPU se desploma. Suele aparecer al subir demasiado el grado de multiprogramación: si la suma de los |WS| de todos los procesos (D) supera los marcos disponibles, la hiperpaginación es segura.
Para evitarla, el SO puede usar el modelo del conjunto de trabajo (dar a cada proceso al menos |WS| marcos y suspender procesos si D no cabe) o la frecuencia de fallos de página (PFF): si la tasa de fallos de un proceso supera un límite superior se le dan marcos, si baja de un límite inferior se le quitan y, si no hay marcos que dar, se suspende algún proceso.
Lo que se valora:
- Localidad bien definida
- Conjunto de trabajo con la ventana Δ (y reloj − U ≤ Δ)
- Hiperpaginación: fallos encadenados por falta de marcos y CPU ociosa
- Causa: grado de multiprogramación alto, D > marcos
- Soluciones: modelo del WS, PFF con sus dos límites, suspender procesos
La clave es la relación: localidad → conjunto de trabajo → si no cabe, hiperpaginación. Con eso, las soluciones salen solas.
Todo el tema en un dibujo
Si solo tienes un minuto antes de entrar al examen, mira esto:
Las seis tarjetas siguen el orden del tema: la memoria virtual provoca los fallos de página, los fallos obligan a reemplazar páginas, el reemplazo exacto (LRU) se aproxima con el bit R, y todo funciona mientras los conjuntos de trabajo quepan; cuando no caben, aparece la hiperpaginación.
Chuletario: memoria virtual
Lo esencial en 30 segundos
- Memoria virtual: el proceso no tiene que estar entero en RAM; el resto, en el área de intercambio (swap).
- Paginación por demanda: una página se lee la primera vez que se pide (bit de validez a i → fallo de página).
- Fallo de página: trap → comprobar → (víctima, escribirla si M = 1) → leer → v = 1 → repetir la instrucción.
- FIFO la más antigua · óptimo la que más tarde vuelve · LRU la que lleva más tiempo sin usarse.
- Belady: con FIFO, más marcos pueden dar más fallos. LRU y el óptimo no la sufren.
- WS(t, Δ): páginas distintas de las últimas Δ referencias; dentro si reloj − U ≤ Δ.
- Hiperpaginación: Σ |WS| > marcos → fallos encadenados, CPU parada. Solución: WS, PFF o suspender procesos.
Quiero… / Cómo / Resultado
| Quiero… | Cómo | Resultado |
|---|---|---|
| saber si una página está en RAM | bit de validez de su entrada | v = en RAM; i = en disco (fallo) |
| saber si hay que escribir la víctima | bit M | M = 1 → 2 E/S; M = 0 → 1 E/S |
| el tiempo efectivo de acceso | (1 − p) · acceso + p · servicio, todo en ns | 100 ns, 8 ms, p = 0,001 → 8.099,9 ns |
| el mínimo de fallos posible | número de páginas distintas de la cadena | fallos obligatorios |
| la víctima de FIFO | la que entró antes | sale aunque se use mucho |
| la víctima de LRU | el último uso más antiguo | se basa en el pasado reciente |
| la víctima del óptimo | la siguiente aparición más lejana (o ninguna) | menos fallos que nadie; no implementable |
| la víctima del reloj | primera con R = 0; a las de R = 1 se les pone 0 | segunda oportunidad |
| la víctima de NRU | clase no vacía más baja: (R, M) = (0,0) < (0,1) < (1,0) < (1,1) | al azar dentro de la clase |
| la víctima de aging | registro desplazado a la derecha con R por la izquierda | la de menor valor |
| saber si una página está en el WS | reloj − U ≤ Δ | sí / no |
| detectar hiperpaginación | D = Σ |WS| frente a marcos libres | D > marcos → hiperpaginación |
| ajustar marcos con PFF | tasa de fallos frente a los dos límites | por encima: dar marcos; por debajo: quitar |
Plantillas de los ejercicios
Traza (FIFO, 3 marcos) — la primera parte de la cadena de onedrive del cuestionario:
| ref | 0 | 3 | 0 | 1 | 4 | 0 |
|---|---|---|---|---|---|---|
| marco A | 0 | 0 | 0 | 0 | 4 | 4 |
| marco B | 3 | 3 | 3 | 3 | 0 | |
| marco C | 1 | 1 | 1 | |||
| ¿fallo? | F | F | · | F | F | F |
| sale | 0 | 3 |
Tiempo efectivo: TEA = 0,999 · 100 + 0,001 · 5.000.000 = 99,9 + 5.000 = 5.099,9 ns.
Conjunto de trabajo (Δ = 3): ventana 5, 2, 5 → WS = {2, 5} → |WS| = 2 (el 5 cuenta una vez).
Reloj − U: reloj = 60, Δ = 10, U = 50 → 60 − 50 = 10 ≤ 10 → dentro (el borde cuenta).
Síntoma / Causa probable
| Síntoma | Causa probable |
|---|---|
| Me salen menos fallos que páginas distintas | no has contado los fallos obligatorios (marcos vacíos) |
| Mi FIFO y mi LRU dan lo mismo en todo | en LRU no estás actualizando el último uso en los aciertos |
| El TEA me sale de pocos nanosegundos con p = 0,001 | no pasaste los ms a ns |
| Con más marcos me salen más fallos | si es FIFO, puede ser la anomalía de Belady (no es un error) |
| Mi |WS| es mayor que Δ | estás contando páginas repetidas: el WS es un conjunto |
| En el óptimo dudo entre dos víctimas | las dos no vuelven: empate, vale cualquiera (dilo en el examen) |
| Todo va lento con la CPU casi parada | hiperpaginación: Σ |WS| no cabe en la RAM |
Antes de entregar, pregúntate
- ¿He contado como fallo cada primera referencia, aunque hubiera marcos vacíos?
- ¿He aplicado la regla del algoritmo que pide el enunciado (llegada, último uso o próximo uso) y no otra?
- ¿Están todas las unidades en lo mismo (ns o ms) antes de calcular el TEA?
- En el conjunto de trabajo, ¿he contado páginas distintas y he usado ≤ (no <) con Δ?
Con esto cierras el Tema 5 de IC2, la memoria. El siguiente, y último de la teoría de IC2, son los archivos: cómo se organizan, cómo se accede a ellos y cómo se reparte el espacio del disco. ¡Nos vemos allí!
Sigue aprendiendoTodos los artículos de Sistemas operativos¿Te ha servido este artículo? Así puedes apoyar SergioLearns →
¿Listo para el examen?Simulacro del examen de teoría de IC2 — primer parcial, segundo parcial o convocatoria, con tu nota real y el repaso de cada fallo (como si estuvieras en el aula)
