BOLGestionMemoriaACSoluciones

Vista previa del material en texto

3
ARQUITECTURA DE COMPUTADORES. 2º INGENIERÍA INFORMÁTICA. 
SOLUCIONES Problemas de Gestión de Memoria. 
 
 
1. Antes de ver en qué entradas de la memoria caché van a ir los bloques asociados a las referencias 
que nos dan y ver los aciertos y fallos que se producen vamos a ver como serían las direcciones de 
memoria principal (MP) y cómo se interpretarían en función de la organización de la memoria 
caché: 
 
a) Si el tamaño de la palabra es de 16 bits y los bloques son de una sola palabra el campo de 
desplazamiento dentro del bloque tendrá un sólo bit para acceder al byte dentro de la palabra. 
Como nos dicen 32 entradas y es de correspondencia directa necesitaremos 5 bits para acceder 
a la entrada en la caché. Los bits del campo etiqueta se deducen de restar los bits necesarios 
para direccionar una posición de memoria (16 bits) de la suma de los anteriores campos. Así 
una dirección de MP será interpretada por la caché de la siguiente manera: 
 
 
 
 
 
b) Análogamente a como hemos razonado en el apartado a) deducimos el esquema de direcciones 
de esta caché. Hay que fijarse que la dirección siempre será de longitud 16 bits 
independientemente de cómo se interprete ya que ese es el tamaño de una dirección a MP. 
 
 
 
 
c) 
 
 
 
d) 
 
 
 
 
 
Ahora para cada caso iremos viendo a qué bloques de la MP se accede. Esos bloques habrán de ser 
traídos de la MP a la memoria caché y ubicados en unas determinadas líneas en función de su 
organización interna. 
 
En la tabla que se muestra a continuación se ha escrito para cada caso a qué entrada o conjunto irá 
el bloque que se trae de memoria principal. En el caso de las memorias asociativas por conjuntos de 
dos vías se indica el conjunto y el elemento dentro del conjunto separado por un guión. Entre 
paréntesis se ha escrito si ese acceso a memoria ha supuesto un acierto o fallo de caché. Sólo se 
produce un caso de fallo de bloque debido a un problema de conflicto en el caso de la caché con 
correspondencia directa en el acceso 11. El resto son todos forzosos. Nótese que en el caso c) al ser 
el bloque más grande da como resultado una disminución en el número de fallos de bloque 
(forzosos). 
De esta tabla también se puede deducir el estado final de la memoria caché: 
10 5 1 
Etiqueta Índice byte
11 4 1 
Etiqueta Conjunto byte
9 4 2 1 
Etiqueta Conjunto word byte 
15 1 
Etiqueta byte 
 
 4
- En el caso de la caché de correspondencia directa (mapeado directo) se traen 13 bloques y 
se producen también 13 fallos. Las 12 entradas, en este caso líneas ocupadas, son la 0, 2, 3, 
4, 5, 8, 9, 10, 12, 18, 21, y 28. Para saber los valores de las etiquetas que se guardan en la 
memoria caché no hay más que tomar los 10 primeros bits de la referencia empezando por 
la izquierda (ver esquema de direcciones). En el caso del acceso 11 se produce un fallo por 
conflicto con el bloque traído en el acceso 0. Hay 13 fallos pero se van a quedar 12 bloques. 
Por lo tanto será la etiqueta del bloque asociado al acceso 11 la que finalmente quede en la 
memoria caché. 
- Análogamente al caso anterior, en el caso b) las 13 líneas de la memoria caché ocupadas 
son: 0 (0-0), 4 (2-0), 8 (4-0), 20 (10-0), 16 (8-0), 18 (9-0), 5 (2-1), 24 (12-0), 1 (0-1), 10 (5-
0), 11 (5-1), 6 (3-0) y 25 (12-1). También se traen 13 bloques de MP y se producen 13 
fallos. 
- En el caso c) se producen 8 fallos de caché y se traen 8 bloques de MP. Las líneas ocupadas 
son: 0 (0-0), 2 (1-0), 4 (2-0), 8 (4-0), 14 (7-0), 16 (8-0), 10 (5-0) y 6 (3-0). 
- En el caso d) se producen 13 fallos, uno por bloque. Las entradas en este caso, al igual que 
en la correspondencia directa, son las propias líneas de la caché. Los bloques de MP se van 
almacenando de forma secuencial en la memoria caché ya que pueden ir ubicados en 
cualquier posición. 
 
