Organización del Computador I Verano

Memoria Virtual Basado en el capítulo 5 del libro de Patterson y Hennessy

Verano 2014

Profesora Borensztejn

Memoria Virtual •  Memoria Virtual es la técnica que permite que un

programa (y sus datos) no necesite estar completo en memoria para ejecutarse.

•  Esto es necesario por dos motivos: –  Los programas suelen ser muy grandes y no caben

enteros en memoria física. –  En un sistema multiusuario/multitarea, varios

programas comparten la misma CPU: es necesario que todos ellos esten en memoria física al mismo tiempo, y obviamente, no caben.

Memoria Virtual •  Solución:

–  Todos los programas que están ejecutándose en un momento determinado del tiempo, están en disco. Sólo sus partes actualmente accedidas están en memoria principal.

–  La memoria principal actúa como una caché del disco donde están los programas completos que se están ejecutando.

–  La técnica de memoria virtual ofrece además, un mecanismo de protección entre programas: asegura que ningún programa lee/escribe los datos de otro programa

Espacios de Direcciones •  La memoria física tiene un espacio de direcciones igual a

2n bytes, siendo n el número de bits (señales) que el procesador tiene para direccionar memoria. La memoria física (DRAM) se accede con direcciones físicas.

•  La memoria virtual tiene un espacio de direcciones igual a 2m, siendo m la cantidad de bits que los programas utilizan para especificar una dirección (de una instrucción o de un dato). Estas direcciones se llaman direcciones virtuales.

Memoria virtual

Memoria física (DRAM)

dirección virtual

dirección física

Espacios de Direcciones

•  Cuando un programa es compilado, sus direcciones son direcciones del espacio virtual.

•  Cuando un programa es ejecutado, las direcciones con las que se accede a memoria son direcciones del espacio físico.

•  En el medio, debe haber un proceso que traduzca una dirección virtual a una dirección física.

•  El proceso de traducción permite que un programa cambie muchas veces su mapeo entre dirección virtual y dirección física durante su ejecución.

•  La técnica de memoria virtual la implementa: –  El sistema operativo con soporte de hardware –  La traducción de direcciones virtuales a físicas, la realiza el

hardware (en casi todos los procesadores actuales)

Memoria Virtual

P h y s i c a l a d d r e s s e s

D i s k a d d r e s s e s

V i r t u a l a d d r e s s e s A d d r e s s t r a n s l a t i o n •  La unidad (bloque)

de transferencia se llama página.

•  Fallo: Fallo de página (Page Fault)

•  El mapeo se realiza entre las páginas de memoria virtual y las páginas de memoria física.

Traducción •  Una dirección de memoria virtual se compone

de: –  Número de página –  Offset dentro de la página

•  La función de traducción asigna un número de página física a la página virtual.

•  La traducción se realiza cada vez que se accede a un dato.

3 2 1 011 10 9 815 14 13 1231 30 29 28 27

Page offsetVirtual page number

Virtual address

3 2 1 011 10 9 815 14 13 1229 28 27

Page offsetPhysical page number

Physical address

Translation

Páginas

•  Cuando la función de traducción encuentra que no hay mapeo para una dirección virtualèfallo de página

•  El fallo de página tiene una penalización enorme: acceder al disco cuesta millones de ciclos de proceso

•  Los sistemas de memoria virtual se diseñan de forma de reducir esta penalización.

Páginas

–  Las páginas deben ser lo suficientemente grandes para amortizar el tiempo de acceso: de 4KB, 16KB, 32KB y 64 KB.

–  Se usa un esquema totalmente asociativo para colocar las páginas en memoria.

–  El software gestiona los fallos de página: el hardware avisa que hay fallo, el SO toma el control, transfiere la página y utiliza algún algoritmo para decidir a quien reemplaza.

–  Cuando se escribe en memoria principal, no se actualiza el disco: se utiliza la política de escritura diferida. El disco se actualiza cuando la página se elimina de memoria.

