T5-Memorias

Jerarqua de memoria

Katia Leal Algara [email protected]

http://gsyc.escet.urjc.es/~katia/

Departamento de Sistemas Telemticos y Computacin (GSyC)

GSyC - Jerarqua de memoria 1

!qNecesidad de una jerarqua de memoria!qVeremos:!

qMecanismo de acceso de memoria en este tipo de jerarqua!qDiseo y evaluacin del rendimiento de la

jerarqua de memoria!qAspectos tecnolgicos y de diseo de los

distintos niveles de la jerarqua de memoria!

Conceptos bsicos de memoria

Introduccin


!q El sistema de memoria de los primeros modelos de

computador se descart rpidamente por su bajo rendimiento!

q En su lugar, hoy se utiliza una jerarqua de memoria organizada en niveles que incluye:!qMemoria cach!qMemoria principal!qMemoria virtual!

q Cada una:!q se ubica fsicamente en un lugar distinto!q se fabrica con una tecnologa diferente!q se gestiona de manera independiente!


Diseo de una jerarqua de memoria bsica


!q Memoria cach (MC)!q Ubicada en el mismo chip que el procesador!q Fabricada con memoria RAM esttica (SRAM),

Static Random Access Memory!q Es un tipo de memoria basada en semiconductores que a

diferencia de la memoria DRAM es capaz de mantener los datos sin necesidad de circuito de refresco. Sin embargo, s son memorias voltiles, es decir que pierden la informacin si se les interrumpe la alimentacin elctrica!

q Controlada por el controlador de cach incluido en el mismo chip!

q Hoy en da existen varios niveles de cach!qHasta ahora hemos estado utilizando memoria cach de

nivel 1!




!q Memoria principal (MP)!q Ubicada en un chip diferente al procesador!q Fabricada con memoria RAM dinmica (DRAM),

Dynamic Random Access Memory!q Para mantener almacenado un dato, se requiere revisar el

mismo y recargarlo cada cierto tiempo, en un ciclo de refresco. Su principal ventaja es la posibilidad de construir memorias con una gran densidad de posiciones y que todava funcionen a una velocidad alta!

q Controlada por el controlador de memoria principal que se encarga de planificar los accesos a la misma!

q Hoy en da el controlador puede ubicarse en el mismo chip que el procesador y la memoria cach o en otro chip como el chipset norte o el MCH!




!qMemoria virtual (MV)!qUbicada en el disco duro!qFabricada con tecnologa magntica!qSe controla desde el sistema operativo a

travs del controlador de disco duro!




!q rdenes de magnitud de capacidades y tiempos de acceso!




!q Tecnologas y caractersticas de los diferentes niveles!




!qInclusin: cualquier informacin contenida

en un nivel de la jerarqua debe estar tambin en los niveles superiores!

qCoherencia: las copias de la misma informacin en los diferentes niveles son coherentes entre s, es decir, que almacenan los mismos valores!

qDebe haber una correspondencia de direcciones entre los distintos niveles de la jerarqua!

!


Propiedades de una jerarqua de memoria


!qLa palabra a leer o escribir se busca en MC!

qSi la palabra se encuentra en cach, acierto!qSi no se encuentra en cach, fallo. La

penalizacin por fallo depender de la latencia de la MP y de su ancho de banda!

qSi la palabra no se encuentra en la MC, se trae un bloque que contiene dicha palabra desde la MP!

qQu pasara si siempre se produjeran fallos en la cach?!qPrincipio de localidad!


Aciertos y fallos en el acceso a la cach


!q Localidad espacial!

qSi se referencia un elemento, los elementos cercanos a l tambin tendern a ser referenciados!qLa jerarqua de memoria mueve bloque con palabras

contiguas en memoria a los niveles ms altos de la jerarqua!qOperaciones con matrices y arrays, ejecucin

secuencial de un programa!q Localidad temporal!

qSi se referencia un elemento, este tender a ser referencia pronto!qLa jerarqua de memoria mantiene los datos accedidos

recientemente lo ms cerca posible del procesador!qEstructura de los programas: datos y bucles!


Principio de localidad


!qRelacin entre MP y MV similar a la

existente entre MC y MP!qLa MP se divide en pginas o segmentos!qCuando se produce un fallo de pgina o

segmento, se debe acceder a la MV!qLa penalizacin en este caso es mayor

ya que la MV es la ms lenta de la jerarqua!qEn la gestin de este nivel interviene el

SO. El procesador realiza un cambio de contexto y ejecuta otra tarea hasta que la pgina o segmento est disponible en MP!


Aciertos y fallos en el acceso a la MP


!1. Se traduce la direccin virtual a una direccin fsica!2. Si se traduce con xito, es porque la palabra se encuentra en MP. Con esta

direccin se accede a la memoria cach!3. Tipos de fallos en la MC:!

q Iniciales, cuando se referencia una palabra por primera vez!q De capacidad, cuando se producen reemplazos!q De conflicto, varios bloques tienen asignada la misma ubicacin en

memoria cach!4. En caso de fallo, hay que pasar por el controlador de MP, que mapear la

direccin fsica buscada a la ubicacin fsica de la palabra dentro de los chips DRAM!

5. El controlador planificar el acceso a la MP puesto que otros dispositivos tambin acceden a la MP!

6. En caso de acierto, el bloque que incluye la palabra se enva a la MC!7. En caso de fallo, se debe resolver el fallo de pgina o segmento desde la

memoria virtual!8. El SO realiza un cambio de contexto y pasa a ejecutar otro proceso!9. Una vez que la pgina o el segmento est en MP, se lleva el bloque

correspondiente a MC y se reanuda la ejecucin de la instruccin que provoc el fallo!


Mecanismo completo de acceso a memoria


!qEn caso de tener dos niveles de MC, el mecanismo de

acceso es el mismo, salvo que cuando falla el acceso al primer nivel de cach, primero se intenta resolver desde el segundo!

qSi la palabra est en el segundo nivel, se enva el bloque completo al primer nivel, completando el acceso sin salir del chip del procesador!

qEn caso de fallo, se debe intentar desde MP!qSiguiendo el principio de inclusin, el bloque que

provoc el fallo se lleva desde la MP hasta la cach de segundo nivel, y desde sta, a la cach de primer nivel!

qEn el caso de un procesador segmentado, todo este proceso (hasta llegar a la MP) debera completarse en la etapa de acceso a memoria, es decir, en un nico ciclo de reloj!





Acceso a memoria del nanoMIPS en la etapa M


!tMEM = taciertoMC + TF pF!

!qtaciertoMC: Tiempo de acierto de la MC!qTF: Tasa de fallos de la MC !

TF = nm de fallos / nm total accesos a memoria!!

qpF: Penalizacin por fallo en MC !qNormalmente, el tiempo invertido en acceder a la

memoria se suma al tiempo de CPU!t = tCPU + tMEM!


Evaluacin de prestaciones de la jerarqua de memoria


!qMtricas que suelen utilizarse con la

