Gestión de memoria(AC 06-07) - icaro.eii.us.es

Profesores y Horarios de Tutorías Temas 3 y 4

Teoría:

Daniel Cascado Caballero ([email protected]) Despacho: F070

Lourdes Miró Amarante ([email protected]) Despacho: F061 Horario de tutorías: Martes: 11:00h a 13:00h; 17:30 a 19:30 Miércoles: 10:30h a 12:30h 1

Bibliografía Básica Temas 3 y 4

Estructura y Diseño de Computadores, J. L. Hennessy y D. A. Patterson. Ed. Reverte, 2000. Organización y arquitectura de computadores, W. Stalling. Prentice-Hall, 2000.

2

1

Estructura Básica de un Computador Máquina Von Neumann

CPU Interconexiones

Memoria

E/S Periféricos

3

Ampliación Máquina Von Neumann Programa principal I1 I2

TEMA 4

TEMA 3 CPU palabras

. .

Memoria principal Interrupción

Ii Ii+1

(Mc) páginas bloques

. . In Rutina de servicio i1 i2 . . im Sistema de interrupciones

(Mp)

Memoria cache

Memoria principal

Memoria secundaria

(Mp)

(Ms)

Sistema de memoria cache

Sistema de memoria virtual 4

2

Tema 3: GESTIÓN DE MEMORIA ÍNDICE

Jerarquía de memoria Memorias caché

1. 2.

Introducción Organización física Organización lógica Optimización

1. 2. 3. 4.

3.

Memoria virtual

5

Jerarquía de memoria Introducción

Necesidad de grandes cantidades de memoria rápida con tiempos de acceso y transferencia pequeños.

Diferentes tipos de memorias según los criterios de tamaño, velocidad y coste (tecnología). Idealmente sería deseable una capacidad indefinidamente grande de memoria tal que cualquier particular…palabra estuviese inmediatamente disponible… Estamos… forzados a reconocer la posibilidad de construir una jerarquía de memorias, memorias cada una de las cuales tenga mayor capacidad que la precedente pero que sea menos rápidamente accesible.

A.W. Burks, H.H. Goldstine y J. Von Neumann, Discusión preliminar del diseño lógico de un instrumento de cálculo electrónico (1946)

1. Jerarquía de memoria

6

3

Definición Una jerarquía de memoria está organizada en varios niveles, cada uno más pequeño, más rápido y más caro por byte que el siguiente.

Coste/bit (+) Capacidad (-) Velocidad (+) Frecuencia de accesos (+)

Registros procesador Caché Memoria principal Caché de disco Disco magnético CD-DVD


7

Propiedades

Inclusión: Cualquier información almacenada en un nivel de memoria, debe encontrarse también en los niveles inferiores. nivel i+1

nivel i

Coherencia: Las copias de la misma información existentes en los distintos niveles deben ser consistentes.

Localidad de referencia: Los programas favorecen una parte de su espacio de direcciones en cualquier instante de tiempo. Localidad temporal: Si se referencia un elemento, éste tenderá a ser

referenciado pronto (p.e. bucles) Localidad espacial: Si se referencia un elemento, los elementos cercanos a él tenderán a ser referenciado pronto (p.e. tablas).


8

4

Funcionamiento

El procesador sólo accede al nivel más alto (más rápido y de menor tamaño).

Si el procesador pide un dato y éste se encuentra en el nivel superior (acierto).

Si el dato no se encuentra en este nivel (fallo) se trae del nivel inferior al superior.

Nivel superior

Bloques

Las transferencias de datos entre niveles se hace con bloques de varios bytes.

Nivel inferior 1. Jerarquía de memoria

9

Conceptos básicos

Nivel (level). Bloque (block): mínima unidad de información que puede estar presente o no en la jerarquía de dos niveles (tamaño fijo o variable). Acierto/Fallo (hit/miss). Frecuencia de aciertos/fallos (hit rate, Hr /miss rate, Mr ). Tiempo de acierto (hit time). Penalización por fallo (miss penalty).