Como ubicar y encontrar una página

•  SO gestiona la localización de las páginas: – Algoritmos sofisticados que llevan la cuenta de

las páginas que no se necesitarán por mucho tiempoè totalmente asociativo

– Dificultad: localizar la página. Una búsqueda total es impracticable.

– Se utiliza una Tabla de Páginas.

Tablas de Página Physical memory

Disk storage

Valid

111101101101

Page table

Virtual page number

Physical page or disk address •  Tabla de Páginas

reside en Memoria •  Se indexa con el

número de página virtual.

•  Contiene el número de página física o bien una indicación de que no está.

•  Cada programa tiene su propia Tabla de Páginas. •  Un registro del

procesador apunta a la dirección en memoria de la Tabla de Páginas

Tabla de Páginas

Page offsetVirtual page number

Virtual address

Page offsetPhysical page number

Physical address

Physical page numberValid

If 0 then page is not present in memory

Page table register

Page table

20 12

18

31 30 29 28 27 15 14 13 12 11 10 9 8 3 2 1 0

29 28 27 15 14 13 12 11 10 9 8 3 2 1 0

•  Tamaño de página: 212 bytes (4K bytes)

•  Espacio virtual de direcciones: 232 bytes

•  Espacio físico de direcciones: 230 bytes

•  Tamaño de la Tabla de Páginas: 220

entradas, de 19 bits. •  O sea: un millón de

entradas de 32 bits (redondeando para hacer mas fácil el acceso)

Programas y Procesos •  La Tabla de Páginas, junto con el PC y los

registros representan el estado del programa que se está ejecutando.

•  La Tabla de Páginas define el estado de la memoria del programa.

•  Si se quiere compartir la CPU, se deberá salvar el estado del programa.

•  El programa y su estado se denomina proceso. •  Un proceso está activo si está en posesión de la

CPU : de lo contrario está inactivo. •  El S.O es el que pasa los procesos del estado

inactivo a activo y viceversa

¿Donde está la página en disco? •  Un fallo de página

provoca una excepción que le da control al S.O

•  Este debe localizar el lugar del disco donde se encuentra la página que falló.

•  Utiliza una estructura similar a la Tabla de Páginas, o bien la misma Tabla de Páginas para almacenar la ubicaciónde la página en disco.

Physical memory

Disk storage

Valid

111101101101

Page table

Virtual page number

Physical page or disk address

•  El S.O también tiene una tabla por proceso donde guarda información de sus páginas mapeadas.

•  Reemplaza, utilizando LRU.

Problema •  Calcular el tamaño de la Tabla de Páginas

necesaria para soportar un sistema con páginas de 4KB, 4 bytes por entrada en la TP y direcciones virtuales de 32 bits.

•  Respuesta: 4MB!!!!!!!!!!

•  Es decir: se necesita en memoria por cada programa que está corriendo una tabla de 4MB

•  En una máquina con varios cientos de programas activos ............toda la memoria de la máquina estaría ocupada por las Tablas de Páginas!

Soluciones 1.  Limitar el tamaño de la TP por proceso, de manera que esta crezca

solo si el proceso lo necesita. Registro Límite. 2.  Idem que el anterior pero permitiendo que las direcciones crezcan

en los dos sentidos: de abajo hacia arriba (heap) y de arriba hacia abajo (pila). De esta forma las direcciones virtuales pertenecen a dos segmentos: el bit de mayor peso de la dirección identifica a cual. Cada segmento tiene una Tabla de Páginas diferente. MIPS

3.  Aplicar una función de hashing a la dirección virtual de forma que el tamaño de la Tabla de Páginas escale al tamaño de la memoria física y no al de la memoria virtual. Tabla de Páginas Invertida.

4.  Utilizar múltiples niveles de tablas de páginas. Un directorio que contiene direcciones de Tablas de páginas y las Tablas de Páginas que están en el segundo nivel. Tablas Jerárquicas. INTEL