memoria principal o la memoria virtual:!qLatencia: tiempo que transcurre desde que

un acceso a memoria comienza hasta que finaliza. Depende de la tecnologa con la que est fabricada la memoria!qAncho de banda: cantidad de informacin

por unidad de tiempo que puede transferirse desde/hacia la memoria. Depende de la organizacin de la memoria!


Evaluacin de prestaciones de la jerarqua de memoria


!qComparacin entre una tecnologa de

memoria perfecta y una jerarqua real!

qFrecuencia de reloj = 2 GHz!qCPI ideal de 1!q100 instrucciones!q2 MC, una de datos y otra de instrucciones,

ideales, nunca fallan!

t = tCPU = I CPI T = 100 1 1/2 109 = 50 ns!!


Ejemplo


!qSi la MC de instrucciones tiene una tasa de fallos

del 4% y una penalizacin por fallo de 100 ns, y la MC de datos tiene una talla se fallos del 6% y una penalizacin por fallo de 115 ns!qSi para ejecutar las 100 instrucciones hacen falta

100 accesos a la memoria de instrucciones y 25 a la de datos, el tiempo que se invierte en acceder a la memoria es:!

tMEM = n de acceso a MI(taciertoMI + TFMI pFMI)+ !n de acceso a MD(taciertoMD + TFMD pFMD)!

= 100(0 + 0.04 100) + 25(0 + 0.06 115) = 572,25 ns!qTiempo de CPU:!

t = tCPU + tMEM = 50 ns + 572,5 ns = 622,5 ns!!!


Diseo de la memoria cach


!qAlmacena unos determinados bloques de

informacin denominados marcos!qPara determinar qu bloque est ocupando un

determinado marco, se utilizan etiquetas o tags!qLas etiquetas se comparan con la del bloque

buscado para indicar si se ha producido un acierto o un fallo!qAspectos bsicos de su diseo!qOrganizacin de la memoria cach!qPoltica de ubicacin!qPoltica de reemplazo!qPoltica de escritura!




!qTamao de la memoria cach!qTamao de marco!qUnificacin o divisin de las

instrucciones y los datos!qImplementacin de cachs multinivel!


Organizacin de la memoria cach


!qDemasiado pequea!qIncrementa la tasa de fallos!qNo captura bien la localidad!qFallos de capacidad!

qDemasiado grande!qNo se podr integrar en el mismo chip

que el procesador debido al consumo de rea y de potencia!qMs lenta, ms comparaciones de

etiquetas!


Organizacin de la memoria cach: Tamao


!qBloques grandes!qSe captura mejor la localidad espacial!qSe reducen los fallos iniciales!q !qAumenta la penalizacin por fallo, se necesita

ms tiempo para traer los bloques del siguiente nivel!

qSe debe llegar a un compromiso teniendo en cuenta la latencia y el ancho de banda de conexin con el siguiente de la jerarqua!


Organizacin de la memoria cach: Marco


!qLa segmentacin del procesador obliga a

la divisin para evitar riesgos estructurales entra las etapas F y M!qCuando no se trata del primer nivel se

puede optar por unificar en bloques de informacin comunes las instrucciones y los datos!

qTodas estas decisiones se toman con ayuda de herramientas de simulacin y siguiendo reglas empricas y heursticas!


Organizacin de la memoria cach: Unificacin o divisin


!qAspecto que ms influye en el rendimiento!qMemoria cach de un nico nivel!qpequea y rpida o grande y lenta? Solucin: utilizar

ms de un nivel de memoria cach, normalmente dos niveles (algunas arquitecturas empiezan a utilizar tres niveles)!

qNivel 1 (L1): cercana al procesador, pequea y rpida!qNivel 2 (L2): mayor tamao, aprovecha el principio

de localidad, ms lenta pero menos fallos de capacidad!qLa penalizacin por fallo es menor, en lugar de ir a

MP ir a la cach de nivel 2!


Organizacin de la memoria cach: Multinivel


!qComparacin de una jerarqua de memoria

con una sola cach con otro jerarqua de memoria con dos niveles de cach!qProcesador con un nico nivel de cach

unificada!qTiempo de acceso: 1 ns!qTasa de fallos del 5%!qPenalizacin por fallos: 90 ns!qTiempo medio de acceso a memoria para

realizar una lectura:!tMEM (lectura) = taciertoL1 + TFL1 pFL1 = 1 + 0,05 90 = 5,5 ns!


Ejemplo


!qSegundo nivel de memoria cach!qTiempo de acceso: 12 ns!qTasa de fallos del 10%!qSuponemos que los movimientos de informacin

entre los dos niveles implican un tiempo despreciable!qTiempo medio de acceso a memoria para

realizar una lectura:!

tMEM (lectura) = taciertoL1 + TFL1 pFL1 = 1 + 0,05 pFL1!pFL1 = tL2 = taciertoL2 + TFL2 pFL2 = 12 + 0,1 90 = 21 ns!

tMEM (lectura) = 1 + 0,05 21 = 2,05 ns!Ganancia = 5,5/2,05 = 2,68!

!!


Ejemplo


!qLa memoria cach slo almacena

unos determinados bloques de informacin!qCualquier bloque puede alojarse en

cualquier marco?!qPoltica de ubicacin: tasa de fallos Vs

tiempo de acceso!qCorrespondencia directa!qTotalmente asociativa!qAsociativa por conjuntos!


Poltica de ubicacin


!q A cada bloque de memoria principal solo le

corresponde un marco de memoria cach!q Correspondencia entre memoria principal y cach!

qDireccin fsica: 19 bits!qTamao de bloque: 16 bytes (24)!qCapacidad MC: 2KB (2048B/16B = 128 bloques)!qCapacidad MP: 512KB (512KB/16B = 32.768 bloques)!

q Ejemplo: para ubicar el bloque 5 de MP en una MC de 128 marcos tendremos que realizar el mdulo!

Bloque 5 mod 128 marcos = marco 5!


Poltica de ubicacin: Correspondencia directa


Memoria cach



qVentajas!qLa lectura permite el acceso simultneo al directorio y a la palabra dentro del bloque de MC!qAlgoritmo de reemplazo trivial!

qInconvenientes!qIncremento de la tasa de fallos cuando dos bloques de MP correspondientes al mismo bloque de MC son accedidos de forma alternativa!

Memoria cach



qCualquier bloque de MP se puede ubicar en cualquier bloque de MC!

qLa etiqueta se compara con todas las etiquetas almacenadas en cach!

qVentajas !!qFlexibilidad, permite implantar gran variedad

de algoritmos de reemplazo!qPresenta la mayor tasa de aciertos!

qInconvenientes!qMayor tiempo de acceso!

Memoria cach

Poltica de ubicacin: Totalmente asociativa


Memoria cach

Poltica de ubicacin: Totalmente asociativa


q Dividir la MC en C conjuntos de B bloques o vas!q Se aplica:!

qCorrespondencia directa a nivel de conjuntos!qCorrespondencia asociativa a nivel de bloques!