Tiempo de acceso (access time): tiempo para acceder a la primera palabra de un bloque en un fallo. Tiempo de transferencia (transfer time): tiempo adicional para transferir las restantes palabras del bloque.


10

5

Evaluación del rendimiento

Tiempo medio de acceso a memoria Tiempo de acceso medio a memoria = Tiempo de acierto + + Frecuencia de fallos*Penalización por fallo

Por el principio de localidad, Mr suele ser <= 10% El Mr se obtiene mediante TRAZAS de accesos a memoria. Habrá un Mr por cada nivel de la jerarquía. Influencia de parámetros

El tamaño de bloque influye sobre: Penalización por fallo Tiempo de acceso medio a memoria Frecuencia de fallos


11

Evaluación del rendimiento Relación entre parámetros Tiempo medio de acceso

Tamaño del bloque

Penalización por fallo

Tiempo de transferencia

Frecuencia por fallo

Tiempo de acceso Tamaño del bloque


Tamaño del bloque

12

6

Memoria caché Introducción CPU palabras

Representa el nivel de jerarquía de memoria entre la CPU y la memoria principal.

Memoria Memoria caché caché

Controlador Controlador de decaché caché bloques

Se le pueden aplicar todos los conceptos vistos para la jerarquía de memoria (propiedades, funcionamiento, conceptos básicos, rendimiento).

Memoria principal (Mp)

2. Memoria cache

13

Estructura Memoria Caché/Memoria Principal

Mp (memoria principal):

formada por 2n palabras direccionables. “dividida” en nB bloques de tamaño fijo 2K (palabras por bloque). Campos de una dirección física:

Dirección de memoria

Mp

1 DF:

B

P

Mc

0 Bloque 0

(n-k bits) (k bits) Bloque

Palabra

.

n

Bloque 1

.

dirección

Mc (memoria cache):

Línea 0

2

formada por nL líneas de (nL << nB).

2K

.

palabras

.

Línea de caché (contenido):

Información de bloque Datos adicionales Bit de línea válida. Info. identificación de bloque Otros...

2. Memoria cache

. Línea nL -1

. Bloque 2n/2k -1= nB -1 2n

-1

14

7

Funcionamiento

2. Memoria cache

15

Arquitecturas

Organización física

Según su ubicación dentro o fuera del chip procesador: internas o externas. Según su ubicación con respecto al resto de dispositivos (configuración).

Organización lógica

Según el tipo de información que contienen: unificadas o separadas. Según su estructura interna y funcionamiento: ubicación, identificación, sustitución y escritura

2. Memoria cache

16

8

Organización física

Según su ubicación Caches externas: No se encuentran en el interior del chip del procesador (cache-off-chip). Caches internas: Se encuentran en el propio chip del procesador (cache-on-chip).

Según la configuración Configuración en serie (Look-Trough Architecutre). Configuración en paralelo (Look-Aside Architecture).

2. Memoria cache. cache Organización Física

17

Configuración en serie CPU

Bus Cache

DMA

I/O

Memoria

Bus

Tc

Tmp t

Ventajas: Si el dato se encuentra en la caché no hay acceso a memoria y no se ocupa el bus. Inconvenientes: La caché debe tener 2 interfaces de buses diferentes y el tiempo de acceso, en caso de fallo, es mayor (igual al tiempo de acceso a caché más el tiempo de acceso a memoria principal). Tacc = Hr*Tcache +(1-Hr)*(Tcache+Tmemp)

2. Memoria cache. Organización Física según la CONFIGURACIÓN

18

9

Configuración en paralelo Cache

DMA

I/O

Memoria

Bus

CPU Tc Tmp t

Ventajas: Sólo hay una interfaz con el bus y el tiempo de fallo es menor (igual al tiempo de acceso a memoria principal). Inconvenientes: El bus se ocupa en cualquier acceso a memoria, evitando que otros dispositivos puedan acceder a él.

Tacc=Tcache*Hr + (1-Hr)*Tmemp

2. Memoria cache. Organización Física según la CONFIGURACIÓN

19

Organización lógica

Según el tipo de información que contienen: unificadas o separadas.

Separadas:

