1 Paginamiento / Paging Sistemas Operativos 16 de Septiembre de 2011

2 ¿Qué es? ● Una forma de implementar memoria virtual ● ¿LA forma de implementar memoria virtual? ● Todos los sistemas operativos modernos usan paginamiento ● Hardware dedicado

3 ¿Cómo se hace? ● Elegimos un tamaño p = 2 N ● Dividimos la memoria virtual en bloques de tamaño p llamados páginas (pages) ● Dividimos la memoria física en bloques de tamaño p llamados marcos de página (page frames) donde ponemos el contenido de las páginas ● Usamos una tabla de páginas (page table) para convertir direcciones de página (virtuales) en direcciones de marcos de página (físicas) ● Si no entran más páginas en memoria, hacemos lugar escribiendo algunas a disco

4 Ejemplo ● p = 4KB = 2 12 ● Memoria virtual = 64KB = 2 16 ● Memoria física = 32KB = 2 15

5 La búsqueda MOV 14000, REG ● Busco el marco correspondiente a la página 0011 ● Reemplazo la página por el marco ● Devuelvo lo que hay en esa dirección de memoria (26288)

6 Swapping ● Si me quedo sin memoria, mando páginas al disco ● Bit de presencia/ausencia ● Cuando se intenta usar una página ausente, se genera un fallo de página (page fault) 1. Libero un marco (¿Cuál? Próxima clase) 2. Traigo la página a memoria 3. Actualizo la tabla ● Optimización: Si no modifiqué una página que traje de disco, no necesito escribirla para liberarla ● Bit de modificación (dirty bit)

7 Tabla de páginas

8 Ventajas del paginamiento ● Es simple ● Pocos problemas de fragmentación ● Un bloque de memoria grande se divide en páginas no necesariamente contíguas en memoria física ● Baja sobreutilización ● A lo sumo se desperdician p – 1 bytes ● Flexible para swapping

9 Velocidad ● Todo esto se repite en cada acceso a memoria ● MMU (memory management unit) ● Transparente para el resto del sistema ● Excepción en caso de fallo de página ● ¡Por cada acceso necesito una lectura extra! ● Localidad espacial y temporal en los accesos ● TLB (translation lookaside buffer)

10 TLB ● Memoria asociativa muy rápida ● Similar a un diccionario ● Entradas: Indice de página + datos de la tabla de páginas ● Busca en todos los elementos simultáneamente ● Si está no necesito revisar la tabla (TLB hit) ● Si no está (TLB miss / soft miss) ● Leo de la tabla como antes ● t (TLB hit) < t (TLB miss)

11 ¡No escala! ● Hoy: ● Páginas de 4KB ● TLB multinivel de 64 + 512 entradas ● Memoria física de 2 40 bytes = 1 TB ● Memoria virtual de 2 48 bytes = 256 TB ● Con 4 bytes por entrada en la tabla, serían 64 GB por proceso! ● Soluciones ● Paginamiento multinivel (multilevel paging) ● Tabla de páginas invertida (inverted page table)

12 Tabla de páginas invertida ● La tabla va de cada marco de página a una lista de todas las páginas que usan ese marco ● Una sola tabla para todo el SO ● No sirve para la búsqueda ● La búsqueda se hace a través de una tabla hash de páginas a marcos ● Búsquedas caras ● Depende mucho de la performance del TLB

13 Paginamiento multinivel ● Los programas no usan todo el espacio de memoria virtual ● Divido la tabla en un árbol de tablas menores ● Los TLB misses son más caros ● Actualmente hasta 4 niveles

14 Paginamiento multinivel Página: 2 12 bytes Memoria virtual: 2 32 bytes 1 nivel: 2 20 = 1M 2 niveles: 4 x 2 10 = 4096