Nº 
Acceso 
Dirección 
en hex. 
Dirección en 
binario C. Directa 
A. 2 vías 
(conjunto-
línea en 
conjunto) 
A. 2 vías 
con 4 
palabras 
por bloque 
Totalmente 
asociativo 
1 1 0...0 0000 0001 0 (F) 0 – 0 (F) 0 – 0 (F) 0 (F) 
2 4 0...0 0000 0100 2 (F) 2 – 0 (F) 0 – 0 (A) 1 (F) 
3 8 0...0 0000 1000 4 (F) 4 – 0 (F) 1 – 0 (F) 2 (F) 
4 5 0...0 0000 0101 2 (A) 2 – 0 (A) 0 – 0 (A) 1 (A) 
5 14 0...0 0001 0100 10 (F) 10 – 0 (F) 2 – 0 (F) 3 (F) 
6 11 0...0 0001 0001 8 (F) 8 – 0 (F) 2 – 0 (A) 4 (F) 
7 13 0...0 0001 0011 9 (F) 9 – 0 (F) 2 – 0 (A) 5 (F) 
8 24 0...0 0010 0100 18 (F) 2 – 1 (F) 4 – 0 (F) 6 (F) 
9 38 0...0 0011 1000 28 (F) 12 – 0 (F) 7 – 0 (F) 7 (F) 
10 9 0...0 0000 1001 4 (A) 4 – 0 (A) 1 – 0 (A) 2 (A) 
11 41 0...0 0100 0001 0 (F) 0 – 1 (F) 8 – 0 (F) 8 (F) 
12 B 0...0 0000 1011 5 (F) 5 – 0 (F) 1 – 0 (A) 9 (F) 
13 4 0...0 0000 0100 2 (A) 2 – 0 (A) 0 – 0 (A) 1 (A) 
14 2B 0...0 0010 1011 21 (F) 5 – 1 (F) 5 – 0 (F) 10 (F) 
15 5 0...0 0000 0101 2 (A) 2 – 0 (A) 0 – 0 (A) 1 (A) 
16 6 0...0 0000 0110 3 (F) 3 – 0 (F) 0 – 0 (A) 11 (F) 
17 9 0...0 0000 1001 4 (A) 4 – 0 (A) 1 – 0 (A) 2 (A) 
18 11 0...0 0001 0001 8 (A) 8 – 0 (A) 2 – 0 (A) 4 (A) 
19 8 0...0 0000 1000 4 (A) 4 – 0 (A) 1 – 0 (A) 2 (A) 
20 18 0...0 0001 1000 12 (F) 12 – 1 (F) 3 – 0 (F) 12 (F) 
 
2. Tiempo medio de acceso = tiempo acierto + 
 porcentaje/probabilidad fallo * penalización por fallo 
 T = N*(10 ns) + 0.05*(20*10) = 10N ns + 10 ns 
 T = (N+2)*(10 ns) + 0.03*(20*10) = 10N ns + 26 ns No se consigue una mejora 
 en el tiempo medio de acceso 
3. COMPUTADOR A: 
 
 5
Decir que en la caché hay 4 vías con 256 entradas en cada vía es lo mismo que decir que existen 
1024 líneas y la memoria es asociativa por conjuntos de 4 vías. Sabiendo esto lo que está claro es 
que van a existir 256 conjuntos/entradas y en cada uno 4 líneas/bloques. 
¿Profundidad y anchura? Profundidad ya la sabemos 256 conjuntos/entradas de 4 elementos cada 
uno. Para saber la anchura necesitamos saber lo que ocupa el campo de etiqueta y el de 
desplazamiento o datos. Veamos cuánto ocupan: 
Datos: (64K para datos / 256 conjuntos) / (4 líneas por conjunto) = (2
16
/ 2 8 ) / 2 2 = 2 6 bits = 64 
bits = 8 bytes = 2 3 bytes se necesitan 3 bits para direccionar el dato dentro del bloque. 
Tendremos 8 bytes en cada bloque o línea 
 
