Soporte HW para
Administración de Memoria
Cecilia Hernández
2007-1
Paginación
dirección virtual
npv
offset
Marco Pag 0
Marco Pag 1
nmp
nmp
npv: Num. página virtual
nmp: Num. marco página
offset
dirección física
Marco Pág 2
Marco Pag 3
Marco Pag 4
.
.
.
Marco Pag
N
Cada Proceso tiene su propia tabla de página
Fallos de Páginas

Interrupción (por fallo de página) hace que SO se
ejecute


SO salva estado de proceso en ejecución y salta a
rutina de interrupción para atender fallo
Encuentra un marco de lista libre o reemplazada de
proceso (mismo u otro)


Encuentra en disco página de proceso que necesita
cargarse en memoria (*)


Bloquea proceso y ejecuta otro entre tanto
Cuando E/S terminan


Si se requiere E/S (acceso a disco) bloquea proceso
y ejecuta otro
Setea entrada de página con marco, V=1, R = 1 y
M =0 y bits protección apropiados
Pone proceso en cola de listos
Página de disco a memoria





SO sabe id de proceso responsable de fallo de
página y dirección virtual que produce fallo
Id de proceso almacenado en PCB
PCB proceso tiene puntero a tabla de página
Dirección virtual contiene número página virtual
que produce fallo
SO tiene estructura de datos similar a tabla de
página que contiene direcciones a disco de
páginas

Un arreglo con entradas por cada página en el
espacio de direccionamiento
Problemas con paginación

Accesos a memoria para direccionar memoria física

2 referencias a memoria por traducción


Solución


A tabla de página y memoria
Usar cache para almacenar tabla de página (TLB:
Translation lookaside buffer)
Requerimiento de memoria


Una entrada por página virtual
En arquitectura de 32 bits y páginas de 4KB



Número de páginas virtuales 220 = 1.048.576 de
entradas en tabla de páginas
4 bytes por entrada = 4* 1.048.576 = 4MB
Cada proceso tiene su propia tabla de página


Para 50 procesos 50 *4MB = 200 MB sólo para almacenar
tablas de páginas
Solución

Paginar tablas de páginas
Paginando tablas de página

Observación

Procesos en ejecución sólo necesitan una
porción del espacio de direccionamiento en
memoria
 Idea de conjunto de trabajo expuesta por
proceso de acuerdo a localidad
 Puede que proceso no use su espacio
completo de direccionamiento 32/64 bits
 Proceso puede que no referencie algunas
partes de direccionamiento nunca

Caso de rutinas de manejo de errores, si proceso
no expone errores en tiempo de ejecución
Tablas de páginas de 2 niveles
dirección virtual
npv1
npv2
offset
Marco Pag 0
Marco Pag 1
nmp
nmp
offset
dirección física
Marco Pág 2
Marco Pag 3
Marco Pag 4
.
.
.
Marco Pag N
Cada Proceso tiene sus propias tablas de página
npv1: Num. página virtual a nivel 1
npv2: Num. página virtual a nivel 2
nmp: Num. marco página
Ejemplo

Espacio de direccionamiento de 32 bits,
páginas de 4KB, cada entrada en tabla de
páginas de 4 bytes

Bits para offset?
 Se necesitan 12 bits para direccionar 4KB


212 = 4KB
Si tabla de primer nivel debe estar contenida en
una página
 Distribución de campos en dirección virtual?

4KB/4 = 1KB = 1024 entradas en tabla primer nivel
 10 bits 210 = 1024
 1024 tablas de segundo nivel
 Si se usan los 32 bits, se requieren 32 -10 -12
= 10 bits para índices a tablas de segundo
nivel, luego cada tabla de segundo nivel
tambien es contenida en 1 página
Generalización





En un principio arquitecturas
usaban tablas de 1 nivel
VAX, P-II tablas de 2 niveles
SPARC usa tres niveles
68030 usa cuatro niveles
Tabla de nivel inferior debe contener
información de marcos de página
Otros esquemas

Tabla de página es tabla hash



Esquema útil para espacios de
direccionamiento grandes (64 bits) y evitar
tabla de páginas muy grandes
Número de página se usa como hash
Para manejar colisiones
 Cada entrada en la tabla hash contiene una
lista enlazada de elementos
 Cada elemento en la lista enlazada contiene el
número de página virtual, la entrada en la
tabla de página y el puntero a siguiente
elemento en la lista
Tabla de páginas como tabla hash
dirección virtual
p
offset
Marco Pag 0
Marco Pag 1
hash
m2
offset
dirección física
a m1
p: Num. página virtual
nmp: Num. marco página
p m2
Marco Pág 2
Marco Pag 3
Marco Pag 4
.
.
.
Marco Pag N
Cada Proceso tiene su propia tabla de página
Otros esquemas

Tabla de página invertida




Para evitar usar mucha memoria para tablas de página
Tabla tiene una entrada por cada marco de página
Cada entrada contiene la página virtual almacenada en
el marco de página
Sólo se necesita una tabla en el sistema


Para identificar páginas virtuales de procesos cada
entrada tambien tiene pid de proceso



No una por proceso
Luega cada entreda contiene pid y página virtual
PowerPC y UltraSPARC usan este esquema
Uso de memoria menora para almacenar tabla de
página, pero búsqueda puede ser lenta
 Para mejorar búsqueda se usa tabla de página usando

hash
Luego, cada traducción requiere 2 referencias a
memoria una para hash y otra para tabla invertida
Tabla de página invertida
dirección virtual
pid
p
offset
Marco Pag 0
Marco Pag 1
m
m
pid p
búsqueda
offset
dirección física
Marco Pág 2
Marco Pag 3
Marco Pag 4
.
.
.
Marco Pag N
Una tabla de página en el SO para todos los procesos
Mejorando desempeño con TLB

