Universidad de Costa Rica Escuela de Ciencias de la Computación e Informática CI-0122 Sistemas operativos NachOS Proyecto Programado # 3 Caching: TLB y memoria virtual

• Descripción

• En esta fase de NachOS se investigará el uso de caching con dos propósitos:
• Primero, se va a emplear un traductor de direcciones basado en software (Translation Lookaside Buffer [TLB]), se trara de una memoria cache para la tabla de páginas, con el fin de dar la ilusión de un acceso rápido al traductor de direcciones virtuales que funcionaría en un espacio de direcciones muy grande
• Además, se va a utilizar el disco como parte de la memoria principal, con el fin de proveer un espacio de direccionamiento (casi) ilimitado, con el desempeño cercano al de la memoria física
• Para esta asignación no se provee código nuevo, el único cambio necesario de compilar el código ya existente (threads y userprog) con las banderas DVM y DUSE_TLB), incluidas dentro del Makefile del proyecto "vm" (-DVM y -DUSE_TLB); su tarea será escribir el código para manejar el TLB e implantar la memoria virtual
• En el proyecto #2 se utilizaron tablas de páginas para simplificar la asignación de memoria y aislar los fallos a un espacio de direcciones, de manera que no afecten a otros programas
• Para esta fase, el hardware no sabe nada de las tablas de páginas
• En su lugar, solo trabaja con un cache, cargado por software (el sistema operativo, alias usted) de las entradas de las tablas de páginas, denominado TLB
• En casi todas las arquitecturas modernas se incorpora un TLB a fin de aligerar las traducciones virtuales a físicas del espacio de direcciones
• Dada una dirección lógica de memoria (una instrucción que se desea buscar o un dato para cargar o guardar), el procesador primero busca en el TLB para determinar si el mapeo de esa dirección virtual a la dirección física ya se conoce
• Si es así (acierto TLB o "TLB hit") entonces la traducción puede efectuarse rápidamente
• Pero si el mapeo no se encuentra en el TLB (fallo TLB o "TLB miss") entonces se deben acceder las tablas de páginas y/o de segmentos
• En muchas arquitecturas, entre ellas NachOS, DEC MIPS y las HP Snakes, un fallo TLB causa una trampa al kernel del sistema operativo, que se encarga de efectuar la traducción, carga la traducción en el TLB y regresa al programa que efectuó el fallo
• Esto permite al kernel del sistema operativo elegir entre cualquier combinación de tabla de páginas, tabla de segmentos, tabla invertida, etc., necesaria para llevar a cabo la traducción de la dirección
• En sistemas que no utilicen TLB basado en software, entonces el hardware realiza la misma labor, pero en este caso el hardware debe especificar el formato exacto para las tablas de páginas y segmentos
• Por esta razón las TLB manipuladas por software son más flexibles, al costo de ser un poco más lentas para manejar los fallos TLB. Si estos fallos son muy infrecuentes, el impacto en el desempeño de un sistema TLB manejado por software es mínimo
• La ilusión de tener memoria ilimitada es provista por el sistema operativo, utilizando la memoria principal como un cache para el disco (swap)
• Para esta asignación, la traducción de las direcciones de las páginas de lógicas a físicas, permite la flexibilidad de traer páginas del disco al momento en que sean solicitadas
• Cada entrada en el TLB posee un bit de validez:
• Si el número de la página lógica está en la TLB (TLB hit) y este bit está encendido entonces la página está en memoria
• Si está apagado o el número de página virtual no está en el TLB, se necesita consultar a una tabla de páginas administrada por software (SO, alias usted) para determinar si la página está en memoria o si la página debe ser traída del disco (swap), en ambos casos la entrada de traducción debe ser agregada la TLB
• Adicionalmente, el hardware enciende el bit de uso (use bit) cada vez que la página se utiliza y el bit de suciedad (dirty bit) si el contenido fue modificado en la entrada correspondiente de la TLB
• Cuando el programa hace referencia a una página que no se encuentra en el TLB, el hardware genera una excepción de falta de página (PageFault exception), llevando el control al kernel (ExceptionHandleren NachOS)
• El kernel, verifica en la tabla de páginas del hilo/proceso, si la página no está en memoria, entonces lee la página del disco, busca un marco ("frame") libre, corrige la entrada en la tabla de páginas para apuntar a la nueva página, actualiza la TLB y luego devuelve el control al programa que produjo la excepción
• Por supuesto, el kernel debe encontrar primero espacio en la memoria principal para esta nueva página que debe ser traída, probablemente desocupando una casilla y escribiendo esa página removida en el disco (swap), si ésta fue modificada antes (dirty)
• Como en cualquier sistema de caching, el desempeño depende de la estrategia para determinar cuáles de las páginas permanecen en memoria y cuáles se mantienen en el disco
• En un fallo de página, el kernel debe decidir cuál de las páginas va a reemplazar; idealmente debe reemplazar aquella que no se va a utilizar por un largo tiempo, manteniendo en memoria solamente las páginas que van a ser referenciadas pronto
• Otra consideración importante, es que si la página que se reemplaza había sido modificada, ésta debe ser guardada en el disco antes de traer la nueva
• En muchos sistemas de memoria virtual (como UNIX) se evita ese gasto de tiempo extra, escribiendo las páginas al disco por adelantado, de manera que cualquier fallo de página posterior podrá ser completado más rápidamente