Etiqueta: (16K para etiquetas/256 conjuntos) / (4 líneas por conjunto) = (2
14
/ 2 8 ) / 2 2 = 2 4 bits 
 = 16 bits por etiqueta 
 
Así pues se tendrá el siguiente esquema de direcciones: 
 
 
 
 
Esto quiere decir que la memoria física o principal tendrá un total de 2 27 bytes o lo que es lo mismo 
128 Mbytes. 
 
La organización o esquema de la memoria caché será el siguiente: 
 
 ETI BLOQUE ETI BLOQUE ETI BLOQUE ETI BLOQUE 
0 
. 
. 
. 
. 
. 
 
 
 
 
 
 
255 
 
 2 bytes 8 bytes 
 
 
COMPUTADOR B: 
Si ahora los bloques son de 4 palabras tendremos que el campo de desplazamiento estará dividido 
en dos partes: una para la palabra y otra para el byte dentro de la palabra. El resto de campos del 
esquema de direcciones no sufren variaciones por lo que el esque de direcciones queda como sigue: 
 
 
 
Como las palabras son ahora de dos bytes entonces la memoria física o principal tendrá un total de 
2 26 palabras o lo que es lo mismo 64 Mpalabras de 16 bits o dos bytes. La capacidad de la MP sigue 
siendo la misma pero la forma de acceder o interpretar la información cambia. 
16 8 3 
Etiqueta Conjunto desplazamiento 
16 8 2 1
Etiqueta Conjunto word byte 
 
 6
4. Si tenemos un procesador de 32 bits significa que el tamaño de una palabra (y/o una referencia a 
memoria si no nos dicen nada más) es de 32 bits o lo que es lo mismo de 4 bytes. Este también sería 
el tamaño de una dirección enviada por el procesador a memoria principal. 
Como nos dicen que las líneas son de 4 palabras ya tenemos el campo de desplazamiento dentro del 
bloque: 4 bits o 2+2 (W+B). En total 16 bytes por línea = 4 palabras*4bytes por palabra. 
 
¿Cuál es el tamaño del campo conjunto? o lo que es lo mismo, ¿cuántas entradas o conjuntos tiene 
nuestra caché? Sabemos que es asociativa de4 vías, 16 bytes por línea y que el tamaño total de la 
caché es de 16 Kbytes. Por lo tanto el número de conjuntos o entradas será: 
16Kbytes / 16 bytes por línea = 2 14 / 2 4 = 2 10 líneas. 
Como tenemos 4 vías, es decir, conjuntos de 4 líneas: 210 líneas / 2 2 líneas por conjunto = 
2 8 conjuntos o entradas = 256 conjuntos o entradas 8 bits para el campo conjunto 
 
¿Cuál es el tamaño de la etiqueta? No hay más que restar al tamaño total del campo de direcciones 
(32 bits) la suma de los anteriores campos: 
32 bits del campo direcciones – (8 bits campo conjunto o entrada + 4 bits campo desplazamiento 
dentro del bloque o línea) = 20 bits 
Por lo tanto el esquema de direcciones sería: 
 
 
 
De la dirección 0xABCDE8F8 hex sólo nos interesan los 12 primeros bits para saber el conjunto o 
entrada en la caché y luego la posición dentro de la línea (palabra+byte). 
..... 1000 1111 1000 bin Los 2 primeros bits (los que están más a la izquierda) nos dicen que el byte 
dentro de la palabra será el cero (00), los dos siguientes que la palabra dentro del bloque o línea será 
la 2ª (10) y los 8 bits restantes que estará en el conjunto o entrada 143 (1000 1111). 
 
