Tema 3. ¿Cómo se traduce de dirección virtual a dirección física?

Memoria Virtual

                   La Memoria Virtual es un concepto que permite al software usar más memoria principal que la que realmente posee el ordenador. La mayoría de los ordenadores tienen cuatro tipos de memoria: registros en la CPU, la memoria caché (tanto dentro como fuera del CPU), la memoria física (generalmente en forma de RAM, donde la CPU puede escribir y leer directa y razonablemente rápido) y el disco duro, que es mucho más lento, pero también más grande y barato.

Las dos razones por las que se utiliza memoria virtual son:

- compartir la memoria eficientemente y sin peligros entre múltiples programas.

- eliminar el inconveniente de tener un espacio de memoria principal pequeño y limitado, ya que puede ocurrir que los programas necesiten más memoria que la disponible en memoria principal.

                Muchas aplicaciones requieren el acceso a más información (código y datos) que la que se puede mantener en memoria física. Esto es así sobre todo cuando el sistema operativo permite múltiples procesos y aplicaciones ejecutándose simultáneamente. Una solución al problema de necesitar mayor cantidad de memoria de la que se posee consiste en que las aplicaciones mantengan parte de su información en disco, moviéndola a la memoria principal cuando sea necesario. Hay varias formas de hacer esto. De modo que se usa el disco duro para “emular” la memoria principal.

La Tabla de Páginas

                Para poder llevar a cabo esta técnica, en lugar de tener una lista con las direcciones de memoria reales, debemos llevar el control todas las direcciones virtuales que “componen” nuestra memoria “ampliada”. Así realmente se puede usar más memoria de la que realmente hay en el hardware. En la Tabla de Páginas se mantiene una lista de todas las direcciones virtuales y su relación con las direcciones físicas reales donde están almacenados los datos. El SO se encarga de gestionar todo esto: el uso de la memoria, los traslados de la memoria a disco y viceversa, y la traducción de direcciones.

                En Memoria Virtual, los bloques de memoria, llamados páginas, se traducen de un conjunto de direcciones es virtuales a otro conjunto, direcciones físicas. Las páginas son la unidad básica con la que se trabaja.

                Cuando un programa se está ejecutando accede continuamente a direcciones de memoria. Como hemos dicho, parte de nuestra memoria virtual está realmente en la rápida memoria principal, pero también hay una parte que está en el disco duro. De todos las lecturas/escrituras que se hagan a memoria, cuantos más accesos a direcciones virtuales acertemos con direcciones reales de memoria principal mejor, porque serán muy rápidos. Por contra, si al acceder a una dirección virtual ésta se encuentra en el disco duro, esto recibe el nombre de fallo (o fallo de página), porque al acceder a disco los tiempos de lectura son mucho más altos y perdemos eficiencia. Es fácil ver que cuantos menos fallos y más aciertos tengamos mejor. Por eso se han creado varios algoritmos para intentar que los accesos a disco (la tasa de fallos) sean mínimos y la velocidad sea la máxima posible.

La caché TLB: Translation Lookahead Buffer
                 El TLB es una pequeña memoria caché para anticipar las direcciones de traducción. En esta caché se guardan los bloques de páginas de la memoria virtual que tienen mayor probabilidad de ser accedidas. De modo que cuando un programa va a acceder a memoria virtual, antes de ir a buscar en la tabla de páginas, mirará en la TLB y si estuviera allí la dirección virtual consultada, directamente obtendría la dirección física que necesita. Rapidísimo. Genial.

                A veces, sin embargo, no está la dirección virtual en la TLB. Habría que acceder a la tabla de páginas tardando un poco más, sobre todo en caso de que la dirección no estuviera en la memoria sino en el disco. Habría que considerar si es interesante actualizar la TLB y/o la tabla de páginas. Con este fin, hay algoritmos de reemplazo de páginas que consideran si es oportuno o no intercambiar páginas entre memoria y disco, siempre buscando que el rendimiento global sea máximo, que haya el máximo éxito en los accesos a memoria. Hay muchos algoritmos para decidir como mover las páginas: FIFO (el primero en entrar el primero en salir), LRU (el que lleva más tiempo sin ser usado)…