5.  Paginar la Tabla de Páginas: es decir, permitir que las Tablas de Páginas residan en el espacio virtual.

Escrituras

•  Escritura diferida: además solo se escribe si la página fue modificada. Bit de sucio. (dirty).

•  El bit de dirty se activa cuando se realiza una escritura en la página

Traducción de direcciones •  Si la Tabla está en MP: un acceso a un dato requiere dos

accesos (al menos!): –  Uno para acceder a la dirección –  Otro para acceder al dato

•  Se puede acelerar basándose en el principio de localidad de las referencia:

–  Si una página fue recientemente referenciadaè es probable que lo vuelva a ser pronto porque los datos tienen localidad espacial y temporal

•  Solución: poner una pequeña caché de las últimas referencias traducidas a direcciones físicas: TLB

•  Translation LookAside Buffer

TLB: caché de direcciones

V a l i d 1 1 1 1 0 1 1 0 1 1 0 1

P a g e t a b l e

P h y s i c a l p a g e a d d r e s s V a l i d T L B

1 1 1 1 0 1

T a g V i r t u a l p a g e n u m b e r

P h y s i c a l p a g e o r d i s k a d d r e s s

P h y s i c a l m e m o r y

D i s k s t o r a g e

•  La TLB es una pequeña caché, por lo tanto cada entrada contiene un tag: el número de página virtual.

•  Cuando hay un fallo en la TLB, puede o no haber fallo de página.

•  Los fallos en la TLB los sirve el hardware por lo general.

•  La TLB contiene también los bits de referencia y sucio. Si hay reemplazo, se copian en memoria. (escritura diferida)

TLB •  Algunos valores normales para la TLB:

–  Tamaño: 32 a 4096 entradas –  Bloque: 1 o 2 entradas de Tabla de Página de 4-8 bytes

cada una. –  Tiempo de acierto: 0,5-1 ciclo –  Penalización por fallo: 10-30 ciclos –  Tasa de fallos: 0,01%-1% –  Asociatividad:

•  totalmente asociativaè difícil el reemplazo. Pocas entradas. •  Poca asociatividad (2,4)

TLB de la DECStation 3100 •  Sistema de memoria:

–  Páginas de 4KB –  Espacio de direcciones de 32 bits –  Espacio de direcciones virtuales de 32 bits –  TLB:

•  de 64 entradas •  totalmente asociativo •  compartido entre referencias a instrucciones y a datos.

TLB de la DECStation 3100 •  Fallo en la TLB:

–  MIPS salva el número de página virtual en un registro especial y genera una excepción.

–  El SO gestiona el fallo de la TLB, indexando la Tabla de Páginas con los dos registros:

•  El que contiene el número de página virtual •  El que contiene la dirección base de la TP del proceso actual •  Hay instrucciones especiales que le permiten al SO colocar la

dirección física en la TLB •  El hardware mantiene un índice a la siguiente entrada a ser

reemplazada (escogida al azar) •  Un fallo en la TLB tarda alrededor de los 16 ciclos •  Si la entrada en la TLB recientemente actualizada no contiene una

dirección física, la CPU genera otra excepción: fallo de página. •  Cuando la operación a realizar es una escritura: se comprueba en

la TLB que la página tenga derecho de escritura: sistema de protección.

TLBs y caches (DECStation 3100)

Yes

Deliver data to the CPU

Write?

Try to read data from cache

Write data into cache, update the tag, and put

the data and the address into the write buffer

Cache hit?Cache miss stall

TLB hit?

TLB access

Virtual address

TLB miss exception

No

YesNo

YesNo

Write access bit on?

YesNo

Write protection exception

Physical address

•  Si hay Hit en la TLBèse accede a la caché. •  Si es una escritura, y

hay permiso de escritura en la página, se sobreescribe en caché, y se envían al buffer de escritura

•  No hay fallos por escritura en esta caché: se escribe en caché en cualquier caso.