q Solucin intermedia!q Reduce el tiempo de acceso de la memoria totalmente

asociativa e incrementa la tasa de aciertos de la directa!q Ajustar los valores de C y B!!q Ejemplo: para ubicar el bloque 5 de MP en una MC

asociativa de 64 conjuntos de 2 vas, tendremos que realizar el mdulo!

Bloque 5 mod 64 conjuntos = conjunto 5 !!

q uso de simuladores para determinar el diseo de cach que ms nos conviene!

Memoria cach

Poltica de ubicacin: Asociativa por conjuntos


Memoria cach

Poltica de ubicacin: Asociativa por conjuntos


Memoria cach

Ubicacin del bloque 12 con las tres polticas 498 Chapter 7 Large and Fast: Exploiting Memory Hierarchy

cache entry holds one block and each set has one element. A fully associativecache with m entries is simply an m-way set-associative cache; it has one set withm blocks, and an entry can reside in any block within that set.

The advantage of increasing the degree of associativity is that it usuallydecreases the miss rate, as the next example shows. The main disadvantage, whichwe discuss in more detail shortly, is an increase in the hit time.

FIGURE 7.13 The location of a memory block whose address is 12 in a cache with 8 blocks varies for direct-mapped, set-associative, and fully associative placement. In direct-mapped placement, there is only one cache block where memory block 12 can befound, and that block is given by (12 modulo 8) = 4. In a two-way set-associative cache, there would be four sets, and memory block 12 must be in set(12 mod 4) = 0; the memory block could be in either element of the set. In a fully associative placement, the memory block for block address 12 canappear in any of the eight cache blocks.

Direct mapped

2 4 5 760 1 3Block #

Data

Tag

Search

12

Set associative

20 1 3Set #

Data

Tag

Search

12

Fully associative

Data

Tag

Search

12


q Cuando se produce un fallo en MC hay que determinar qu bloque de MC desalojar para traer el bloque que ha producido el fallo desde MP!

q En el caso de una cach con correspondencia directa solo se puede desalojar un bloque!

q Dicha seleccin puede reducir la tasa de fallos de los accesos posteriores a MC!

q A tener en cuenta !!qProbabilidad de uso de una pgina!qCoste del intercambio (modificada?)!

q Algoritmos ms utilizados!qAleatorio!qFIFO!qLRU!

Memoria cach

Polticas de reemplazo


q Aleatorio: se utiliza un generador de nmeros aleatorios para escoger el bloque a reemplazar!qMs sencilla de implementar y la menos costosa!

q FIFO - First In First Out, reempleza el bloque que ha permanecido en MC el mayor periodo de tiempo!qMs costoso a medida que aumenta al nmero de

bloques, se debe mantener una lista ordenada!q LRU - Least Recently Used, reemplaza el bloque

de memoria que lleva ms tiempo sin utilizarse!qMs complejo y costoso en cuanto a recursos, pero es

el qu mejores resultados ofrece!q Tasa de aciertos Vs Tamao cach (nmero de

bloques)!

Memoria cach

Polticas de reemplazo


qLas escrituras llevan ms tiempo puesto que no se puede realizar trabajo en paralelo!qEn el caso de las lecturas, se recupera la informacin de un marco determinado al tiempo que se realiza la comparacin de las etiquetas!

qPolticas!qEscritura directa!q Post-escritura!

Memoria cach

Polticas de escritura


q Se escribe a la vez en el primer nivel de memoria cach y en el siguiente nivel de la jerarqua!

q En caso de fallo, se trae el bloque de MP a MC y una vez en esta, se procede a realizar la escritura!

q Ventajas!qFcil de implementar!qAsegura la coherencia!

q Inconvenientes!qSe genera mucho trfico a memoria!qEl procesador tiene que esperar (diferencia

tiempos de escritura en MC y MP) a que se complete la escritura!qSolucin: buffer de escritura!

Memoria cach

Polticas de escritura: Escritura Directa - Write through


q Cuando se modifica una palabra solo se hace en el primer nivel de cach!

q Para no actualizar la memoria con cada reemplazo, se activa un bit, el bit de sucio o dirty bit, que indicar si el bloque ha sido modificado o no!

q La escritura del bloque en MP se realiza cuando el bloque sucio en MC se reemplaza!

q Ventajas!qMenos trfico de informacin!qLos aciertos en escritura se llevan a cabo a la

velocidad de la MC!q Inconvenientes!

qDiseo ms complejo, requiere ms recursos!q Teniendo en cuenta posibles fallos transitorios de la MC,

es preferible la escritura directa!

Memoria cach

Polticas de escritura: Post-escritura - Write back


q Estructura hardware en la que se realizan las escrituras en primera instancia!

q Posteriormente se solapa la escritura con el siguiente nivel de la jerarqua con la ejecucin de las siguientes instrucciones!

q Estructura pequea y rpida organizada como una memoria cach!

q Las escrituras en el buffer suponen una penalizacin menor que hacerlas en el siguiente nivel de la jerarqua de memoria!

q Si el buffer est lleno, el procesador debe parar hasta que quede una posicin vaca!

Memoria cach

Buffer de escritura


!

qLas escrituras se hacen palabra a palabra en cach y en este buffer en lugar de en el siguiente nivel de la jerarqua de memoria!qEl contenido del buffer se volcar en

el siguiente nivel:!qCuando est lleno!qCuando se produzca un fallo de lectura y sea necesario actualizar el siguiente nivel con el contenido del buffer antes de resolver el fallo!

Memoria cach

Buffer de escritura: escritura directa


qEl buffer se utiliza para volcar los bloques sucios que van a ser reemplazados en memoria cach!

qNo hay que esperar a que se escriba el bloque sucio en el siguiente nivel, puesto que se almacena temporalmente en el buffer!

qEl contenido del buffer se volcar en el siguiente nivel:!qCuando est lleno!qCuando se produzca un fallo!

Memoria cach

Buffer de escritura: post-escritura


qSi el acceso a MC es para escritura y el bloque no se encuentra, se produce un fallo de escritura!

qEscritura con ubicacin (Write with allocate)!qSe asocia con post-escritura!qSe lleva el bloque de MP a MC donde se

realiza la escritura!qEscritura sin ubicacin (Write with no

allocate)!qSe asocia con escritura directa!qSlo se escribe sobre la MP!

Memoria cach

Polticas de escritura


qComparacin ancho de banda de MP consumido por las dos polticas de escritura!

qFrecuencia de reloj: 2,5 GHz!qAccesos a memoria: 2107!qnico nivel de MC unificada!qTasa de fallos MC: 12%!qTamao de bloque: 16 palabras!q70% lecturas, 30% escrituras!qMC con escritura directa!qEscritura con ubicacin!

Memoria cach

Ejemplo


q Ancho de banda consumido:!ABMP = referencias a memoria por segundo (%fallos lectura16

+ %aciertos escritura1 + %fallos escritura17) = !!2107(0,120,716 + 0,880,31 + 0,120,317) = !!4,44 107 palabras por segundo!

Memoria cach