Traducción de direcciones virtuales a direcciones físicas

                El TLB hace referencia a direcciones físicas en su tabla. Puede residir entre la CPU y la caché de la misma o entre esta caché y la unidad de memoria primaria. Esto depende de si la caché utiliza direccionamiento físico o virtual. Si la caché se direcciona de manera virtual, las peticiones se envían directamente de la CPU a la caché, la cual accede al TLB cuando es necesario. Si la caché se direcciona de manera física, la CPU realiza una búsqueda en el TLB con cada operación de memoria, y la dirección física resultante es enviada a la caché. Existen pros y contras en ambas implementaciones.

                Una optimización común para las cachés direccionadas de manera física es realizar una búsqueda en el TLB en paralelo con el acceso a caché. Los bits de orden más bajo de cualquier dirección virtual (por ejemplo en un sistema de memoria virtual que tiene páginas de 4KB, los 12 bits más bajos de la dirección virtual) no cambian en la traducción de dirección virtual a física. Durante un acceso a caché se realizan dos acciones: Se utiliza un índice para encontrar una entrada en el sistema de datos de la caché, y a continuación las etiquetas de la línea encontrada se comparan. Si la caché está estructurada de tal manera que pueda ser indexada utilizando solo los bits que no cambian en la traducción, la caché puede realizar su operación de "indexación" mientras el TLB traduce la parte alta de la dirección. Entonces, la dirección traducida del TLB es enviada a la caché. La caché realiza una comparación de etiquetas para determinar si este acceso ha sido un acierto o un fallo.

Fallo

                En las arquitecturas modernas se pueden observar dos métodos de tratar un fallo de TLB, mediante hardware y mediante software:

               - Con el manejo hardware del TLB, la propia CPU comprueba las tablas de paginación para ver si hay alguna entrada válida para la dirección virtual especificada. Si la entrada existe, se lleva a la TLB y se reintenta el acceso; esta vez el acceso será un acierto, y el programa podrá proceder con normalidad. Si la CPU no encuentra una entrada válida para la dirección virtual en las tablas de página, se genera una excepción de fallo de página, la cual deberá manejar el sistema operativo. El manejo de los fallos de página normalmente implica llevar los datos pedidos a la memoria física, generando una entrada en la tabla de paginación para mapear la dirección virtual que faltaba para corregir la dirección física, y reiniciar el programa.

                - Con el manejo software de las TLB, un fallo genera una excepción "fallo de TLB", y el sistema operativo debe acceder a las tablas de paginación y realizar la traducción por software. Entonces, el sistema operativo carga la traducción en el TLB y reinicia el programa desde la instrucción que causó el fallo. Como en el sistema de manejo hardware, si el SO no encuentra una traducción válida en las tablas, ocurre un fallo de página y el SO deberá manejarlo de la manera correspondiente.

Estadísticas típicas

Tamaño: 8 - 4.096 entradas

Tiempo de acierto: 0,5 - 1 ciclos de reloj

Penalización por fallos: 10 - 30 ciclos de reloj

Ratio de fallos: 0.01% - 1%

Si un acierto de TLB requiere 1 ciclo de reloj, un fallo requiere 30 ciclos, y siendo el ratio de fallos 1%, el ratio de ciclos de memoria efectiva es una media de

1x0,99 + (1+30)x0,01 = 1,30 ciclos de reloj por acceso a memoria.

Referencias:

Apuntes de 3º de Estructura de Computadores de la Universidad Complutense de Madrid (UCM)
 http://www.fdi.ucm.es/profesor/jjruz/WEB2/Temas/EC7.pdf

Apuntes de Estructura de Computadores III de la Universidad de La Laguna (etsii.ull.es)
http://www.scribd.com/doc/8245822/Estructura-de-Computadores-3

Artículos sobre la Caché TLB y paginación: www.wikipedia.org