•  Si es lectura: fallo o acierto

•  Cuando hay fallo en la TLBè No se accede a caché.

Integración: memoria virtual, cachés y TLB’s

Caché TLB M.Virtual Posible?acierto acierto acierto SI. Situación Ideal!fallo acierto acierto SI. Si hay hit en TLB, no se comprueba la Tabla de Páginasacierto fallo acierto SI. La entrada se busca de la TP y luego se accede a la cachéfallo fallo acierto SI. La entrada se busca de la TP y luego se falla en la cachéfallo fallo fallo SI. Fallo de TLB y Fallo de Página: despues de reintentar la caché tiene que fallarfallo acierto fallo NO. No puede haber una traducción para una página que no está en memoriaacierto acierto fallo NO. No puede haber una traducción ni dato para una página que no está en memoriaacierto fallo fallo NO. No puede haber datos en caché que no estén en memoria

Integración

•  Sistemas con direcciones físicas traducidas ANTES de acceder a la caché: –  Cachés indexadas físicamente y etiquetadas físicamente –  El tiempo necesario para acceder al dato es la suma de los

tiempos de acceso a la TLB y a la Caché. •  Sistemas con direcciones físicas traducidas DESPUES de

acceder a la caché: –  Cachés indexadas virtualmente y etiquetadas virtualmente –  Se accede en paralelo a la TLB y a la Caché –  Solo en caso de miss en caché se usa la dirección física

obtenida en la TLB –  Problema: una misma dirección física puede tener varias

direcciones virtualesè estar contenida en varias líneas de la caché. (páginas compartidas entre programas)

Integración

•  Sistemas mixtos: – Las cachés se indexan con la dirección virtual (se

pueden usar los bits de desplazamiento de página que no se cambian en la traducción), pero se comparan con la dirección física.

– La caché y la TLB se acceden en paralelo. La TLB suministra la etiqueta para los comparadores

Protección •  Es una de las funciones del sistema de memoria

virtual: permitir la compartición de la memoria única entre múltiples procesos: protección entre procesos y con el SO.

•  En la TLB, el bit de escritura protege contra accesos de escritura no deseados.

•  Lecturas: –  El SO debe garantizar que las páginas virtuales de dos

procesos independientes se asignen a páginas físicas disjuntas.

–  También debe garantizar que un proceso no pueda cambiar su Tabla de Páginas, sin embargo el SO si debe poder cambiar las Tablas de Páginas.

Protección

•  El hardware debe proporcionar: –  Al menos dos modos de ejecución: proceso usuario y

proceso kernel (supervisor, ejecutivo) –  Instrucciones que solo puedan ser usadas por el proceso

kernel (para actualizar las estructuras de datos) –  Mecanismos para pasar de un modo a otro

•  De usario a kernelè excepciones, llamadas al sistema (syscall)

•  De kernel a usuarioèretorno de excepción: restaura el estado del proceso.

Jerarquía de Menoria Característica Cachés M.Virtual TLBTamaño en bloques 1000-100000 2000-250000 32-4000Tamaño en Kbytes 8-8000 8000-8000000 0.25-32Tamaño de bloque 16-256 4000-64000 4-32Penalización por fallo 10-100 ciclos 1 millon-10 millones 10-100Tasa de fallos 0,1%- 1% 0,00001%-0,0001% 0,01%- 2%

•  Ideas Comunes –  ¿dónde se encuentra un bloque?

•  En una única posición •  En unas cuantas •  En cualquiera

–  ¿cómo se encuentra un bloque? •  Indexando •  Búsqueda limitada (al conjunto) •  Búsqueda total •  Tabla de búsqueda

•  Ideas Comunes –  ¿qué bloque se debe reemplazar?

•  cualquiera •  El menos recientemente utilizado

–  ¿qué ocurre con las escrituras? •  Escritura a través (write through) •  Escritura diferida (write back)