Ejemplo (continuacin)

Tipo de acceso Acciones Trfico con MP

Acierto de lectura - Lectura MC 0

Fallo de lectura - Traer bloque de MP - Lectura en la MC

16 palabras

Acierto de escritura - Escritura en MC y en MP 1 palabra

Fallo de escritura - Traer bloque de MP - Escribir en la MC y en la MP

17 palabras


Memoria cach

Ejemplo (continuacin) Tipo de acceso Acciones Trfico con MP

Acierto de lectura - Lectura MC 0

Fallo de lectura, reemplazamiento bloque limpio

- Traer bloque de MP - Lectura en la MC

16 palabras

Fallo de lectura, reemplazamiento bloque sucio

- Escritura de bloque en MP - Traer bloque de MP - Lectura en MC

32 palabras

Acierto de escritura - Escritura en MC 0

Fallo de escritura, reemplazamiento bloque limpio

- Traer bloque de MP - Escritura en la MC

16 palabras

Fallo de escritura, reemplazamiento bloque sucio

- Escritura de bloque en MP - Traer bloque de MP - Escritura en MC

32 palabras


!q En post-escritura, el 10% de los bloques son

modificados cuando se encuentran ubicados en cach!

q Ancho de banda consumido:!ABMP = referencias a memoria por segundo (%fallos con reemplazamiento bloque limpio16 + %fallos

con reemplazamiento bloque sucio32) = !!2107(0,120,916 + 0,120,132) = !!4,22 107 palabras por segundo!

Memoria cach



!q Comparacin del tiempo medio de acceso a memoria con las

dos polticas de escritura!q T medio acceso a MC es de 4ns !q Latencia de acceso a MP es de 85ns!q Tamao bloque: 16 palabras!q MC con escritura directa!tMEM (lectura) = tacierto + TFpF!tMEM (escritura) = tacierto + latenciaMP + TFpF!!pF = 16(latenciaMP) = 16 (85) = 1360 ns!tMEM (lectura) = tacierto + TFpF = 4 + 0,12 1360 = 167,2 ns!tMEM (escritura) = tacierto + latenciaMP + TFpF = !

!4 + 85 + 0,12 1360 = 252,2 ns!!!

Memoria cach

Ejemplo


!q En media:!tMEM = %lectura tMEM (lectura) + %escritura tMEM (escritura) = 0,7 167,2 + 0,3 252,2 = 192,7 ns!

q Con las post-escritura tenemos el mismo comportamiento para lecturas y escrituras:!

tMEM = tacierto + TFpF !q Pero la penalizacin por fallo se modifica respecto de la

escritura directa!pF = 16(latenciaMP) + %sucios16(latenciaMP) = ! 1685 + 160,185 = 1496 ns!!tMEM = tacierto + TFpF = 4 + 0,12 1496 = 183,52 ns!!

Memoria cach



!q Diseo de una jerarqua de memoria con dos niveles de cach

unificados!qEl primer nivel de escritura directa!qEl segundo nivel de post-escritura con un 26% de bloques modificados!

q No se solapan accesos y transferencias!q L1, tamao de bloque de 8 palabras, t de acceso de 1 ns, talla de

fallos del 5%!q L2, tamao de bloque de 16 palabras, t de acceso de 9 ns, tasa de

fallos del 9%!q Transferencia de una palabra entre MP y L2 supone 0,5 ns!q Transferencia de una palabra entre L1 y L2 supone 0,1 ns!q Latencia acceso MP de 85 ns!tMEM (lectura) = taciertoL1 + TFL1pFL1!tMEM (escritura) = taciertoL1 + taciertoL2 + TFL1pFL1!pFL1 = 8 (tL2 + tbusL1L2)!tL2 = taciertoL2 + TFL2pFL2!!

Memoria cach

Ejemplo


!pFL2 = 16(latenciaMP + tbusL2MP) + 16%sucios(latenciaMP + tbusL2MP)!pFL2 = 16(0,85+0,5) + 160,26(0,85+0,5) = 1723,68 ns!tL2 = 9 + 0,09 1723,68 = 164,13 ns!pFL1 = 8 (164,13 + 0,1) = 1313,85 ns!!tMEM (lectura) = 1 + 0,051313,85 = 66,69 ns!tMEM (escritura) =1 + 9 + 0,051313,85 = 75,69 ns!!tMEM = %lectura tMEM (lectura) + %escritura tMEM (escritura) = !

!0,7 66,69 + 0,3 75,69 = 69,39 ns!!!

Memoria cach



!q Chips de memoria!

qMatrices cuadradas de celdas DRAM!qCada celda almacena un bit!

q El controlador de memoria gestiona los accesos!qDentro del propio procesador o en un chipset o hub

externo!q Mapea la direccin fsica a ubicacin fsica!

qChip o chips + matrices + filas + columnas Bits a recuperar!

q Evolucin de las diferentes tecnologas de memoria desde la DRAM convencional hasta las actuales DDR3!

Memoria principal

Diseo de la memoria principal


!q Modelo obsoleto!q Las actuales son el resultado de aplicar mejoras y

optimizaciones sobre la misma!q Proceso de acceso a memoria:!

qEl procesador vuelca la direccin en el bus !qEl controlador la decodifica!qDetermina el/los chip/s que deben ser accedidos y las

matrices dentro de los mismos!qEnva a las matrices la direccin de fila y columna para

validarlas!q Desaprovechamiento de recursos:!

qDespus de recuperar una fila para extraer una columna, si a continuacin queremos acceder a otro columna de esa misma fila, se vuelve a repetir todo el proceso !!

Memoria principal

DRAM convencional


!q Divisin de la memoria en pginas!q Los accesos que se encuentran en la misma

pgina requieren menos ciclos de espera!qCada pgina se corresponde justo con todas las celdas

en una misma fila de la matriz del chip de memoria!q Accesos en modo burst!

qUna vez accedida la columna, se puede acceder a las tres siguientes columnas de esa misma fila sin necesidad de volver a cargar la fila en el driver de datos!q5-3-3-3: 5 ciclos para el primer acceso, 3 para los

restantes!qSe fabricaban con tiempos de acceso de 70 60 ns y

fueron muy populares en sistemas basados en el 486 y los primeros Pentium!

Memoria principal

FPM DRAM: Fast Page Mode DRAM


!q Las tecnologas anteriores eran asincrnicas,

utilizaban sus propias seales de sincronizacin para realizar los accesos a memoria, introduciendo latencia y retardos innecesarios!

q La tecnologa de memoria actual es sncrona, utilizando el reloj global del sistema!

q Las memoria pueden funcionar en modo 5-1-1-1!q La industria se decant por las tecnologas

sncronas, ya que permiten construir integrados que funcionen a una frecuencia superior a 66 MHz!

q Tiempos de acceso de entre 25 y 10 ns!q Utilizada en los Pentium II y en los Pentium III , as

como en los AMD K6, AMD Athlon K7 y Duron!

Memoria principal

SDRAM o DRAM Sincrnica