Tacc= %instrucciones * Tacc_inst + %datos*Tacc_datos

Según su estructura interna y funcionamiento (Políticas):

Ubicación (función de correspondencia). Localización. Sustitución. Escritura.

2. Memoria cache. Organización Lógica

20

10

Caches unificadas vs. Caches separadas

Caches unificadas o mixtas (unified or mixed): Contienen tanto datos como instrucciones Caches separadas (separated): Existe una caché para datos y otra para instrucciones

Ventajas No hay competencia entre acceso a datos y acceso a instrucciones. Duplicación del ancho de bus (puertos separados) Parámetros de diseño (capacidad, tamaños de bloque, asociatividad, etc.) diferentes para instrucciones y datos (optimización) Inconvenientes En general la tasa de fallos global es algo mayor (próxima transparencia):

la caches de instrucciones tienen menor frecuencia de fallos que las de datos (localidad) la separación de instrucciones y datos elimina fallos debidos a conflictos pero al dividir también se fija el espacio de caché dedicado a cada tipo

No se equilibra la carga de trabajo de forma automática

2. Memoria cache. Organización Lógica. Cache unificada vs cache separada.

21

Ejemplo caches separadas: Pentium II Depósito de instrucciones. Buffer de reordenación.

Unidad de lectura y decodificación de instrucciones.

Caché de instrucciones L1. (8-16K)

Unidad de retirada

Unidad de ejecución y envío

Caché de datos L1. (8-16K)

Cada caché tiene asociada al menos una unidad de control que controla las peticiones de datos.

Interfaz con el bus

Bus del sistema

Caché L2. (256-1M)


22

11

Comparativa (I) Comparativa de frecuencias de fallos (VAX, 16 bytes/bloque, LRU, 2 vías)

Ejemplo: Frecuencia de fallos (53% de referencias son instrucciones)

En caché unificada de 32KB: 4.3% En caches separadas de 16KB: 53%*3.6%+47%*5.3%=4.4%


23

Comparativa (II) Ejemplo: (75% de accesos a instrucción)

a)

b)

Caches separadas de 16KB. Penalización: 50 ciclos, Tiempo de acierto para instrucción: 1 ciclo, para datos: 2 ciclos (un solo puerto) Cache unificada de 32KB. Penalización: 50 ciclos, Tiempo de acierto: 1 ciclo

Solución: a) Tacceso medio =75%*(1+3.6%*50)+25%*(2+5.3*50)= 3.26 ciclos b) Tacceso medio=1+4.3%*50 = 3.0 ciclos=3.15 ciclos


24

12

Políticas de Ubicación y Localización.

Ubicación: Dado un bloque de Mp, con una dirección Db, que se quiere subir a caché, ¿En qué línea hay que ubicarlo?

Función de correspondencia: Línea = f(Db)

Localización: ¿En qué líneas de caché tengo que buscar para saber si un bloque de Mp con dirección Db está en ella?

Se utiliza la función de correspondencia.

2. Memoria cache. Organización Lógica. Políticas de UBICACIÓN y LOCALIZACIÓN 25

Ubicación de un bloque. ¿Qué hay que hacer cuando se quiere subir un bloque a caché? Se averiguan las líneas en las que es posible ubicar mediante la función de correspondencia. Se selecciona una mediante la política de reemplazo (se verá más adelante). Si la línea está vacía, el bloque se guarda en ésta. Si no,se produce un conflicto, y habrá que bajar el antiguo bloque a memoria principal y subir el nuevo a la línea seleccionada. 2. Memoria cache. Organización Lógica. UBICACIÓN

26

13

Identificación de un bloque Una vez que se sabe en qué líneas buscar un bloque con dirección Db ¿Cómo se sabe si está realmente en caché? Se mira el bit de válido de la línea para saber si es válida. Se descompone la dirección Db al menos, en estos campos: Etiqueta (tag): Desplazamiento de bloque (block offset): selecciona el dato deseado dentro del bloque. Se extrae el campo etiqueta y se compara con el campo etiqueta de la línea. Si la línea es válida y las etiquetas son iguales, el bloque está en caché.

