Download ARQUITECTURA DE COMPUTADORES

ARQUITECTURA DE COMPUTADORES.
2º ING. INFORMÁTICA.
PROBLEMA DE MEMORIA VIRTUAL.
Enunciado.
Se supone un sistema basado en microprocesador cuya jerarquía de memoria tiene los
siguientes parámetros:
Memoria Virtual: 16Mbytes en páginas de 512 bytes.
TLB: 64 líneas en total y asociativa 32 vías.
Caché: 64 Kbytes para datos. Asociativo 4 vías. Bloques de dos palabras.
Memoria física o principal: 4 Mbytes. Palabras de 2 bytes.
Disco: memoria secundaria o archivo de intercambio de 64 Mbytes.
Especificar la tabla de páginas (TP), la TLB, la caché, la memoria principal y el fichero
de intercambio. Especificar los campos de la dirección virtual, la dirección de memoria
principal, la dirección en disco, y los campos de la dirección de caché. ¿De dónde se
saca la dirección que sirve de entrada a la caché?
Suponed un proceso de 4 páginas, y que el sistema operativo asignan los marcos 4A,
4B, 4C y 4D a las páginas virtuales de este proceso cuando se inicia el mismo. ¿Cómo
se rellenan los campos de la tabla de páginas? ¿Cambiaría la TLB? ¿Y cuando el
sistema operativo empezase a ejecutar ese proceso? ¿Cómo cambiarían la TP y la TLB
si queremos acceder a la dirección 00023Chex? ¿Acertaría en la caché si este es el primer
acceso que ejecuta este proceso? ¿Dónde tendría que estar este dato en la caché?
Suponed que el sistema operativo asignará los marcos de memoria A0, A1, A2 y A3 a
este proceso.
¿Qué pasaría si acto seguido se accede a la dirección 00023Ehex? ¿Acertaría en la TLB?
¿Y estaría la página en memoria principal? ¿Estaría el dato en la caché?
¿Qué pasaría si acto seguido se accede a la dirección 000240hex? ¿Acertaría en la TLB?
¿Y estaría la página en memoria principal? ¿Estaría el dato en la caché?
1
Solución:
Comenzaremos por dimensionar la tabla de páginas, con todos sus campos. ¿Cuántas
entradas tendremos en la tabla de páginas? Tendremos tantas como páginas virtuales.
Podemos averiguar el número de páginas virtuales si sabemos cuantas páginas virtuales
puede ver cada proceso: Tenemos un sistema de memoria virtual con 16 Mbytes, y
páginas de 512 bytes.
24
9
16 Mbytes / 512 bytes = 2 bytes / 2 bytes = 32768 páginas virtuales.
Por lo tanto la dirección virtual será:
23
9 8
número de página virtual (15 bits)
0
desplazamiento
La tabla de páginas devolverá una dirección en memoria principal o una dirección de
disco (marco en disco o en memoria principal). ¿Qué ancho tienen estas dos
direcciones? Sabemos que tenemos 4Mbytes de memoria principal y 64Mbytes de
disco, ambos divididos en páginas de 512 bytes.
22
9
4 Mbytes / 512 bytes = 2 bytes / 2 bytes = 8192 marcos en memoria principal.
26
9
64 Mbytes / 512 bytes = 2 bytes / 2 bytes = 131072 marcos en disco.
Por lo tanto la dirección en memoria principal será:
21
9 8
número de marco en memoria principal (13 bits)
0
desplazamiento
y la dirección en disco...
25
9 8
número de marco en disco (17 bits)
0
desplazamiento
Y tendremos una tabla de páginas con la siguiente estructura. Se escoge la
implementación más usual con bit de validez (V) para indicar si la página está en disco
o en memoria principal y el bit de “página sucia” (D). La tabla de páginas la
direccionaremos con el campo “número de página virtual” de la dirección virtual.
V D Dirección página en memoria (principal ó disco) (17 bits)
0
.
.
.
.
.
.
32767
.
.
.
.
.
.
2
Vamos a dimensionar la TLB. Sabemos que tiene 64 líneas y es asociativa por
conjuntos de 32 vías. Esto quiere decir que la TLB va a tener dos entradas de 32 líneas
cada una.
¿Cuál es la dirección que se le da como entrada a la TLB?
La misma que se le da como entrada a la tabla de páginas, es decir el campo “número
de página virtual” de la dirección virtual, pero la TLB va a tener un modo distinto de
interpretar esta dirección para saber si una entrada en la tabla de páginas está o no en la
TLB. Si la TLB tiene 2 entradas/conjuntos (64 líneas y 32 líneas por conjunto), parte de
la dirección de la TLB va a destinarse a seleccionar el conjunto (en concreto el bit
menos significativo), y el resto se destinará a etiqueta. Por lo tanto, la dirección entrada
a la TLB nos queda así:
número de página virtual.
14
1
ETIQUETA
0
E
Y la TLB...
0
...
31
Conjunto/Vía cero
ETIQ. V Dir. Memoria
-0
-...
...
...
-0
--
Conjunto/Vía uno
ETIQ. V Dir. Memoria
-0
-...
...
...
-0
--
Ahora dimensionaremos la caché: tiene 64KB para datos, y bloques de 2 palabras, de 2
bytes cada una, y es asociativa de cuatro vías. ¿Cuántas líneas va a tener la caché?
((64Kbytes / 4 vias ) / 4 bytes por bloque) = 4096 líneas = 2 12 líneas.
¿Qué dirección se le suministrará a la caché? la dirección completa de memoria
principal. ¿Cómo la interpretará?
La estructura de direcciones de la caché sabiendo que es asociativa por conjuntos de 4
vías, bloques de 2 palabras de dos bytes cada una y con una memoria principal de 4
Mbytes será la siguiente:
21
14 13
2 1
ETIQUETA
CONJUNTO/ENTRADA W
0
B
¿Cómo estará organizada la caché?
Tendremos cuatro vías, y cada una de ellas tendrá 4096 líneas. En cada línea se guarda
información de línea válida, etiqueta y bloque de dos palabras de dos bytes cada una (un
bloque en cada línea de la vía).
3
ETI V BLOQUE
ETI V BLOQUE
ETI V BLOQUE
ETI V BLOQUE
LRU
0
... ...
...
... ...
... ...
...
...
... ...
...
...
4095
(NOTA: en el anterior esquema el campo LRU presente en cada conjunto de 4 líneas es
debido a que para implementar la política pseudo-LRU con cuatro elementos hacen falta
tres bits.)
Ya tenemos totalmente dimensionado el sistema. Ahora suponemos que se crea un
proceso en nuestra máquina, y que el sistema operativo le guarda espacio en disco en los
marcos 4Ahex – 4Dhex. Lo primero que haría el sistema operativo sería crear una tabla de
páginas para ese proceso, y rellenarla de la siguiente manera:
0
1
2
3
V
0
0
0
0
D Dirección página en memoria (principal ó disco) (17 bits)
0
4Ahex
0
4Bhex
0
4Chex
0
4Dhex
.
.
.
.
.
.
.
.
.
32767 0
(NOTA: en la figura anterior los campos con las direcciones de página se supone que ocupan 17
bits pero se omite escribir todos los ceros a la izquierda por motivos de claridad. Así por
ejemplo 4A hex = 0 0000 0000 0100 1010 bin )
Esto no supondría cambio alguno en la TLB, puesto que todavía no hemos accedido a
las páginas de este proceso y todavía no hemos llevado ninguna de estas a memoria.
Hay que recordar que en la TLB tenemos entradas pertenecientes a páginas virtuales
que han sido llevadas a memoria principal. Cuando el sistema operativo cambie de
proceso y empiece a ejecutarlo, lo que hará será borrar la TLB.
Al acceder a la dirección virtual 00023Chex, habría que traducir esta dirección virtual a
una dirección en disco o memoria principal. Primero se mira en la TLB, que al haberse
borrado no contiene ninguna línea válida. Hay que buscar en la tabla de páginas. ¿En
qué entrada? La dirección virtual en binario es:
0000 0000 0000 0010 0011 1100 bin
Que se interpreta como:
página: 0000 0000 0000 001 bin = página 1
desplazamiento: 0 0011 1100bin = 03Chex
4
El dato que buscamos está en la página virtual nº1. Al mirar en la TP se ve que la página
está en el marco 4Bhex de disco. Se trae a memoria principal, al marco A1, y se modifica
la entrada de la página 1 en la TP.
0
1
2
3
.
.
.
V
0
1
0
0
.
.
.
D
0
0
0
0
.
.
.
Dirección página en memoria (principal ó disco) (17 bits)
4Ahex
A1hex
4Chex
4Dhex
.
.
.
32767 0
Ahora actualizaremos la TLB. ¿Qué se guarda en la TLB? El mismo valor que se ha
almacenado en la tabla de páginas, es decir, la dirección del marco de memoria principal
que contiene la página virtual nº1 del proceso que se va a ejecutar.
0000 0000 0000 001 Æ dirección de la entrada/conjunto 1 en TP
(La etiqueta es 0000 0000 0000 00 y el último bit sirve para indicar el conjunto/entrada
1 en la TLB)
Como la TLB es una caché asociativa por conjuntos de 32 vías, el bloque se podrá
guardar en cualquiera de las 32 líneas de la TLB del conjunto 1. Por comodidad se
guarda el bloque en la primera línea (línea cero) del conjunto 1, puesto que está libre
(hay que recordar que se vació la TLB al comenzar la ejecución del proceso).
0
...
31
Conjunto/Vía cero
ETIQ. V Dir. Memoria
-0
-...
...
...
-0
--
Conjunto/Vía uno
ETIQ.
V Dir. Memoria
0000 0000 0000 00
1
A1hex
...
...
...
-0
--
Una vez actualizada la TP y la TLB, la dirección virtual 00023Chex pasaría a ser la
dirección de memoria principal 01423Chex (marco en MP + desplazamiento).
Marco en memoria principal: 00A1hex ( 0 0000 1010 0001bin )
Desplazamiento: 03Chex ( 0 0011 1100bin )
Con esta dirección de memoria principal (01423Chex) se accede al caché para ver si está
el dato. Este dato no estará, porque es la primera vez que se accede a los datos de esa
página, que han sido traídos desde disco, de manera que si el caché tenía un dato de esa
dirección de memoria cuando sus datos pertenecían a otra página virtual, estos datos han
sido invalidados. ¿Dónde buscará el dato en la caché? Veamos cómo ve la dirección de
memoria nuestra caché:
ETIQUETA
0000 0101
INDICE
0000 1000 1111
W
0
B
0
5
Buscará el dato en alguna de las vías de la línea 143 (índice = 0000 1000 1111bin =
08Fhex) y buscará la palabra 0 del bloque.
Al tener un fallo de caché, se traerá a la caché un bloque entero de memoria, y lo
guardará en uno de los cuatro bloques de la línea 143 de la caché. ¿Qué direcciones se
traerán a la caché?:
0000 0101 0000 1000 1111 0 0bin = 01423Chex
0000 0101 0000 1000 1111 0 1 bin = 01423Dhex
0000 0101 0000 1000 1111 1 0 bin = 01423Ehex
0000 0101 0000 1000 1111 1 1 bin = 01423Fhex
Realmente se traerán dos palabras de dos bytes cada una. Después de traer el bloque de
memoria principal, el procesador podrá acceder al dato de la posición 01423Chex.
Si la siguiente dirección virtual a la que accede el procesador es la 00023Ehex, volvería a
consultar la TLB. Primero vamos a descomponer los campos de esta dirección virtual.
La dirección virtual en binario es:
0000 0000 0000 0010 0011 1110
Que se interpreta como:
página: 0000 0000 0000 001 bin = página 1
desplazamiento: 0 0011 1110 bin = 03Ehex = desplazamiento 62
Buscará en la TLB el conjunto/entrada 1 de un bloque válido cuya etiqueta sea:
0000 0000 0000 000
Se produce un acierto (hit) en la TLB, pues es la misma página que consultamos
anteriormente. De este modo, se encontrará el bloque, y se dará como resultado que el
dato está en el marco A1hex de la memoria principal. No habrá que consultar la tabla de
páginas.
Ahora se consulta en la caché. La dirección en memoria principal será:
Número de marco en memoria principal: A1hex
Desplazamiento dentro de ese marco: 3Ehex
Por lo tanto la dirección en memoria principal queda como:
0000 0101 0000 1000 1111 1 0 bin
De nuevo, consultaremos la caché. El caché ve la dirección de la siguiente forma:
ETIQUETA
0000 0101
INDICE
0000 1000 1111
W
1
B
0
6
Es decir, busca dentro de la línea 143 (0000 1000 1111bin = 8Fhex) un bloque válido con
la etiqueta 0000 0101, y dentro de ese bloque buscará la palabra 1. El dato estará en
memoria, pues el bloque asociado a esta dirección de memoria lo cargamos
anteriormente en la caché cuando tuvimos el primer fallo de caché ( es la dirección
01423Ehex ).
Si después accedemos a la dirección virtual 000240hex estaremos accediendo a la misma
página virtual (marco en MP), que estará ya en la memoria principal, y por lo tanto
volveremos a tener un acierto en la TLB, que volverá a convertir nuestra dirección
virtual en:
Número de marco en memoria principal: A1hex
Desplazamiento dentro de ese marco: 40hex
Esta vez buscaremos en la caché la siguiente dirección: 0000 0101 0000 1001 0000 0 0
ETIQUETA
0000 0101
INDICE
0000 1001 0000
W
0
B
0
Buscará por primera vez un bloque válido en alguna de las cuatro vías de la línea 144
(0000 1001 0000 bin) de la caché que tenga la etiqueta 0000 0101, y buscará dentro de
ese bloque la palabra 0. Este dato no está en la caché, y se producirá un fallo en caché
(recordemos que todos los datos de la caché que pertenecían al marco A1hex de memoria
quedaron invalidados cuando cargamos la página virtual 1 de nuestro proceso) que hará
que se traiga a caché otro bloque de la memoria principal (de la misma página virtual o
marco que cargamos al principio en MP) con las siguientes direcciones de memoria:
0000 0101 0000 1001 0000 0 0 = 014240hex
0000 0101 0000 1001 0000 0 1 = 014241hex
0000 0101 0000 1001 0000 1 0 = 014242hex
0000 0101 0000 1001 0000 1 1 = 014243hex
7