!q DDR (Double Date Rate) transfiere informacin dos

veces en cada ciclo de reloj: en el flanco de subida y en el de bajada!

q Con esta tcnica se llegan por primera vez a los 400MHz!

q DDR2 permite trabajar a mayores frecuencias!q Para trabajar a frecuencias tan altas y no tener

problemas con el calor, se reduce la tensin de alimentacin a 1,8 V!

q Para seguir aumentando la frecuencia hasta los 1900 MHz, la tecnologa DDR3 reduce de nuevo la tensin de alimentacin !

Memoria principal

DDR, DDR2, DDR3


!q La memoria virtual se introduce en la jerarqua de memoria

porque:!qPermite la multiprogramacin proteccin!qPermite ejecutar procesos ms grandes que la MP!qPermite independencia de las referencias con

respecto a la localizacin de los procesos en MP!q La MV no se controla exclusivamente por hardware!q La tecnologa de la MV es el almacenamiento magntico!q La unidad de informacin no es el bloque, sino el

segmento o la pgina, mucho mayores que el bloque que se maneja entre MC y MP!

q El alojamiento es siempre asociativo !q La poltica de escritura es siempre post-escritura!

Memoria virtual

Diseo de la memoria virtual


!q Ms compleja y difcil de gestionar!q Latencia del orden de ms y no de ns!q Resolver un fallo de pgina implica un cambio de contexto para

evitar la enorme penalizacin por fallo!q Decisiones clave a la hora de disear un sistema de memoria virtual:!q El tamao de la pgina debe ser lo suficientemente grande para

amortizar el elevado tiempo de acceso!q Tamao tpico entre 4KB y 16KB!q Nuevos servidores y desktops se estn desarrollando para soportar pginas de

32KB y 64KB!q Los nuevos sistemas empotrados utilizan pginas de 1KB!

q Priman las polticas que reducen el nmero de fallos de pagina, por eso la tcnica de alojamiento empleada es totalmente asociativa!

q Los fallos de pgina se manejan por software, puesto que la sobrecarga introducida por estos algoritmos es mucho menor que el tiempo de acceso a disco!

q La escritura-directa queda descartada en MV. En su lugar se emplea post-escritura!

Memoria virtual

Diseo de la memoria virtual


!qDireccin virtual direccin

generada por el procesador!qDireccin fsica direccin que

maneja la unidad de memoria!qMemory Management Unit (MMU):!qTraduce direcciones virtuales a

direcciones fsicas!qTrabaja en tiempo de ejecucin de

manera transparente a la CPU!

Memoria virtual

Organizacin de la memoria virtual


Memoria virtual


512 Chapter 7 Large and Fast: Exploiting Memory Hierarchy

overlay that was not loaded and that the overlays loaded never exceeded the totalsize of the memory. Overlays were traditionally organized as modules, each con-taining both code and data. Calls between procedures in different modules wouldlead to overlaying of one module with another.

As you can well imagine, this responsibility was a substantial burden on pro-grammers. Virtual memory, which was invented to relieve programmers of thisdifficulty, automatically manages the two levels of the memory hierarchy repre-sented by main memory (sometimes called physical memory to distinguish it fromvirtual memory) and secondary storage.

Although the concepts at work in virtual memory and in caches are thesame, their differing historical roots have led to the use of different termin-ology. A virtual memory block is called a page, and a virtual memory miss iscalled a page fault. With virtual memory, the processor produces a virtualaddress, which is translated by a combination of hardware and software to aphysical address, which in turn can be used to access main memory.Figure 7.19 shows the virtually addressed memory with pages mapped to mainmemory. This process is called address mapping or address translation. Today,the two memory hierarchy levels controlled by virtual memory are DRAMs

FIGURE 7.19 In virtual memory, blocks of memory (called pages) are mapped from oneset of addresses (called virtual addresses) to another set (called physical addresses).The processor generates virtual addresses while the memory is accessed using physical addresses. Both thevirtual memory and the physical memory are broken into pages, so that a virtual page is really mapped to aphysical page. Of course, it is also possible for a virtual page to be absent from main memory and not bemapped to a physical address, residing instead on disk. Physical pages can be shared by having two virtualaddresses point to the same physical address. This capability is used to allow two different programs to sharedata or code.

page fault An event that occurs when an accessed page is not present in main memory.

virtual address An address that corresponds to a location in virtual space and is translated by address mapping to a physical address when memory is accessed.

address translation Alsocalled address mapping. The process by which a virtual address is mapped to an address used to access memory.

Virtual addresses Physical addressesAddress translation

Disk addresses


Memoria virtual


7.4 Virtual Memory 513

and magnetic disks (see Chapter 1, pages 5, 13 and 23). If we return to ourlibrary analogy, we can think of a virtual address as the title of a book and aphysical address as the location of that book in the library, such as might begiven by the Library of Congress call number.

Virtual memory also simplifies loading the program for execution by provid-ing relocation. Relocation maps the virtual addresses used by a program to dif-ferent physical addresses before the addresses are used to access memory. Thisrelocation allows us to load the program anywhere in main memory. Further-more, all virtual memory systems in use today relocate the program as a set offixed-size blocks (pages), thereby eliminating the need to find a contiguousblock of memory to allocate to a program; instead, the operating system needonly find a sufficient number of pages in main memory. Formerly, relocationproblems required special hardware and special support in the operating sys-tem; today, virtual memory also provides this function.

In virtual memory, the address is broken into a virtual page number and a pageoffset. Figure 7.20 shows the translation of the virtual page number to a physicalpage number. The physical page number constitutes the upper portion of thephysical address, while the page offset, which is not changed, constitutes the lower

FIGURE 7.20 Mapping from a virtual to a physical address. The page size is 212 = 4 KB. Thenumber of physical pages allowed in memory is 218, since the physical page number has 18 bits in it. Thus,main memory can have at most 1 GB, while the virtual address space is 4 GB.

Virtual page number Page offset

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

Physical page number Page offset

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

Virtual address

Physical address

Translation


!

qTres mtodos de asignacin de memoria !qPaginacin: tamao fijo de bloque de informacin!qSegmentacin: tamao variable de bloque de informacin!qTcnica hbrida, paginada/segmentada: los segmentos se componen de un nmero entero de pginas!

Memoria virtual

Asignacin de memoria


!q La paginacin se gestiona adems de con el

hardware, con la colaboracin del SO!q Es tan importante reducir los fallos de pgina que

los diseadores se centran en desarrollar algoritmos de ubicacin de pginas lo ms ptimos posible!

q El problema de utilizar ubicacin totalmente asociativa radica en localizar una entrada: una bsqueda completa es impracticable!!

q En su lugar, se localizan las pginas por medio de unas tablas que indexan la memoria!

q A esta estructura se la denomina tabla de pginas y reside en memoria!

Memoria virtual

Paginacin


!q El espacio de direcciones virtuales de un proceso

no es contiguo, pudiendo alojarse en cualquier posicin de memoria fsica!

q La memoria fsica se divide en bloques de tamao fijo denominados marcos!