• Sección de preguntas (para entender el funcionamiento de la cache y memoria virtual en NachOS debe conocer las respuestar a estas preguntas y las funcionalidad indicadas

• ¿Qué es un "page fault"?
• Para la lectura/escritura de datos a la memoria, el simulador utilizar los métodos "machine::ReadMem" y "machine::WriteMem". Estos métodos utilizan direcciones virtuales o lógicas debe entender ¿Por qué?, además debe comprender por qué es posible que estos métodos retornen falso
• Entender el funcionamiento del método "machine::Translate, parámetros, valor de retorno
• ¿Qué es un "TLB"?
• Comprender la composición de las entradas de la "page table"
• Comprender la composición de las entradas de la "TLB"
• En los cambios de contexto, ¿Cuál debe ser el valor inicial de esta estructura, cuando un proceso recién comienza su ciclo de CPU?
• ¿Qué representa la variable "tlb" en la clase "Machine"? ¿Cuántas hay?
• Entender el significado de "TLB es una cache de la tabla de páginas"
• Comprender la función de los métodos "AddrSpace::RestoreState" y "AddrSpace::SaveState" la "page table"
• Comprender cuándo son llamados estos métodos
• Comprender para qué sirven las variables "pageTable" y "tlb" declaradas en la clase "Machine"
• Explicar cómo se realiza la búsqueda de la dirección lógica en el método "machine::Translate"
• Casos en el que el simulador utiliza la variable "pageTable"
• Casos en el que el simulador utiliza la variable "tlb"
• ¿Cómo se determina que la página es válida?
• Funcionalidad de la variable "entry"
• Mapeo de la dirección lógica a la dirección física
• ¿Qué representa la variable "pageFrame"?
• ¿Cómo se deriva la dirección física y cómo es devuelta por el método "machine::Translate"?
• Entender cómo se modifican los valores de "use" y "dirty" y en cuál estructura ocurren los cambios
• Identificar y comprender los casos en que son generadas excepciones en el método "machine::AddrSpace"
• Comprender cómo resolver cada uno de los casos en que ocurre una excepción "PageFaultException" en el método "machine::Translate"
• ¿Es posible que en los casos anteriores la página si esté en memoria? ¿Cómo determinar si la página realmente no está en memoria?
• Explicar cómo proceder con los otros tipos de excepciones
• El simulador de MIPS no avanza los contadores de programa cuando ocurren las excepciones, en el caso de "SysCallException", lo tuvimos que realizar 'manualmente', analizar que debería ocurrir con los tipos de excepciones encontrados
• Comprender cómo conseguir los marcos de memoria para asignarlos a las páginas faltantes
• ¿Cómo aplicar los algoritmos de reemplazo?
• ¿Qué pasa si toda la memoria física está llena?
• ¿Cómo reemplazar marcos de memoria?
• ¿Cómo determinar si un marco debe ir al SWAP?
• Comprender cómo conseguir la página faltante
• Determinar el origen de la página faltante, recordar los segmentos de los programas MIPS
• ¿Cómo recuperar la página faltante?
• ¿Puede estar en el archivo ejecutable original?
• ¿Puede estar en el SWAP?
• ¿Cuáles estructuras debe actualizar para no volver a producir la excepción?
• SWAP
• Conocer la estructura interna del archivo de intercambio
• Conocer el momento en que el archivo debe construirse y destruirse
• ¿Cómo determinar la cantidad de elementos que debe contener?
• Estrategia a seguir para determinar cuáles elementos están ocupados/libres

• Instrucciones

1. Implantar en NachOS el TLB administrado por software
• Para ello es necesario crear un sistema de traducción manipulado por software que maneje los fallos TLB
• Revise la traducción de direcciones lógicas a físicas que ocurren en el método "Translate" en el archivo "translate.cc" del directorio "machine"
• Investigue cómo se realizan las traducciones y los tipos de excepciones que se pueden generar, ponga especial atención a "PageFaultException"
• Determine qué cosas debe cambiar para que esa excepción no ocurra de nuevo cuando se re-ejecuta la instrucción
• Note que utilizando en el compilador la bandera "-DUSE_TLB", el hardware no utiliza los registros para las tablas de páginas; por lo que es necesario asegurarse de que el estado de la TLB es colocado correctamente en los cambios de contexto
• Revise el método "RestoreState" de la clase "AddrSpace"
• Revise los "ASSERT" que se encuentran al principio del método "Translate"
• Intente correr el programa de usuario "halt" y determine que ocurre
• Corrija el método "RestoreState" para que no inicialice la variable "machine->pageTable" ni "machine->pageTableSize", utilice compilación condicional para que el proyecto de "userprog" no se estropee y los siga utilizando
void AddrSpace::RestoreState() { #ifndef VM machine->pageTable = pageTable; machine->pageTableSize = numPages; #endif }
• Muchos de los sistemas lo que hacen es invalidar al TLB completamente cada vez que ocurre un cambio de contexto; las entradas se van recargando conforme las páginas son referenciadas nuevamente
• Para el ítem 2, su esquema de traducción de páginas debe llevar cuentas de las páginas sucias y utilizar las banderas que el hardware coloca en las entradas del TLB
2. Implantar memoria virtual
• Para ello se necesitan rutinas para mover páginas del disco a la memoria y viceversa
• Se recomienda que utilice el sistema de archivos de NachOS como área de respaldo (backing-store), de esta manera, cuando se implante el sistema de archivos en la asignación 4, es posible utilizar el sistema de memoria virtual como un caso de prueba
• A fin de encontrar las páginas que no se referencian y sacarlas cuando ocurre un fallo de página, es necesario llevar pista de todas las páginas que están siendo utilizadas en el sistema
• Una manera simple de hacer esto, es empleando un "core map", que es básicamente una tabla de páginas invertida, en lugar de traducir números de página virtual en números de páginas físicas (marcos), un "core map" traduce de número de página física al número de página virtual del hilo/proceso que está utilizando esa página física
3. Evalúe el desempeño de su sistema. Los fallos de cache (en este caso fallos TLB y fallos de página) pueden ser divididos en tres categorías:
• "Compulsory misses", aquellos que ocurren debido a la primera referencia de un item; siempre la página debe ser traída del disco y colocada en la memoria y en el TLB
• "Capacity misses", aquellos debidos al tamaño del cache; si el "working set" del programa de mayor que la memoria principal o que el número de entradas en el TLB, el programa incurre en estos fallos. Estos ocurren en un cache que no es infinita
• "Conflict misses", aquellos debidos a la política de reemplazo del cache. No ocurrirían si el cache utilizara una política óptima para efectuar el reemplazo de sus páginas, para el mismo programa en un cache del mismo tamaño
4. Escriba un conjunto de programas de usuario "útiles" para demostrar fallos de TLB y páginas (pocos y muchos fallos)
• En otras palabras, escriba un programa de usuario de prueba que muestre cuando ocurren pocos fallos en el TLB; otro que muestre cuando ocurren pocos fallos de página; otro que muestre cuando ocurren muchos fallos de TLB; etc.
• Como ejemplo, se presentan los programas "sort.c" y "matmult.c" en el directorio "test" que presentan un gran número de "conflict misses" para la mayoría de políticas de administración
• Para cada caso de prueba, explique el desempeño de su sistema e indique como se podría mejorar
5. Probablemente le resulte útil reducir el tamaño de la memoria (en machine.h) para provocar más rápidamente el comportamiento de la paginación

• La memoria de la máquina MIPS se establece en 32 páginas
• Programa de usuario "halt"
• Verifique el programa de usuario "halt" funcione, debe hacer tres faltas de página:
• Falta en la página lógica 0, dirección 0
• Falta en la página lógica 1, dirección 208
• Falta en la página lógica 9, dirección 1260
• Puede comprobar las referencias generadas empleando la bandera de debug "-d a" cuando corre el programa nachos (./nachos -d a -x ../test/halt)
• También puede utilizar el "debugger" para analizar los resultados
• Programa de usuario "halt2.lab"
• Verifique el programa de usuario halt2.lab funcione, debe hacer tres faltas de página:
• Falta en la página lógica 0, dirección 0
• Falta en la página lógica 1, dirección 272
• Falta en la página lógica 9, dirección 1388
• Programa de usuario "matmult5.lab"
• Para la dimensión 5 matmult5.lab :
• La salida del programa es 80, "Exit" debe funcionar para visualizarlo
• El programa produce 11 faltas de página
• Ninguna página es movida al SWAP
• Programa de usuario "matmult20.lab"
• Para la dimensión 20 matmult20.lab :
• La salida del programa es 7720, "Exit" debe funcionar para visualizarlo
• El programa produce 115 faltas de página (Seconde Chance)
• Hubo 46 páginas que debieron ser movidas al SWAP
• Programa de usuario sort
• El menor elemento del arreglo es cero
• El programa produce 4549 faltas de página (Seconde Chance enhanced)
• Hubo 2256 páginas que debieron ser movidas al SWAP
• Hubo 2249 páginas que fueron recuperadas del SWAP
• Intente correr el progrma "shell", dentro de este correr "sort" y luego "hatl"

[farroyo@cloud vm]$ ./nachos -x ../test/shell
--../test/sort
--../test/halt
Machine halting!

Ticks: total 18858910, idle 0, system 51360, user 18807550
Disk I/O: reads 2467, writes 2474
Console I/O: reads 26, writes 2
Paging: faults 2528 pages not in memory, 1458137 PageFaultExceptions
Network I/O: packets received 0, sent 0

• Como se muestra hay 2528 faltas de página
• El programa produce 1458137 faltas de página (Seconde Chance)
• Hubo 2474 páginas que debieron ser movidas al SWAP
• Hubo 2467 páginas que fueron recuperadas del SWAP
• Cambiando la memoria física a 4 páginas, el programa de usuario sort.lab
• El mayor elemento del arreglo es 1023
• El programa produce 1851363 faltas de página (Seconde Chance)
• Hubo 532493 páginas que debieron ser movidas al SWAP
• Hubo 532460 páginas que fueron recuperadas del SWAP

           [NachOS ...]
              O
             o  
      (\___/)
      (=` o`)
      (_(")(")