5. ¿Cuánto ocupa una línea o bloque? 
 Bloques de 2 palabras x 2 bytes por palabra (16 bits) = 4 bytes = 2 2 bytes 
 2 bits para el campo de desplazamiento dentro del bloque 1+1 (W+B) 
 ¿Cuántas líneas/bloques se pueden almacenar en la memoria caché? 
 4K dobles palabras = 8K palabras. Como cada palabra tiene 16 bits (2 bytes) 
 8K palabras x 2 bytes por palabras = 16K bytes = 16384 bytes = 2 14 bytes 
 Ahora ya se conoce el tamaño total de la caché y lo que ocupa cada línea. Por lo tanto 
para hallar el número de bloques/líneas habrá que hacer: 
214 bytes en la caché / 2 2 bytes por línea en la caché = 2 12 líneas o bloques 
 
Como la memoria caché es asociativa por conjuntos de elementos (4 vías), en total se tendrán los 
siguientes conjuntos o entradas en la memoria caché: 
2 12 líneas o bloques / 4 líneas por conjunto = 1024 = 210 conjuntos o entradas 
 10 bits para el campo de conjuntos 
Como se sabe que las direcciones son de 24 bits la etiqueta ocupará: 24 – (10+2) = 12 bits y el 
esquema de direcciones sería el siguiente: 
 
 
 
20 8 2 2 
Etiqueta Conjunto word byte 
12 10 1 1 
Etiqueta Conjunto word byte 
 
 7
3 bits
La estructura de la caché por tanto tendrá un esquema parecido al siguiente: 
 ETI BLOQUE ETI BLOQUE ETI BLOQUE ETI BLOQUE 
0 
. 
. 
. 
. 
. 
 
 
 
 
 
 
1023 
 12 bits 4 bytes 
 
6. Se va a seguir un razonamiento similar al del ejercicio anterior: 
. ¿Cuánto ocupa una línea o bloque? 
 Bloques de 4 dobles palabras x Y bytes por palabra = 16 bytes de memoria por bloque 
= 2 4 bytes de memoria por bloque 
 Y = 4 bytes por palabra y además 4 bits para el campo de desplazamiento dentro del 
bloque 2+2 (W+B) 
Ya se sabe que el campo conjunto o entradas tendrá 7 bits (128 conjuntos = 2 7 conjuntos). La 
cuestión que queda por resolver es cuánto ocupa el campo etiqueta. 
Para esto es necesario saber cuanto ocupa el campo de direcciones de memoria o la palabra del 
procesador. En este caso se necesita saber que el 486 al igual que el Pentium son procesadores de 
32 bits y por lo tanto el campo dirección ocupa 32 bits. Por lo tanto el campo etiqueta ocupará 21 
bits: 
32 bits – (7 bits + 4 bits) = 21 bits campo etiqueta 
La interpretación de las direcciones se hará de la siguiente manera: 
 
 
 
Si en vez de acceder a dobles palabras accedemos a palabras, que es lo más usual, tendríamos el 
siguiente esquema: 
 
 
 
El esquema de la estructura interna de la memoria caché será el siguiente: 
 V ETI BLOQUE V ETI BLOQUE V ETI BLOQUE V ETI BLOQUE LRU 
0 
. 
. 
. 
 
 
 
 
 
 
127 
 21 bits 16 bytes 1 bit 
 
(NOTA: para implementar el algoritmo Pseudo-LRU para 4 elementos hacen falta 3 bits por 
conjunto.) 
 
21 7 2 2 
Etiqueta Conjunto word byte 
21 7 3 1 
Etiqueta Conjunto word byte 
 
 8
7. a) Lo primero antes de averiguar el MR es saber el número de bloques/líneas con que cuenta la 
memoria caché. Hay una capacidad 256 bytes = 28 bytes en la memoria caché. Además se dice que 
un bloque ocupa 16 bytes (4 palabras de 32 bits = 4x4 bytes). Por lo tanto el número de 
bloques/líneas es: 28 / 24 = 24 = 16 bloques o líneas. Así pues un esquema de la memoria caché sería 
el siguiente: 
Nº 
línea 
palabras 
0 0 1 2 3 
... ... ... ... ... 
... ... ... ... ... 
15 60 61 62 63 
 