q La memoria virtual se divide en bloques del mismo tamao denominados pginas!

q Se mantiene una lista de todos los marcos libres!q Para ejecutar un programa de n pginas, hay que

encontrar n marcos libres y cargar el programa!q Despus, se debe inicializar la tabla de pginas

para traducir direcciones virtuales a fsicas!

Memoria virtual

Paginacin


!q Debido a la utilizacin de una poltica de ubicacin totalmente

asociativa, el SO puede implementar algoritmos de reemplazo ms inteligentes para reducir los fallos de pgina !

q La verdadera dificultad radica en encontrar una entrada: una bsqueda exhaustiva es impracticable!

q En su lugar se emplea una tabla de pginas que reside en memoria:!q Indexada con el nmero de pgina de la direccin virtual!q Permite obtener la pgina fsica en la que se ubica la pgina

virtual buscada!q Cada programa del sistema tiene su propia tabla de pginas!q Para indicar la localizacin de la tabla de pginas en MP, el

hardware incluye un registro que apunta al comienzo de la tabla de pginas, el page table register!

Memoria virtual

Ubicacin y bsqueda de pginas


!q Para evitar colisiones entre el espacio de

direcciones virtuales de los distintos procesos, el SO se encarga de:!q La asignacin de la memoria fsica!q Actualizar las tablas de pginas proteccin!

q Un bit de vlido se utiliza en cada entrada de la tabla de pginas para indicar si la pgina est o no presente en la MP:!q Off la pgina no est presente en MP, fallo de pgina!q On la pgina est presente en MP, acceso a la MC!

Memoria virtual

Ubicacin y bsqueda de pginas


Memoria virtual

Esquema de traduccin de direcciones 7.4 Virtual Memory 517

Because we do not know ahead of time when a page in memory will be chosento be replaced, the operating system usually creates the space on disk for all thepages of a process when it creates the process. This disk space is called the swapspace. At that time, it also creates a data structure to record where each virtualpage is stored on disk. This data structure may be part of the page table or may bean auxiliary data structure indexed in the same way as the page table. Figure 7.22

FIGURE 7.21 The page table is indexed with the virtual page number to obtain the corresponding portion of the physicaladdress. The starting address of the page table is given by the page table pointer. In this figure, the page size is 212 bytes, or 4 KB. The virtual addressspace is 232 bytes, or 4 GB, and the physical address space is 230 bytes, which allows main memory of up to 1 GB. The number of entries in the pagetable is 220, or 1 million entries. The valid bit for each entry indicates whether the mapping is legal. If it is off, then the page is not present in memory.Although the page table entry shown here need only be 19 bits wide, it would typically be rounded up to 32 bits for ease of indexing. The extra bitswould be used to store additional information that needs to be kept on a per-page basis, such as protection.

Virtual page number Page offset

3 1 3 0 2 9 2 8 2 7 3 2 1 01 5 1 4 1 3 1 2 1 1 1 0 9 8

Physical page number Page offset

2 9 2 8 2 7 3 2 1 01 5 1 4 1 3 1 2 1 1 1 0 9 8

Virtual address

Physical address

Page table register

Physical page numberValid

Page table

If 0 then page is notpresent in memory

20 12

18

swap space The space on thedisk reserved for the full virtual memory space of a process.


!

Memoria virtual

Esquema de traduccin de direcciones


!q Si el bit de vlido est a off se produce un fallo de pgina!q Se debe transferir el control al SO: mecanismo de excepcin!q Una vez que el SO tiene el control debe:!q Buscar la pgina en el siguiente nivel de la jerarqua, en

el disco magntico!q Decidir en qu marco de MP alojar la pgina!

q Se debe llevar un control de la localizacin en el disco de las pginas virtuales!

q El SO reserva espacio en disco para todas las pginas de un proceso: swap space!

q Al mismo tiempo crea una estructura de datos para almacenar la ubicacin en el disco de cada pgina virtual!

q Esta nueva estructura puede formar parte de la tabla de pginas o ser una estructura auxiliar tambin indexada!

Memoria virtual

Fallo de pgina


Memoria virtual

Fallo de pgina


shows the organization when a single table holds either the physical page numberor the disk address.

The operating system also creates a data structure that tracks which processesand which virtual addresses use each physical page. When a page fault occurs, if allthe pages in main memory are in use, the operating system must choose a page toreplace. Because we want to minimize the number of page faults, most operatingsystems try to choose a page that they hypothesize will not be needed in the nearfuture. Using the past to predict the future, operating systems follow the leastrecently used (LRU) replacement scheme, which we mentioned in Section 7.3.The operating system searches for the least recently used page, making theassumption that a page that has not been used in a long time is less likely to beneeded than a more recently accessed page. The replaced pages are written to swapspace on the disk. In case you are wondering, the operating system is just another

FIGURE 7.22 The page table maps each page in virtual memory to either a page inmain memory or a page stored on disk, which is the next level in the hierarchy. The vir-tual page number is used to index the page table. If the valid bit is on, the page table supplies the physicalpage number (i.e., the starting address of the page in memory) corresponding to the virtual page. If thevalid bit is off, the page currently resides only on disk, at a specified disk address. In many systems, thetable of physical page addresses and disk page addresses, while logically one table, is stored in two sepa-rate data structures. Dual tables are justified in part because we must keep the disk addresses of all thepages, even if they are currently in main memory. Remember that the pages in main memory and thepages on disk are identical in size.

Page tablePhysical page or

disk addressPhysical memory

Virtual pagenumber

Disk storage

1111011

11

1

0

0

Valid


!q El SO mantiene otra estructura de datos en la que almacena

qu procesos y qu direcciones virtuales utiliza cada pgina fsica!

q Cuando todas las pginas fsicas estn ocupadas, la mayora de los SSOO emplean una aproximacin del algoritmo LRU (Least Recently Used) para reemplazar una pgina que lleva cierto tiempo sin ser referenciada!

q Para ayudar al SO, algunos ordenadores proporcionan el bit de referencia o bit de uso, que se pone a 1 cuando se accede a la pgina!

q Si la pgina a reemplazar ha sido modificada, en los sistemas de MV se emplea write-back, de tal manera que la pgina se modifica en cada escritura en MP y solo se copia en el disco duro cuando es sustituida!

q Para saber si una pgina ha sido modificada, a la tabla de pginas se le aade el dirty bit!

Memoria virtual

Fallo de pgina


!q Cuando varios procesos compartan la MP, se debe evitar la lectura o

escritura en zonas de memoria que no pertenecen a un proceso!q Un bit de permiso de escritura en el TLB puede proteger a una pgina de ser

escrita!q El hardware debe proporcionar al SO los siguientes mecanismos:!q Soportar dos modos de ejecucin: supervisor y usuario!q Proporcionar una parte del estado del procesador en modo slo lectura

de tal manera que el usuario no la pueda escribir:!q Bit de modo usuario/supervisor!q Puntero de tabla de pginas!q TLB!