Tablas de páginas de un nivel


Tablas de páginas de 2 niveles


2 referencias para acceso a información
3 referencias para acceso a información
Como hacer para que sobrecarga de
traducción sea mínima



Usar TLB cache dentro de CPU
Traducción de dirección virtual a física en
Hardware
TLB manejada por MMU (Memory Management
Unit)
 MMU encargada de traducción virtual a física
TLB

Traduce páginas virtuales a marcos



Acceso para extraer marco de página
Puede realizarlo en un ciclo de reloj
TLB implementada en HW



Cache completamente asociativa (todas las entradas
accesadas paralelamente)
Tags en cache son los números de páginas virtuales
Datos en cache son los marcos de página

Marco de página mas offset dirección física


MMU puede calcular dirección física
TLB explota localidad

Procesos contienen conjunto de paginas en conjunto de
trabajo


Típicamente TLB contiene entre 16-48 entradas (64-192 KB)
Aciertos en TLB son muy importantes

Costos de fallos hacen traducción virtual a física muy cara
Ilustración con TLB
dirección virtual
numero pag
offset
Tag
Datos
numero pag numero marco
numero marcooffset
TLB hit
=
dirección física
TLB
Memoria Física
numero pag
numero marco
TLB miss
Tabla de página
Manejando TLBs

La idea es que la traducción virtual a física sea
realizada por la TLB la mayoría de las veces



Típicamente aciertos son > 99%
En caso de fallo, MMU va a tabla de página y extrae
marco para página virtual y lo pone en la TLB
MMU

Sabe donde están las tablas de página en memoria




OS las mantiene y HW de MMU las accesa directamente
Formato de tablas de página debe ser definido en HW
Así se hace en arquitecturas x86
TLB cargada por software


Fallo en TLB capturado por SO, SO encuentra marco para
página virtual y lo carga en TLB
Debe ser rápido, pero normalmente toma entre 20-200
ciclos de reloj



ISA de la CPU tiene instrucciones para manipular la TLB
SO decide el formato de la tabla de página
MIPS3000
Manejando TLBs

SO debe asegurar consistencia entre TLB y tabla de
página


Cuando SO cambia bits de protección en entrada de tabla
de página debe invalidar entrada en TLB si es que
tambien esta ahí
Qué ocurre en cambio de contexto?


Cada proceso tiene sus propias tablas de página
Luego SO necesita invalidar todas las entradas en la TLB


Una de las principales fuentes de sobrecarga en cambio de
contexto
Cuando hay un fallo en TLB y TLB esta completamente
ocupada hay que elegir una reemplazo, dado que se
necesita cargar una nueva


Luego, debe haber un algoritmo de reeplazo en la TLB
Normalmente LRU implementado en HW
Implementaciones con paginación

Memoria compartida

Dos procesos pueden compartir memoria física



Cada proceso tiene su tabla de página, con números
de página virtual correspondientes a cada proceso.


Leer/escribir en un espacio compartido
Ejecutar código perteneciente a una biblioteca
Mismo marco en entradas de cada tabla de página
Copy-on-write (COW)

Para caso fork(), en lugar de copiar espacio de
direccionamiento, hacer que hijo comparta lo del
padre hasta que hijo escriba


Hacer que hijo solo pueda leer
Cuando hijo quiere escribir, SO atiende SO asigna
un nuevo marco al hijo y lo mapea en su tabla de
página y luego lo resume
Implementaciones con paginación

Archivos mapeados a memoria



En lugar de usar llamadas a sistema open,
read, write, close
 Mapear archivo a espacio de direccionamiento
virtual
 Inicialmente todas las páginas en región
mapeadas están inválidas
SO lee una página de archivo de disco cuando
accesa a página inválida
SO escribe una página a archivo cuando es
reemplazada y su bit M (dirty bit)
Resumen

Traducción de memoria virtual a física

Usa TLB, tablas de páginas de múltiples niveles
(normalmente en HW : MMU)

Cuando hay fallos en TLB se accesa memoria
conteniendo tabla de página


Si págino no esta en tabla de página : Fallo de página
SO Maneja fallos de página
 Salva estado de proceso y lo bloquea




Ejecuta algoritmo de reemplazamiento cuando se
ve escaso de marcos libres
Encuentra marco libre, trae lo que necesita de
disco y lo copia en marco
Actualiza entrada en tabla de página
Pone proceso en cola de listos
Resumen

Dos problemas en traducción

Desempeño
Ciclos requerido por traducción
 Solución: usar TLB


Cantidad de memoria para contener
tabla de página por procesos

Tablas de múltiples niveles


Esto hace uso de TLB más importante porque
costo de fallos incrementa
Tablas invertidas con uso de tablas hash
Detalles de TLB

Implementado en HW

Cache completamente asociativa





TLBs son pequeñas entre 16 y 64 entradas


Todas las entradas accesadas en paralelo en búsqueda de marco
para cada traducción
Tag en TLB corresponden a número de página virtual
Datos en TLB corresponden a marcos de página
Con marco y offset MMU puede directamente calcular dirección
física
AMD operon tiene 2 niveles de TLB
Para traducción de dir virtual a física son accesadas antes
de acceso a tabla de página



Acierto. Marco de página se encuentra en TLB para página
virtual referenciada por CPU
Fallo. Traducción requiere acceso a tabla de página, trae marco
a entrada en TLB (si es necesario saca otra, normalmente
algoritmo LRU)
En Cambio de contexto: Entradas en TLB son invalidadas porque
referencias pertenecen a proceso que sale de CPU
Descargar

Document