Proyecto NachOS - Asignación No. 1
Construcción de un Sistema de Threads
-
Presentación
- Inspirado en el trabajo original de Thomas E. Anderson (Computer Science Division, University of California at Berkeley)
- Traducción al castellano por Federico A. Meza y Francisco Arroyo
(Escuela de Ciencias de la Computación e Informática, Universidad de Costa Rica)
-
Descripción
- Para esta asignación se suministra parte de un sistema de threads operativo. El trabajo de cada estudiante será completarlo y utilizarlo luego para resolver varios problemas de sincronización
- El primer paso es leer y entender el sistema suministrado
- Este sistema ya implanta el llamado al sistema Fork para Threads, finalización de threads y semáforos para sincronización
- Ejecute el programa "nachos" para una prueba simple del código
- Siga minuciosamente esta ejecución ("a pie") para este caso simple que se muestra
- NachOS tiene varias opciones para realizar "debugging" que se pueden activar desde la línea de comandos, para poder utilizarlas debe revisar el archivo "main.cc" del directorio "threads"
- Cuando se está siguiendo el código es útil llevar registro del estado de cada thread
- El estudiante notará que cuando un thread hace un llamado a la función SWITCH, otro thread comienza a ejecutarse, y la primera acción que toma el nuevo thread es retornar de la función SWITCH
- Aunque sabemos que este comentario parecerá un poco críptico en este momento, también sabemos que el estudiante entenderá los threads una vez que comprenda qué el SWITCH que es llamado es distinto del SWITCH que retorna
- Los archivos necesarios para esta asignación, y cuyo código fuente se adjunta, son los siguientes:
- main.cc, threadtest.ccr, una prueba simple de nuestras rutinas de threads
- thread.h, thread.cc, estructuras para los threads y operaciones tales como fork, yield, finish, etc.
- scheduler.h, schecduler.cc, administración de la lista de threads listos para ejecución
- synch.h, synch.cc, rutinas de sincronización, semáforos, locks y variables de condición
- list.h, list.cc, manejo de listas genéricas (LISP en C++)
- synchlist.h, synchlist.cc, acceso sincronizado a listas utilizando locks y variables de condición (útil como ejemplo del uso de las primitivas de sincronización)
- system.h, system.cc, rutinas de startup/shutdown de NachOS
- switch.h, switch.s, magia en lenguaje ensamblador para inicializar los threads y para lograr los cambios de contexto entre ellos
- interrup.h, interrup.cc, manejo de la habilitación y deshabilitación de interrupciones, como parte de la emulación de la máquina
- timer.h, timer.cc, emulación de un reloj que provoca una interrupción periódicamente
- stats.h, recopilación de estadísticas interesantes
- Un código sincronizado adecuadamente debe funcionar bien sin importar el orden de ejecución que elija el administrador de los threads listos. En otras palabras, deberíamos estar en capacidad de agregar llamados a la función Thread::Yield (la que provoca que el administrador elija otro hilo para su ejecución), en cualquier lugar del código donde las interrupciones se encuentren habilitadas, sin que esto cambie la correctitud del código
- Como parte de futuras asignaciones se pedirá al estudiante que escriba código sincronizado apropiadamente, así que es crucial entender cómo hacer esto para poder completar el proyecto
- Como una ayuda en este sentido, el código enlazado dentro de NachOS provocará llamados a Thread::Yield de forma repetitiva (aleatoria) pero impredecible
- El código de NachOS es reproducible en el sentido de que si se llama repetidamente con los mismos parámetros hará exactamente las mismas cosas cada vez, incluyendo los llamados 'aleatorios' a Thread::Yield
- Sin embargo, si se invoca con el parámetro "-rs #", con un número diferente cada vez, los llamados en mención se insertarán en distintos lugares del código, cuidando siempre de colocarlos en lugares donde estén habilitadas las interrupciones
- El estudiante deberá asegurarse de emplear varios casos de prueba para las soluciones a los problemas, incluyendo modificaciones al parámetro referido antes. Por ejemplo, para la parte número 2, debería crear múltiples productores y consumidores y demostrar que los resultados pueden variar ligeramente, por supuesto dentro de ciertos límites
- Advertencia: en nuestra implantación a cada thread se le asigna una pequeña pila de ejecución de tamaño fijo. Esto puede provocar errores muy raros (como faltas de segmentación ["segmentation fault"] y extrañas líneas de código), si se declaran estructuras de datos muy grandes como variables automáticas (e.g. int buf[1000])
- Probablemente no se presenten este tipo de problemas, pero en caso de aparecer, podría cambiarse el tamaño de la pila modificando la definición de StackSize dentro del archivo switch.h
- Aunque las soluciones pueden escribirse como rutinas normales de C, el estudiante encontrará que la organización del código es más sencilla si estructura su código como clases de C++. Además, no debe haber ningún tipo de espera ocupado (busy-waiting) en las soluciones de esta asignación
- Para este proyecto los puntos a resolver se enumeran a continuación:
- Implante locks y variables de condición
- Puede utilizar semáforos como bloque de construcción, o en su defecto, rutinas más primitivas de threads como Thread::Sleep
- En el archivo synch.h, se muestra la interfaz pública a locks y variables de condición
- Deben definirse como privados los datos e implantar el cuerpo de la interfaz. Observe que no debe generar mucho código para lograr esta implantación
- Resolver un problema de sincronización, a continuación mostramos unos ejemplos
- Problema del agua H2O: Usted ha sido contratado por la Madre Naturaleza para ayudarla con la reacción química para formar agua, la que parece que no se está llevando a cabo bien por problemas de sincronización
- El truco es reunir dos átomos de hidrógeno (H) y uno de oxígeno (O)
- Para este problema los átomos son procesos/hilos, cada átomo de H llama a un procedimiento Hlisto cuando está listo para reaccionar y cada átomo de oxígeno llama a un procedimiento Olisto
- Para este problema usted debe escribir el código para los procedimientos Hlisto y Olisto utilizando semáforos
- Los procedimientos deben sincronizar los átomos hasta que haya al menos dos átomos de H y un de O, entonces uno de los procedimientos debe llamar a HacerAgua, después del cual dos procesos H y un O deben terminar
- Su solución debe evitar la inanición y la espera ocupada
- Dilema de los filósofos
- Problema de la barbería
- Problema de los caníbales y misioneros
- En su trabajo con el MOPT debe hacer un sistema que sincronice el tráfico que circula por un débil puente angosto ubicado en una carretera pública (Barranca)
- El puente solo permite el flujo de vehículos en un sentido a la vez, y si por alguna razón tres o más vehículos se encuentran sobre el puente a la vez, la estructura colapsará por el peso
- En este sistema cada carro se puede representar por un hilo, el cual ejecutará el procedimiento UnCarro cuando llega al puente:
UnCarro( int direc ) {
LlegaPuente( direc );
CruzaPuente( direc );
SalePuente( direc );
}
El parámetro direc puede ser 1 o 0 e indica el sentido con que el vehículo cruzará el puente
Utilizando locks y variables de condición, escriba los procedimientos LlegaPuente y SalePuente
El procedimiento CruzaPuente solo debe desplegar un mensaje informativo
LlegaPuente no debe retornar hasta que sea seguro para el carro cruzar el puente en la dirección solicitada (debe garantizar que no habrán colisiones de frente y que el puente no se derrumbará)
Un thread llama a SalePuente para indicar que el carro que representa ha terminado de cruzar el puente, además deben tomarse las acciones necesarias para garantizar que otros carros puedan cruzar el puente
En primera instancia considere que el puente se encuentra en una carretera de poco tráfico, por lo que no es necesario garantizar que la solución no lleve a interbloqueos indefinidos (deadlocks) o provoque inanición (starvation)