Para modificar estos elementos, el SO utiliza instrucciones especiales slo disponibles en modo supervisor!q Proporcionar mecanismos para cambiar de modo usuario a modo

supervisor, como por ejemplo, las llamadas al sistema: syscall exception!q Se salva el PC en el registro EPC!q Se pone el procesador en modo supervisor!q Para volver en modo usuario a la direccin almacenada en el EPC,

se utiliza la instruccin ERET q Las tablas de pginas se almacenan en el espacio de direcciones del SO!

Memoria virtual

Proteccin


!q Como las tablas de pginas estn almacenadas en

la MP, cada acceso a la memoria por un programa implica al menos dos accesos a memoria!

q Debido al principio de localidad, sabemos que las palabras de una pgina sern referenciadas pronto, por lo que la traduccin de una pgina virtual a fsica debera conservarse!

q Es por esto que los procesadores actuales incluyen una cach especial que mantiene las traducciones recientemente utilizadas!

q A esta cach de traduccin de direcciones se la conoce comnmente como translation-lookaside buffer (TLB)!

Memoria virtual

Optimizacin de la traduccin de direcciones: TLB


Memoria virtual

Hardware de paginacin con TLB


Accordingly, modern processors include a special cache that keeps track ofrecently used translations. This special address translation cache is traditionallyreferred to as a translation-lookaside buffer (TLB), although it would be moreaccurate to call it a translation cache. The TLB corresponds to that little piece ofpaper we typically use to record the location of a set of books we look up in thecard catalog; rather than continually searching the entire catalog, we record thelocation of several books and use the scrap of paper as a cache of Library of Con-gress call numbers.

Figure 7.23 shows that each tag entry in the TLB holds a portion of the virtualpage number, and each data entry of the TLB holds a physical page number. Becausewe will no longer access the page table on every reference, instead accessing the TLB,the TLB will need to include other bits, such as the dirty and the reference bit.

translation-lookaside buffer (TLB) A cache that keeps track of recently used address map-pings to avoid an access to the page table.

FIGURE 7.23 The TLB acts as a cache on the page table for the entries that map to physical pages only. The TLB contains a sub-set of the virtual-to-physical page mappings that are in the page table. The TLB mappings are shown in color. Because the TLB is a cache, it must havea tag field. If there is no matching entry in the TLB for a page, the page table must be examined. The page table either supplies a physical page numberfor the page (which can then be used to build a TLB entry) or indicates that the page resides on disk, in which case a page fault occurs. Since the pagetable has an entry for every virtual page, no tag field is needed; in other words, it is not a cache,

1111011

11

1

0

0

1000000

11

1

0

0

1001011

11

1

0

0

Physical pageor disk addressValid Dirty Ref

Page table

Physical memory

Virtual pagenumber

Disk storage

111101

011000

111101

Physical pageaddressValid Dirty Ref

TLB

Tag


!q En cada referencia a memoria, primero buscamos si la traduccin est en el

TLB.!q TLB Hit: la traduccin s est en el TLB!

q Nos ahorramos el acceso a memoria para consultar la tabla de pginas.!q Se comprueba el bit de vlido, si es 0 page fault, la pgina no est en memoria.

El procesador genera una excepcin para invocar al SO y que ste resuelva el fallo de pgina.!

q Si el bit de vlido est a 1, se procede a actualizar el bit de referencia y el de sucio (slo en caso de escritura).!

q TLB Miss: la traduccin no est en el TLB, se genera una excepcin !q No nos ahorramos el acceso a memoria.!q Traemos la traduccin de la tabla de pginas sin comprobar el bit de vlido. !q Se re-ejecuta la instruccin, pero en este caso la traduccin s que estar.!q El TLB miss se puede atender tanto por hardware como por software.!

q En el TLB se utiliza write-back, de tal manera que los bits con informacin solo se copian en la tabla de pginas cuando la entrada en el TLB es reemplazada!

q Los diseadores de TLBs utilizan diferentes combinaciones:!q LRU por hardware es demasiado caro, tampoco por software!q Muchos sistemas dan soporte para seleccin de una entrada aleatoria

(random).!

Memoria virtual

Optimizacin de la traduccin de direcciones: TLB


!

q Registros de control de MIPS: estn en el coprocesador 0. !q Se leen por medio de la instruccin mfc0 y se escriben con mtc0

Memoria virtual

TLB miss 532 Chapter 7 Large and Fast: Exploiting Memory Hierarchy

Once the operating system knows the virtual address that caused the page fault,it must complete three steps:

1. Look up the page table entry using the virtual address and find the locationof the referenced page on disk.

2. Choose a physical page to replace; if the chosen page is dirty, it must be writ-ten out to disk before we can bring a new virtual page into this physical page.

3. Start a read to bring the referenced page from disk into the chosen physicalpage.

Register CP0 register number Description

EPC 14 Where to restart after exceptionCause 13 Cause of exceptionBadVAddr 8 Address that caused exceptionIndex 0 Location in TLB to be read or writtenRandom 1 Pseudorandom location in TLBEntryLo 2 Physical page address and flagsEntryHi 10 Virtual page addressContext 4 Page table address and page number

FIGURE 7.27 MIPS control registers. These are considered to be in coprocessor 0, and hence areread using mfc0 and written using mtc0.

HardwareSoftwareInterface

Between the time we begin executing the exception handler in the operating sys-tem and the time that the operating system has saved all the state of the process,the operating system is particularly vulnerable. For example, if another excep-tion occurred when we were processing the first exception in the operating sys-tem, the control unit would overwrite the exception program counter, making itimpossible to return to the instruction that caused the page fault! We can avoidthis disaster by providing the ability to disable and enable exceptions. When anexception first occurs, the processor sets a bit that disables all other exceptions;this could happen at the same time the processor sets the supervisor mode bit.The operating system will then save just enough state to allow it to recover ifanother exception occursnamely, the exception program counter and Causeregister. EPC and Cause are two of the special control registers that help withexceptions, TLB misses, and page faults; Figure 7.27 shows the rest. The operatingsystem can then reenable exceptions. These steps make sure that exceptions willnot cause the processor to lose any state and thereby be unable to restart executionof the interrupting instruction.

exception enable Also called interrupt enable. A signal or action that controls whether the process responds to an excep-tion or not; necessary for pre-venting the occurrence of exceptions during intervals before the processor has safely saved the state needed to restart.


!q Cdigo MIPS para un manejador tpico de un fallo de TLB:!

!!!q Instrucciones especiales para actualizar el TLB:!q tlbwr copia el registro de control EntryLo en la entrada del TLB

seleccionada por el registro de control Random q Random implementa un algoritmo de reemplazo aleatorio!q $k1 y $k0 son registros temporales utilizados por el kernel sin

necesidad de salvarlos!q El SO carga la entrada en el TLB sin comprobarla y re-

ejecuta la instruccin!q Si la entrada resulta ser invlida, se genera un fallo de pgina!

!!!

Memoria virtual

TLB miss


