Antes de empezar
- Qué es un proceso (lección Procesos y sus estados).
- Leer números en binario. Basta con saber que los últimos 4 bits de un número son su resto al dividir entre 16.
Teoría
Toda dirección que usa un programa es virtual. El sistema operativo y el hardware la traducen a una dirección física en la RAM.
La memoria se corta en bloques del mismo tamaño: páginas en la memoria virtual y marcos en la física. Aquí miden 16 bytes; en los sistemas reales, 4 KiB.
Una dirección virtual se parte en dos:
- Número de página = dirección ÷ tamaño de página (división entera).
- Desplazamiento = el resto.
Con páginas de 16 bytes, el desplazamiento son los 4 bits de la derecha y el número de página el resto. Por ejemplo, 70 = 100 0110: página 4 (100), desplazamiento 6 (0110).
La tabla de páginas dice dónde está cada página: en un marco, en disco (es válida pero no está cargada) o inválida (no forma parte del programa). La dirección física es marco × tamaño de página + desplazamiento. El desplazamiento nunca cambia.
La TLB es una caché diminuta y rápida, dentro de la CPU, con las traducciones recientes (página → marco). Si la página está ahí (acierto), no hace falta leer la tabla de páginas. Si no (fallo de TLB), se lee la tabla y se guarda la traducción; si la TLB está llena, se olvida la que lleva más tiempo sin usarse.
Un fallo de página ocurre cuando la página es válida pero está en disco: el sistema operativo la carga en un marco libre, actualiza la tabla y el acceso se repite. Es lento, pero normal. Si la página es inválida, el sistema termina el proceso (violación de segmento).
Costos en este simulador: TLB 1, memoria 100, fallo de página 10 000 unidades de tiempo.
Predecir
El tablero empieza con Recorrido: páginas de 16 bytes, 8 páginas virtuales, 4 marcos y una TLB de 2 entradas, vacía al empezar. El marco 1 está libre.
| Página | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|---|
| Dónde está | marco 2 | marco 0 | disco | marco 3 | disco | inválida | inválida | disco |
El programa accede a las direcciones 20, 25, 70, 23, 3 y 90. ¿Qué pasa en cada acceso? Acierto en la TLB, fallo de TLB con la página en memoria, fallo de página o página inválida. Responde en el panel Tu predicción antes de ejecutar.
Ejecutar
Accesos del programa
Direcciones virtuales en decimal, en el orden en que el programa las usa. Páginas de 16 bytes: 8 páginas virtuales y 4 marcos físicos.
Entradas de la TLB
Con 0 no hay TLB: cada acceso lee la tabla de páginas.
Costos: TLB 1, memoria 100, fallo de página 10 000 unidades.
Tu predicción
¿Qué pasa en cada acceso? Elige una opción por fila.
- 20
- 25
- 70
- 23
- 3
- 90
El tablero antes de empezar
Cada acceso: TLB, después tabla de páginas, después disco si hace falta.
Traducción
Pulsa Ejecutar para traducir el primer acceso.
TLB
Arriba, la usada hace más tiempo: sale la primera.
- Vacía
- Vacía
Tabla de páginas
| Página | Dónde está |
|---|---|
| marco 2 | |
| marco 0 | |
| disco | |
| marco 3 | |
| disco | |
| 5 | inválida |
| 6 | inválida |
| disco |
Memoria física
- Marco 0
- Marco 1 libre
- Marco 2
- Marco 3
Disco
Qué pasó en este turno
Pulsa Ejecutar o avanza acceso a acceso. Aquí verás cada paso de la traducción.
Accesos
| # | Virtual | Página | Despl. | Resultado | Física | Costo |
|---|
Mientras avanza, fíjate en cuatro momentos:
- Acceso 1 (20): ¿qué parte de la dirección cambia al traducirla?
- Acceso 3 (70): ¿cuánto cuesta comparado con los demás?
- Acceso 5 (3): la TLB está llena. ¿Qué sale de la TLB? ¿Sale también de la memoria?
- Acceso 6 (90): ¿por qué este no se resuelve cargando la página?
Debajo del tablero, la tabla de accesos suma el costo de cada uno.
Explicar
Esta etapa se abre cuando ejecutas la simulación hasta el final.
Ir a la simulaciónLo correcto era: fallo de TLB, acierto, fallo de página, acierto, fallo de TLB y página inválida.
Un fallo de página no es un error. La tabla de páginas distingue «en disco» de «inválida». La página 4 está en disco: el sistema operativo la carga en el marco libre y el acceso termina en la dirección física 22. La página 5 no pertenece al programa: eso sí es un error, y Linux envía la señal SIGSEGV. Los fallos de página son la forma normal de cargar páginas cuando se necesitan (paginación bajo demanda); un programa puede tener miles por segundo.
Para qué sirve la TLB. Sin ella, cada acceso necesita al menos dos lecturas de memoria: la tabla de páginas y el dato. Los accesos 2 y 4 están en la página 1, que ya estaba en la TLB desde el acceso 1, así que se saltan la tabla. Las TLB reales tienen desde decenas hasta unos pocos miles de entradas y aciertan más del 99 % de las veces, porque los programas reutilizan direcciones cercanas (localidad).
Solo se traduce el número de página. Los bits del desplazamiento pasan tal cual: 20 = página 1, desplazamiento 4, y la física es 0 × 16 + 4 = 4. Por eso el tamaño de página es una potencia de 2.
Cualquier página en cualquier marco. La página 0 está en el marco 2 y la página 1 en el marco 0. La memoria virtual contigua no necesita memoria física contigua, y así desaparece la fragmentación externa.
Los fallos de página dominan el costo. El recorrido cuesta 201 + 101 + 10 201 + 101 + 201 + 101 = 10 906 unidades, y el acceso con el fallo de página es el 94 % de ese total. En una máquina real, la TLB responde en torno a 1 ns, la DRAM en unos 100 ns, y un fallo de página servido desde un SSD tarda decenas o cientos de microsegundos; desde un disco duro, milisegundos.
Sacar una página de la memoria. Si no hay marcos libres, el sistema saca una página al disco (aquí, la que se cargó primero; la siguiente lección compara mejores elecciones). Su entrada en la tabla vuelve a decir «disco», y su entrada en la TLB debe borrarse: si no, la TLB traduciría a un marco que ahora tiene otra página. La página no se pierde: el siguiente acceso a ella será un fallo de página.
Tablas de páginas reales. Con páginas de 4 KiB y direcciones de 48 bits, una tabla plana necesitaría 2³⁶ entradas por proceso. x86-64 usa un árbol de 4 niveles (5 niveles y direcciones de 57 bits en procesadores recientes con LA57), así que un fallo de TLB puede recorrer 4 o 5 niveles. Las páginas grandes (2 MiB, 1 GiB) permiten que una sola entrada de TLB cubra mucha más memoria, y las entradas llevan un identificador del espacio de direcciones (PCID) para no vaciar la TLB en cada cambio de contexto.
Experimentar
Esta etapa se abre cuando ejecutas la simulación hasta el final.
Ir a la simulaciónUsa el tablero para resolver estos retos. Cada uno tiene una solución posible al desplegarlo.
1. Haz que Recorrido cueste más sin cambiar los accesos.
Pon la TLB en 0 entradas: el total sube a 11 100. Cada acceso lee ahora la tabla de páginas, así que los que antes acertaban en la TLB pasan de costar 101 a costar 200.
2. Consigue cuatro aciertos de TLB en seis accesos.
Accesos 20, 25, 23, 30, 3 y 6, con TLB de 2 entradas: aciertan el 2, el 3, el 4 y el 6. Todos caen en la página 1 o en la 0: cada página falla una vez y después acierta.
3. Haz que una página vuelva del disco después de haber salido.
Carga Memoria llena. No hay marcos libres, así que en el acceso 2 la página 0 sale al disco y la TLB la olvida. En el acceso 5 el programa vuelve a pedirla y hay otro fallo de página.
4. Haz que la simulación se detenga en el primer acceso.
Pon como primer acceso la dirección 100: página 6, inválida. No hay nada que cargar; el proceso termina.
Comprobar
Esta etapa se abre cuando ejecutas la simulación hasta el final.
Ir a la simulaciónProfundizar
- Tablas de varios niveles a mano, y tablas de páginas invertidas.
- Copia en escritura y archivos proyectados en memoria. Después de
fork(), padre e hijo comparten páginas hasta que uno escribe;mmapcarga un archivo con fallos de página. - Fallos menores y mayores. Un fallo menor encuentra la página ya en memoria (por ejemplo, compartida); uno mayor la lee del disco.
/usr/bin/time -vyperf stat -e page-faultslos cuentan. - Invalidaciones de TLB en varios núcleos. Cuando una página deja de estar en memoria, cada núcleo que la tenga en su TLB debe olvidarla.
Para leer más:
- Arpaci-Dusseau y Arpaci-Dusseau, Operating Systems: Three Easy Pieces, caps. 18 a 21. Gratis en línea.
- Silberschatz, Galvin y Gagne, Operating System Concepts, 10.ª ed., secciones 9.3 y 10.2.
- Documentación del núcleo Linux, 5-level paging: docs.kernel.org.