2. Memoria cache. Organización Lógica. IDENTIFICACIÓN

27

Políticas de Ubicación y Localización. Mp

Mc

. . .

B0 B1 B2 B3 B4 B5 B6 B7

Mc B0 B1 B2 B3 B4 B5 B6 B7

DIRECTA

ASOCIATIVA

Mc C0 C1 C2 C3

ASOCIATIVA POR CONJUNTOS

2. Memoria cache. Organización Lógica. Políticas de UBICACIÓN y LOCALIZACIÓN 28

14

Ejemplo de Ubicación de bloque

Memoria: 32 bloques Caches: 8 bloques Tres tipos: - Asociativas - Directa - Asociativa por conjuntos de 2 vías

2. Memoria cache. Organización Lógica. Política UBICACIÓN

29

Ejemplo de localización e identificación de un bloque Memoria: 32 bloques Caches: 8 bloques Tres tipos: - Completamente asociativas - De correspondencia directa - Asociativa por conjuntos de 2 vías

2. Memoria cache. Organización Lógica. LOCALIZACIÓN

30

15

Cache de Mapeado Directo

Líneas MC

Memoria Principal (Mp): 16MB direccionables por bytes (dirección de 24bits).

Memoria Cache (Mc): 64KB.

Tamaño de bloque 16 Bytes: Nº Bloques en MP: nB = 1M (20 bits) Nº Líneas en MC: nM = 4K (12 bits)

M = B mod nM

Interpretación de DF en correspondencia DIRECTA: 4 20 B

P

ETQ

M

P

8

12

4


31

Cache de Mapeado Directo •Ventajas: •Baja complejidad hardware

Dirección solicitada (de CPU) 6 5 4 3 2 1 0 1 1 1 1 0 1 1 ETI INDICE W B

•Rapidez en la identificación •Inconvenientes: V

Datos

•Alta tasa de fallos si varios bloques compiten por la misma línea.

DECODER

COMPARADOR

Etiqueta

Memoria principal

1 1 Encontrado (si)

Bloque 0

ACADA...B3 Bloque 1 (y sigue)

Y

Dato solicitado (AF)

Dato A1 A2 A3 A4 A5 A6 A7 A8 A9 AA AB

......

Selector Acierto (si)

Dirección 0000000 0000001 0000010 0000011 0000100 0000101 0000110 0000111 0001000 0001001 0001010

Bloque 15 1111000 1111001 1111010 1111011 1111100 1111101 1111110 1111111


AC AD AE AF B0 B1 B2 B3

32

16

Cache Totalmente Asociativa

Líneas Mc

Memoria Principal (Mp):

16MB direccionables por bytes (dirección de 24bits).

Memoria Cache (Mc):

Cada bloque B

64KB.

puede ubicarse en

Tamaño de bloque 16 Bytes:

cualquier línea M.

Nº Bloques en MP: nB = 1M (20 bits) Nº Líneas en MC: nM = 4K (12 bits)

Interpretación de DF en correspondencia TOTALMENTE ASOCIATIVA: 20

4

B

P

ETIQUETA

P

20

4


33

Cache Totalmente Asociativa •Ventajas: •Baja tasa de fallos

Dirección solicitada (de CPU) 6 5 4 3 2 1 0 1 1 1 1 0 1 1 ETI W B

•Inconvenientes: •Alta complejidad hardware.

COMPARADOR

Etiqueta

V

Datos

•Lentitud en la identificación. Memoria principal

1111 1 ACADA...B3

Bloque 0

Bloque 1 (y sigue)

Encontrado (si)

Y

Dirección 0000000 0000001 0000010 0000011 0000100 0000101 0000110 0000111 0001000 0001001 0001010


......

Selector Acierto (si)



Bloque 15 1111000 1111001 1111010 1111011 1111100 1111101 1111110 1111111


34

17

Cache Asociativa por Conjuntos

Línea

Memoria Principal (Mp):

16MB direccionables por bytes (24bits).

Memoria Cache (Mc):

64KB.

Tamaño de bloque 16 Bytes:

Nº Bloques en MP: nB = 1M (20 bits) Nº Líneas en MC: nM = 4K (12 bits)

4 vías:

C = B mod nC

Nº de Líneas por Conjunto: 4 Nº de Conjuntos en Mc: nC = 1K (10 bits)

Interpretación de DF en correspondencia ASOCIATIVA POR CONJUNTOS: 20

4

B

P

ETQ

C

P

10

10

4


35

Cache Asociativa por Conjuntos

DECODER

Dirección solicitada (de CPU) 6 5 4 3 2 1 0 1 1 1 1 0 1 1 ETI CJTO W B

Memoria principal

Eti V

VIA 0 Datos

Eti V

Bloque 0

VIA 1 Datos Bloque 1 (y sigue)

11 1 ACADA...B3 =

Dirección 0000000 0000001 0000010 0000011 0000100 0000101 0000110 0000111 0001000 0001001 0001010


......

= Y

Y Acierto vía 1(no)

Acierto vía 0 (si) Selector

Bloque 15 1111000 1111001 1111010 1111011 1111100 1111101 1111110 1111111




36

18

Ejemplo (I) • • •

1 2 3

Procesador de 16 bits de datos y 24 de direcciones Tamaño de la cache: 8KB Tamaño de la línea: 8 bytes 1. Cache totalmente asociativa 2. Cache asociativa por conjuntos de 4 vías 3. Cache de mapeado directo Etiqueta: 21bits

Desplazamiento: 3bits Palabra: 2bits

Etiqueta: 13bits

Conjunto: 8bits


Etiqueta: 11bits

Byte:1bit

Bloque: 10bits

Byte:1bit



Byte:1bit

37

Ejemplo (II)

- Cache asociativa por conjunto de 2 vías - Capacidad de datos: 8KB - Tamaño de bloque: 8 bytes - Número de conjuntos: 512 Pasos de un acierto: 1) División de la dirección 2) Acceso a ambos bancos 3) Comparación de etiquetas 4) Multiplexación 5) Envío a la CPU


38

19

Políticas de escritura Frente acierto en la cache Escritura directa (Write through):

Escritura en Memoria cache (Mc) y Memoria principal (Mp).

Postescritura (Copy Back):

La información se escribe sólo en el bloque de la Mc. Este bloque se denomina sucio o modificado. El bloque modificado de la Mc se escribirá en la Mp sólo cuando éste sea reemplazado. Para reducir la frecuencia de postescrituras en el reemplazo, se usa el bit de modificación o sucio (dirty bit), de manera que si el bloque está limpio no se escribe Mp.

2. Memoria cache. Organización Lógica. Política ESCRITURA

39

Políticas de escritura Ventajas e Inconvenientes

Escritura directa (Write through):

Ventajas:

Inconvenientes:

Fácil de implementar. Bajo coste hardware. La Mp tiene la copia más reciente de los datos (coherencia de cache, multiprocesadores y E/S). Tráfico importante en Mp. Velocidad de la escritura es la velocidad de escritura en Mp (Solución: Buffer de escritura).

Postescritura (Copy Back):

Ventajas:

Las escrituras se realizan a la velocidad de la memoria caché. Múltiples escrituras en un bloque requieren sólo una escritura en Mp. Disminuye tráfico entre Mc y Mp.

Inconvenientes:

Inconsistencia Temporal entre Mc y Mp. Necesidad de bit adicional, bit dirty. Implementación más compleja.


40

20

Políticas de escritura Frente fallo en la cache

Ubicación en escritura (Write allocate): El bloque se carga en Mc y a continuación se escribe sobre él (similar a acierto en escritura). Apropiado para Copy Back (CB-WA).

No ubicación en escritura (No write allocate): El bloque se modifica en Mp y no se carga en Mc. Apropiado para Write Through (WT-NWA).


41

Políticas de reemplazo Espacio de Ubicación

Espacio de Ubicación ES el conjunto de posibles bloques de Mc que pueden ser reemplazadas por un nuevo bloque.