the page table using the page number of the virtual address and the page table regis-ter, which indicates the starting address of the active process page table. To make thisindexing fast, MIPS hardware places everything you need in the special Contextregister: the upper 12 bits have the address of the base of the page table and the next18 bits have the virtual address of the missing page. Each page table entry is oneword, so the last 2 bits are 0. Thus, the first two instructions copy the Context regis-ter into the kernel temporary register $k1 and then load the page table entry fromthat address into $k1. Recall that $k0 and $k1 are reserved for the operating systemto use without saving; a major reason for this convention is to make the TLB misshandler fast. Below is the MIPS code for a typical TLB miss handler:

TLBmiss:mfc0 $k1,Context # copy address of PTE into temp $k1lw $k1, 0($k1) # put PTE into temp $k1mtc0 $k1,EntryLo # put PTE into special register EntryLotlbwr # put EntryLo into TLB entry at Randomeret # return from TLB miss exception

As shown above, MIPS has a special set of system instructions to update theTLB. The instruction tlbwr copies from control register EntryLo into the TLBentry selected by the control register Random. Random implements randomreplacement, so it is basically a free-running counter. A TLB miss takes about adozen clock cycles.

Note that the TLB miss handler does not check to see if the page table entry isvalid. Because the exception for TLB entry missing is much more frequent than apage fault, the operating system loads the TLB from the page table without exam-ining the entry and restarts the instruction. If the entry is invalid, another and dif-ferent exception occurs, and the operating system recognizes the page fault. Thismethod makes the frequent case of a TLB miss fast, at a slight performance pen-alty for the infrequent case of a page fault.

Once the process that generated the page fault has been interrupted, it transferscontrol to 8000 0180hex, a different address than TLB miss handler. This is thegeneral address for exception; TLB miss has a special entry point to lower the pen-alty for a TLB miss. The operating system uses the exception Cause register todiagnose the cause of the exception. Because the exception is a page fault, theoperating system knows that extensive processing will be required. Thus, unlike aTLB miss, it saves the entire state of the active process. This state includes all thegeneral-purpose and floating-point registers, the page table address register, theEPC, and the exception Cause register. Since exception handlers do not usuallyuse the floating-point registers, the general entry point does not save them, leav-ing that to the few handlers that need them.

Figure 7.28 sketches the MIPS code of an exception handler. Note that we saveand restore the state in MIPS code, taking care when we enable and disable excep-tions, but we invoke C code to handle the particular exception.


!qLos fallos de pgina en el acceso a datos son ms complicados:!

1. Ocurren en mitad de la ejecucin de la instruccin!2. La instruccin no se puede completar antes de resolver la

excepcin!3. Despus de tratar la excepcin, la instruccin debe comenzar su

ejecucin de nuevo como si nada hubiera ocurrido!qEn este caso, las instrucciones deben ser rearrancables, algo sencillo en la arquitectura MIPS!qCuando se produce un TLB miss:!q El hardware del MIPS salva el nmero de pgina en el registro

BadVAddr q Genera una excepcin!

qLa excepcin invoca al SO, que trata el fallo va software!q Se transfiere el control a la direccin 0X8000 0000, la direccin

de la rutina software (handler, manejador) encargada de tratar el TLB miss!

!!

Memoria virtual

TLB miss


!q Cuando se produce un fallo de pgina se transfiere

el control a la direccin 0X8000 0180!q Direccin general para una excepcin!q El TLB miss tiene un punto de entrada especial

para reducir la penalizacin por fallo del TLB!q El SO utiliza el registro Cause para determinar

la causa de la excepcin!q Como se trata de un fallo de pgina:!q El SO salva el estado del proceso activo:

registros de propsito general, de coma flotante, registro de direccin de tabla de pginas y los registros EPC y Cause

Memoria virtual

Fallo de pgina


Memoria virtual 7.4 Virtual Memory 535

The virtual address that caused the fault depends on whether the fault was aninstruction or data fault. The address of the instruction that generated the fault is inthe EPC. If it was an instruction page fault, the EPC contains the virtual address of thefaulting page; otherwise, the faulting virtual address can be computed by examiningthe instruction (whose address is in the EPC) to find the base register and offset field.

Save state

Save GPR addi $k1,$sp, -XCPSIZE # save space on stack for statesw $sp, XCT_SP($k1) # save $sp on stacksw $v0, XCT_V0($k1) # save $v0 on stack... # save $v1, $ai, $si, $ti, ...on stacksw $ra, XCT_RA($k1) # save $ra on stack

Save Hi, Lo mfhi $v0 # copy Himflo $v1 # copy Losw $v0, XCT_HI($k1) # save Hi value on stacksw $v1, XCT_LI($k1) # save Lo value on stack

Save Exception Registers

mfc0 $a0, $cr # copy cause registersw $a0, XCT_CR($k1) # save $cr value on stack... # save $v1, ....mfc0 $a3, $sr # copy Status Registersw $a3, XCT_SR($k1) # save $sr on stack

Set sp move $sp, $k1 # sp = sp - XCPSIZE

Enable nested exceptions

andi $v0, $a3, MASK1 # $v0 = $sr & MASK1, enable exceptionsmtc0 $v0, $sr # $sr = value that enables exceptions

Call C exception handler

Set $gp move $gp, GPINIT # set $gp to point to heap area

Call C code move $a0, $sp # arg1 = pointer to exception stackjal xcpt_deliver # call C code to handle exception

Restoring state

Restore most GPR, Hi, Lo

move $at, $sp # temporary value of $splw $ra, XCT_RA($at) # restore $ra from stack... # restore $t0, ...., $a1lw $a0, XCT_A0($k1) # restore $a0 from stack

Restore Status Register

lw $v0, XCT_SR($at) # load old $sr from stackli $v1, MASK2 # mask to disable exceptionsand $v0, $v0, $v1 # $v0 = $sr & MASK2, disenable exceptionsmtc0 $v0, $sr # set Status Register

Exception return

Restore $sp and rest of GPR used as temporary registers

lw $sp, XCT_SP($at) # restore $sp from stacklw $v0, XCT_V0($at) # restore $v0 from stacklw $v1, XCT_V1($at) # restore $v1 from stacklw $k1, XCT_EPC($at) # copy old $epc from stacklw $at, XCT_AT($at) # restore $at from stack

Restore ERC and return

mtc0 $k1, $epc # restore $epceret $ra # return to interrupted instruction

FIGURE 7.28 MIPS code to save and restore state on an exception.


!q Si un programa accede a una MV mayor que la MP

disponible, se ejecutar muy despacio!q Dicho programa estar intercambiando pginas

constantemente entre la memoria y el disco, thrashing!

q Si un programa entra en thrashing, lo mejor es ejecutar dicho programa en una mquina con ms memoria o aadir ms memoria a la actual!

q Otra alternativa es redisear los algoritmos y las estructuras de datos de nuestro programa para tratar de reducir el nmero de pginas que un programa utiliza de forma simultnea, reducir el working set

Memoria virtual

Thrashing Working set

Documents

T5-Memorias