Como se puede ver sólo se pueden introducir un total de 64 palabras como máximo. Hay fijarse y 
tener en cuenta que un número entero en C ocupa 32 bits, es decir, una palabra. Por lo tanto la 
memoria caché podría en el mejor de los casos almacenar hasta 64 números enteros. Si se supone 
que un entero en C ocupa 16 bits (por ej. En un programa en MS-DOS) la solución cambiaría 
ligeramente. 
Ahora hay que analizar ahora el comportamiento del bucle interno. El bucle externo simplemente 
repite lo que hace el bucle interno varias veces. Se dice en el enunciado que la memoria es de 
correspondencia directa. Se va a ir viendo a qué elementos se accede. 
j = 0 Elemento 1 
j = 132 Elemento 133 
j = 264 Elemento 264. No se accede a él porque 264>256 (mirar código del programa). 
 
Por lo tanto se va a acceder a dos números o palabras. La pregunta que hay que hacerse a 
continuación es a qué bloques de memoria principal corresponden estas palabras y dónde se 
ubicarían estos bloques en la memoria caché. Ya que el enunciado no lo dice se supone por 
simplicidad que el array se carga a partir de la dirección y bloque 0 de M.P. (memoria principal). 
Como no se dice nada se supone también que la memoria caché está inicialmente vacía. Atención: 
hay que tener en cuenta que los números de bloques al igual que los elementos del array empiezan a 
contarse a partir de cero y no de uno. 
 
j = 0 Bloque 0 de memoria principal. 0 MOD 16 = 0 
j = 132 Bloque 33 de memoria principal ya que: 132 / 4 = 33 ó 4*33 = 132 es decir, en el 
bloque Nº 32 de M.P. está contenido el elemento Nº 131 del array. Por lo tanto en el bloque Nº 
33 estarán contenidos los elementos Nº-s 132, 133, 134 y 135. 33 MOD 16 = 1 
 
Se puede por tanto concluir que una vez traídos los dos bloques de memoria principal 
correspondientes a los accesos efectuados por el programa (dos únicos fallos forzosos), estos se 
ubicarán en las líneas 0 y 1 de la memoria caché. No existen por lo tanto fallos de conflicto y sólo 
hay que tener en cuenta dos fallos forzosos en la primera iteración del bucle interno (durante la 
primera iteración del bucle externo). Los fallos de capacidad también se descartan porque sólo se 
accede a dos palabras/enteros y en la caché hay espacio para 64 palabras/números. Repetidos estos 
accesos 10000 veces (bucle exterior) se puede concluir por tanto que el Miss Rate es 
aproximadamente cero (MR ~ 0). 
 
b) Ahora zancada es igual a 131. Siguiendo un razonamiento análogo al anterior se trata de 
averiguar los elementos accedidos del array al igual que los bloques de M.P. dónde están contenidos 
para saber dónde se ubicarían una vez traídos a la memoria caché. 
 
 
 9
j = 0 Elemento 1 
j = 131 Elemento 132 
j = 262 Elemento 262. No se accede a él porque 262>256 (mirar código del programa). 
 
Los bloques de memoria principal: 
j = 0 Bloque 0 de memoria principal. 0 MOD 16 = 0 
j = 131 Bloque 32 de memoria principal ya que: 131 / 4 = 32,75 ó 4*32 = 128 es decir, en el 
bloque Nº 31 de M.P. está contenido el elemento Nº 127 del array. Por lo tanto en el bloque Nº 32 
estarán contenidos los elementos Nº-s 128, 129, 130 y 131. 32 MOD 16 = 0 
 
Ahora resulta que los dos accesos que se producen a M.P. debido a la lectura de dos 
números/palabras corresponden a dos bloques diferentes (el bloque 0 y el 32) de M.P. que han de 
ubicarse en la misma línea de la memoria caché. Esto supone que se hayaque traer y expulsar 
sucesivamente bloques de la línea cero de la memoria caché produciéndose dos fallos de conflicto 
en cada iteración del bucle interior. Repetidos estos accesos 10000 veces (bucle exterior) se puede 
concluir por tanto que el Miss Rate es exactamente uno (MR = 1). 
 