Depende de la función de correspondencia: Mapeado directo: Sólo hay una opción. Totalmente asociativa: Cualquier bloque que reside en la cache. Asociativa por conjuntos: Cualquier bloque que reside en el conjunto que tiene asignado el nuevo bloque.

2. Memoria cache. Organización Lógica. Política SUSTITUCIÓN

42

21

Políticas de reemplazo

Diferentes estrategias: Aleatoria (Random): Se elige un bloque al azar. FIFO (First Input First Out): Se sustituye el bloque que más tiempo ha estado en la cache. LRU (Least Recently Used): Se sustituye el bloque que más tiempo ha estado en la cache sin ser referenciado. LFU (Least Frecuently Used): Se sustituye el bloque que menos referencias ha tenido. Se tienen en cuenta criterios de coste y eficiencia Los esquemas más utilizados son el aleatorio y el LRU


43

EJEMPLO Ejemplo de política LRU (cache de 4 bloques) Dirección Bloque LRU

0

3

2

1

0

0

2

3

1

3

0

0

0

0

3

3

3

1

0

0

2

Comparativa de frecuencias de fallos (VAX, 16bytes/bloque)


44

22

Optimización Cómo mejorar el rendimiento de las caches El objetivo es reducir el tiempo medio de acceso a memoria:

Tacceso_medio = Tacierto + ffallos*Penalización_fallo Se puede actuar sobre 3 términos: 1. Reducir el tiempo de acceso en caso de acierto (hit time) 2. Reducir la frecuencia de fallos (miss rate). 3. Reducir las penalizaciones por fallo (miss penalty).

2. Memoria cache. Optimización

45

Reducir la frecuencia de fallos Tipos de fallos

Forzosos (Compulsory):

Capacidad (Capacity):

En el primer acceso a un bloque, éste no se encuentra en la caché.

La caché no puede contener todos los bloques necesarios durante la ejecución de un programa.

Conflicto (Conflict):

Diferentes bloques deben ir necesariamente al mismo conjunto o línea, cuando la estrategia es asociativa por conjuntos o de correspondencia directa (fallos de colisión).

2. Memoria cache. Optimización. Reducción de fallos

46

23

Tipos de fallos Frecuencia total de fallos para cada tamaño de cache:


1.

Fallo forzoso: Independiente del tamaño de cache.

2.

Fallo de capacidad: Decrece al aumentar tamaño de la cache.

3.

Fallo de conflicto: Decrece al aumentar la asociatividad.

47

Tipos de fallos


48

24

Reducir la frecuencia de fallos Técnicas

Aumento del tamaño del bloque.

Aumento de la asociatividad.


49

Incremento del tamaño de bloque

Ventaja:

Se reducen los fallos forzosos (principio de localidad espacial).

Inconvenientes:

Aumentan los fallos por conflicto al reducirse el número de bloques de la caché. La penalización por fallo aumenta al incrementarse el tiempo de transferencia del bloque:

Penalización por fallo

Tiempo de transferencia Tiempo de acceso

Frecuencia por fallo

Tamaño del bloque


Tamaño del bloque

50

25

Incremento del tamaño de bloque

forzosos Conflicto

Capacidad


51

Ejemplo incremento del tamaño de bloque

Ejemplo: Tiempo de búsqueda = 40CLK Tasa de transferencia= 8bytes/CLK Tiempo de acierto= 1CLK a) Cache de 1Kb con línea de 16bytes b) Cache de 256Kb con línea de 256bytes Solución: a) Tiempo de acceso medio a memoria = 1+15.05%*(40+2)=7.321 ciclos b) Tiempo de acceso medio a memoria = 1+0.49%*(40+32)=1.353 ciclos 2. Memoria cache. Optimización. Reducción de fallos

52

26

Incremento de la asociatividad

Ventaja:

Se reducen los fallos por conflicto.

Inconveniente:

Aumenta el tiempo de acceso medio al incrementarse el tiempo de acierto. También aumenta el coste debido a los comparadores.

Cache de mapeado directo (1KB): tamm= 1+(0.133*50)=7.65 ciclos

Cache asociativa por conjuntos de 8 vías (128KB): tamm= 1+(0.0088*50)=1.44 ciclos

