Proyecto Programado # 2

Universidad de Costa Rica

Escuela de Ciencias de la Computación e Informática

CI-1310 Sistemas Operativos

• Descripción

• En la tercera fase de Nachos se investigará el uso de caching que se utilizará en esta tarea con dos propósitos:
• Primero, se va a emplear un traductor de direcciones basado en software (Translation Lookaside Buffer [TLB]) como 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 del espacio de direcciones
• Dada una dirección 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 la dirección virtual a la dirección física ya se conoce
• Si es así (acierto TLB) entonces la traducción puede efectuarse rápidamente
• Pero si el mapeo no se encuentra en el TLB (fallo TLB) 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, permite la flexibilidad de traer páginas del disco en el momento en que se necesiten
• Cada entrada en el TLB posee un bit de validez:
• Si el bit está encendido entonces la página virtual está en memoria, solo se debe actualizar el TLB
• Si está apagado o la página virtual no está en el TLB, entonces se necesita una tabla de páginas administrada por software (SO, alias usted) para saber si la página está en memoria (cargando el TLB cuando se efectúe la traducción) o si la página debe ser traída del disco (swap)
• Adicionalmente, el hardware coloca el bit de uso cada vez que la página se utiliza y el bit de suciedad si el contenido fue modificado.
• 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 (ExceptionHandler)
• 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, corrige la entrada en la tabla para apuntar a la nueva página y luego pasa 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

• Direcciones

1. Implantar 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 la bandera "DUSE_TLB" en tiempo de compilación, el hardware no utiliza 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
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ía:
• "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 fallos. Estos ocurren en un cache que no es infinito
• "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