Modelo de las tres (cuatro) C •  Clasifica las causas de los fallos en:

–  Compulsory (Inevitables): •  fallos de arranque en frío

–  Capacidad •  Ocurren cuando los bloques reemplazados se acceden mas

tarde: no hay lugar para todos los bloques accedidos del programa

–  Conflicto •  Solo ocurren en las asociativas por conjuntos o de mapeo

directo –  Coherencia

•  Bloques desplazados de la caché para mantener coherencia con memoria principal.

Compromiso de Diseño

Cambio de Diseño Efecto en la tasa de fallos Efecto negativo en el rendimientoIncrementar Tamaño decrementar los fallos por capacidad puede incrementar el tiempo de accesoIncrementar Asociatividad decrementa la tasa de fallos por conflicto puede incrementar el tiempo de accesoincrementar tamaño de bloque decrementa la tasa de fallos puede incrementar la penalización por fallos

Modern Systems Characteristic Intel Pentium Pro PowerPC 604

Virtual address 32 bits 52 bitsPhysical address 32 bits 32 bitsPage size 4 KB, 4 MB 4 KB, selectable, and 256 MBTLB organization A TLB for instructions and a TLB for data A TLB for instructions and a TLB for data

Both four-way set associative Both two-way set associativePseudo-LRU replacement LRU replacementInstruction TLB: 32 entries Instruction TLB: 128 entriesData TLB: 64 entries Data TLB: 128 entriesTLB misses handled in hardware TLB misses handled in hardware

Characteristic Intel Pentium Pro PowerPC 604Cache organization Split instruction and data caches Split intruction and data cachesCache size 8 KB each for instructions/data 16 KB each for instructions/dataCache associativity Four-way set associative Four-way set associativeReplacement Approximated LRU replacement LRU replacementBlock size 32 bytes 32 bytesWrite policy Write-back Write-back or write-through

33

Ejemplo: Pipeline del R3000

Fetch D/R ALU/ EA

WB Memoria

•  Cada Etapa está dividida en dos fases. El reloj es de 60 nseg. Cada fase de 30 nseg. •  TLB: TLB read •  I-Cache: Fetch Instrucción •  RF: Lectura de Registros (segunda fase) •  IDEC: Decodificación de Instrucción •  IA: Cálculo de la dirección de la Instrucción •  EA: Cálculo de la Dirección Efectiva del dato •  TLB: Búsqueda en el TLB de datos •  operación: operación •  D-Cache: Acceso al dato •  WB: Escritura de Registros (primera fase)

TLB I-Cache RF EA TLB operación D-Cache

WB

WB

IDEC

IA

34

Ejemplo: R3000 IF RD ALU/

EA WB Memoria

TLB I-Cache RF EA TLB operación D-Cache WB

WB

IDEC IA

Etapa Fase Función IF Φ1 Usando la TLB, traduce una dirección virtual a una dirección física

IF Φ2 Envía la dirección física a la cache de instrucciones

RD Φ1 Llega la instrucción leída de la caché

RD Φ2 Decodifica instrucción

Lee el Banco de Registros

Si es un salto, calcula la dirección de salto

ALU Φ1+ Φ2 Si es R-R, se realiza la operación

ALU Φ1 Si es salto, decide si saltar o no.

ALU Φ2 Si es una referencia a memoria, traduce su dirección virtual a física usando la TLB

MEM Φ1 Si es una referencia a memoria, envía la dirección a la cache de datos

MEM Φ2 Si es una referencia a memoria, recibe el dato de la caché y chequea el tag.

WB Φ1 Escribe en el Banco de Registros

R3000 vs nuestra máquina

•  Semejanzas: –  5 etapas de pipeline. – Retardo del load: 1 ciclo – El slot delay del salto es de un ciclo.

•  Diferencias – El salto se ejecuta en la etapa ALU – La dirección de salto se calcula en RD – La penalización del salto es de 2 ciclos.

FIN Memoria Virtual