Tiempo medio de acceso a memoria (ciclos)


53

Memoria virtual Objetivos

Permitir a los programas usar más memoria de la disponible físicamente. Se gestiona automáticamente los dos niveles de la jerarquía de memoria representada por la memoria principal y la secundaria, liberando al programador de esta tarea (origen histórico) ... se ha inventado un sistema para hacer que la combinación de tambores de núcleos magnéticos parezca al programador como un simple nivel de almacenamiento, realizando automáticamente las transferencias precisas Kilburn y cols. [1962]

Compartir una misma memoria física entre diferentes procesos con su propio espacio de direcciones (sistemas multitarea). Sería muy costoso dedicar una memoria de tamaño igual al espacio total de direcciones a cada proceso. Se requiere un esquema de protección

3. Memoria virtual

54

27

Definiciones (I) Traducción de direcciones

Direcciones virtuales

Direcciones físicas

0

A

4K

B

8K

C

8K

12K

D

12K

Espacio virtual del proceso A. 0

A’

4K

0

C

A

4K

Página

16K 20K

B

24K

A’

28K

Memoria principal

8K 12K

Espacio virtual del proceso B.

D

Disco o Memoria Secundaria 3. Memoria virtual

55

Definiciones (II)

Página (page):en los términos definidos para la jerarquía de memoria es un bloque Fallo de página (page fault) o de dirección (address fault): cuando la página solicitada está en disco (y ha de subirse a memoria). Direcciones virtuales: son las direcciones que genera la CPU Direcciones físicas: son las direcciones que atacan a la memoria principal Correspondencia de memoria (memory mapping) o traducción de direcciones (address translation): el proceso (software/hardware) para traducir las direcciones virtuales a direcciones físicas Niveles de la jerarquía controlados por la memoria virtual: Memoria RAM y disco duro Marco: sitio donde se ubica una página en disco o en MP.

3. Memoria virtual

56

28

Memoria virtual Visión general.

Cada proceso tiene un espacio de direcciones propio, (espacio virtual) mayor incluso que la MP.

El espacio virtual se divide en páginas . El procesador genera direcciones virtuales.

Número de página virtual. Desplazamiento.

Las páginas pueden estar en MP o en disco. Los lugares donde se meten las páginas se llaman marcos. En MS existe un fichero especial en el que se encuentran los marcos de MS. Es gestionado por el S.O. Las direcciones virtuales son traducidas en direcciones físicas para su acceso a MP.

La tabla de páginas (una para cada proceso) relaciona las direcciones virtuales con las físicas (marcos). Existe una tabla de páginas por proceso activo en el sistema.

#pag_física = TablaPaginas(#pagina virtual)

3. Memoria virtual

57

Tabla de Páginas

¿Cómo se sabe si una página está en memoria principal? La dirección virtual se descompone en dos campos: número de página virtual y desplazamiento de página La dirección física se obtiene concatenando simplemente la dirección física de la página con el desplazamiento de página Se utiliza una estructura de datos (tabla de páginas) que contiene la dirección física de la página y es indexada por la dirección virtual La tabla de páginas reside en memoria principal.

3. Memoria virtual

58

29

Tabla de páginas Correspondencia entre dirección virtual y física Registro de la tabla de páginas

Número de página virtual (20) 1

Pag. V (20bits) V D R W LRU 0 1 1 0 1 1 --...

Desplazamiento (12) 120

Marco (18 bits) 46544

1048575

Marco (18) 46544

Desplazamiento (12) 120

3. Memoria virtual

59

Funcionamiento. Dirección virtual

Página en MP?

si

Tratamiento del fallo de página (S. O.)

no MP llena?

no

Dato en caché?

si

no si Bajar página a MS

Subir página a MP y actualizar TP.

Bajar subir bloque a Caché

Dato (desde caché)

Dir. física (desde TP)

3. Memoria virtual

60

30

Ciclo de vida de un proceso en memoria virtual.