c) Si la memoria caché se convierte en una caché asociativa por conjuntos de dos vías se soluciona 
el problema anterior y el MR ~ 0. Esto es así porque sólo se han de traer dos bloques distintos de 
memoria principal en todo el programa y ahora al disponerse de dos líneas por conjunto hay espacio 
suficiente para ubicar esos dos bloques en el mismo conjunto en caso de necesidad. 
 
d) En primer lugar se va a calcular el tiempo de acceso para el caso A. En el enunciado no se aclara 
del todo si en los 20t ciclos que se tarda en acceder a la memoria principal son para leer un bloque o 
solamente una palabra. Se va a suponer que el acceso es a una palabra ya que el acceso de t ciclos a 
la caché es también para acceder a una palabra. Lo contrario también tiene sentido ya que entre la 
memoria principal y la caché los intercambios son siempre a nivel de bloque. Primero hay que 
recordar la expresión del cálculo del tiempo de acceso a memoria caché: 
Tacc. caché = Tacc. hit + MR*Tpenal. = Tacc. hit + Tacc. fallo 
Tacc. cache A = Tacc. hit A + Tacc. fallo A = 20000t + 2*(20t*4) = 20160t 
En caso de fallo traer un bloque a memoria caché cuesta lo mismo que traer 4 palabras por 
separado. Como ya se ha comentado anteriormente se podría haber supuesto que los 20t son 
realmente para traer de M.P. las cuatro palabras en paralelo. 
 
Para el caso B se realiza un razonamiento similar: 
Tacc. cache B = Tacc. hit B + Tacc. fallo B = 20000t + 20000*(20t*4) = 1620000t 
 
Como se puede ver con estos valores el hecho de tener una cierta organización u otra en la memoria 
caché puede influir de forma decisiva en el rendimiento general de un computador en determinadas 
aplicaciones. Estos factores pueden llegar a ser realmente importantes a la hora de por ejemplo de 
tener que diseñar de un sistema de tiempo real. 
 
 
8. Es una cuestión teórica relativa a la memoria virtual. Para responder a la cuestión hay que 
explicar el proceso de traducción de dirección lógica o virtual a dirección física y finalmente el 
acceso al dato a través de la caché. Esto se explica en la teoría y en la bibliografía. 
 
 
 
 10
9. Si las páginas son de 16KB (2 14 bytes) y la dirección virtual ocupa 40 bits (se pueden 
direccionar hasta 2 40 posiciones de memoria) tendremos un total de 2 26 = 67108864 páginas 
posibles en la tabla de páginas. 
 
¿Cuántos bits hay en cada entrada de la tabla de páginas? 
Sabemos que la dirección física ocupa 36 bits y que 14 de esos bits son para el desplazamiento 
dentro de la página. Por lo tanto la dirección de un marco en memoria principal será de 22 bits (36 – 
14). 
 
¿Cuánto ocupa por tanto la tabla de páginas? 
TP = 2 26 páginas en la TP*(22 bits de dirección del marco en MP + 4 bits de control por página) = 
26*2 26 bits = 26*64 Mbits = 1664 Mbits = 208 Mbytes 
 
El esquema de traducción de direcciones será el siguiente: 
 
40 bits 
número de página virtual (26 bits) Desplazamiento (14 bits) 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
36 bits 
número de página física o marco (22 bits) Desplazamiento (14 bits) 
 
 
 
Como apunte se podría decir que el tamaño de la tabla de páginas de un proceso es tan grande que 
habría que recurrir a técnicas de reducción/compactación de tamaño tales como hacer crecer 
dinámicamente la tabla, funciones hash, paginar la tabla de páginas, ... 
 
 
 Bits de 
control 
Dirección de 
Marco en MP 
0 
. 
. 
. 
. 
. 
 
2 26 
Dirección 
virtual 
Dirección 
física 
TABLA DE 
PÁGINAS 
4 
bits 
22 
bits