Cuando un proceso se inicia, se hace sitio en MS para todas sus páginas, y se le crea su propia tabla de páginas. Cuando una página se quiere usar y no está en MP se produce un fallo de página, (paginación bajo demanda) y hace que la página pase a MP. En esta situación se produce una excepción en la CPU, y se llama al S.O. para que gestione el fallo de página. Una página se va a MS cuando la MP está llena y tiene que entrar una página nueva (reemplazo).

El intercambio excesivo de páginas, se llama hiperpaginación.

Cuando un programa termina, se liberan sus marcos de MS y MP.

3. Memoria virtual

61

Buffer de traducción anticipada o TLB (I). Motivación y definición.

La velocidad de un sistema con memoria virtual se ve mermada por su misma naturaleza. Un acceso a dato implica:

Acceso a la tabla de páginas (en MP o en caché) para traducción. Acceso al dato (en caché, en MP o en disco) Por lo tanto, el sistema es al menos, el doble de lento de lo que era cuando no tenía memoria virtual.

Se puede mejorar el rendimiento, aplicando el concepto de localidad referencial a los accesos a la tabla de páginas.

Definiendo una TLB.

Se puede tener una caché de la tabla de páginas = TLB.

Es un mecanismo de aceleración de las consultas a la TP con objeto de traducir lo antes posible.

La memoria perteneciente a la TP no es cacheable por la caché ordinaria. Sólo existe una para todo el sistema, y es interna al procesador. Las referencias pueden pertenecer a uno o a varios procesos (TP):

Una vez realizada la traducción a dir. Física, deja de actuar.

Uno: la TLB se borra al cambiar de proceso.Produce más fallos por iniciación. Varios: campo PID de proceso en la TLB. Evita algunos fallos por iniciación.

Puede ser unificada o separada.

3. Memoria virtual

62

31

TLB. Esquema

3. Memoria virtual

63

TLB. Funcionamiento.

Cuando un proceso se vuelve activo en el sistema se cambia de TP, y la TLB se borra, si sólo tiene refs a un proceso. La CPU genera internamente una dirección virtual que es cotejada en la TLB para ver si está su traducción.

La dirección virtual sólo existe dentro del procesador.

Si la referencia a la TP no está: fallo de TLB: Se trae un bloque de entradas de la TP a TLB y a continuación se consulta ésta.

Cuando hay un acierto en TLB, la página está en MP, y puede que sus datos estén en caché.

Si además, la página no está en MP: fallo de página.

Tamaño de bloque

4-8 bytes (una entrada de TP)

Tiempo de acierto

1 ciclo de reloj

Penalización de fallos 10-30 ciclos de reloj Frecuencia de fallos

0.1%-0.2%

Tamaño TLB

32-8192

3. Memoria virtual

Valores típicos de parámetros

64

32

TLB. Funcionamiento (II). Dirección virtual

Acierto en TLB?

si

Dir. física (desde TLB)

no Página en MP?

si

no MP llena?

Dato en caché?

no

si

no si Bajar página a MS

Subir página a MP y actualizar TP.

Bajar subir bloque a Caché

Dato (desde caché)

Dir. física (desde TP) y actualiza TLB.

3. Memoria virtual

65

TLB. Implementación típica.

Líneas de 1 entrada de la TP. 32-1024 líneas Totalmente asociativo, o asociativo por conjuntos. Mr=0.001 - 0.01 Implementación dentro del procesador. Sólo una. CB-WA. Reemplazo aleatorio. Para cada bloque:

Bit de válido. Bits de etiqueta (nº de página virtual, si blq=1entrada). Entrada de la TP. Bit de Dirty. 66

33

Buffer de traducción anticipada o TLB (IV) Ejemplo: TLB del VAX-11/780 Tamaño de página de 512bytes Entrada de TP de 4bytes TLB de 512bytes asociativa por conjuntos de 2 vías Pasos: 1: Envío del índice de la dirección virtual 2: Comprobación de válido y tipo de acceso a memoria 3: Comparación de etiquetas 4: Envío de la dirección física a través del multiplexor 5: Combinación del número y desplazamiento de página

3. Memoria virtual

67

34

Gestión de memoria(AC 06-07) - icaro.eii.us.es

Recommend Documents