PRÁCTICAS DE LABORATORIO DE SISTEMAS OPERATIVOS

TERCERA PRÁCTICA OBLIGATORIA (2000-01)

Speedy Gonsales

1. Enunciado.

   Los semáforos de SS.OO. se pueden considerar como variables de tipo entero especiales. El alumno elaborará el código de dos funciones cuyo prototipo es:
   int S_Wait(LPLONG); e int S_Signal(LPLONG);
   
   Ambas funciones servirán para realizar las operaciones wait y signal sobre las variables enteras que reciben como argumentos consideradas como semáforos. Es evidente que, para realizar estas funciones no se pueden usar las llamadas a la API de sincronización de WIN32 (las que realizan semáforos, mutexes, exclusiones mutuas, eventos, etc.).
   
   Para probar los semáforos creados, se hará el siguiente programa sencillo:
   
   «Cerca de la frontera estadounidense con México se ubica la fábrica de queso ACME®. Speedy Gonsales y su primo Rahull llevan sin descanso quesos hasta su pueblo mientras que el gato Silvestre y su primo Rupestre tratan infructuosamente de atraparlos. Cansados de tanto correr detrás de ellos, los gatos deciden mover el queso que haya en el pueblo de vuelta a la fábrica. Y en eso se entretienen.»
   
   Basado en esta bonita recreación del duelo entre contrarios, con reminiscencias incluso al yin y el yang orientales, créese un programa para Windows NT en el que tanto los ratones como los gatos estén representados por hilos de ejecución. Existirán sendas variables para almacenar el número de quesos que hay en la fábrica y en el pueblo.
   
   La duración de la ejecución será de 30 segundos exactos. El final de la ejecución se marcará con una variable llamada silbato que valdrá falso al inicio y pasará a ser verdadero cuando el tiempo haya expirado.
   
   Cada segundo exacto, el programa deberá imprimir en la pantalla una línea con el siguiente formato:

   U.S.A.Fábrica:00000031 |FRONTERA| 00000069:Pueblo_México, SUMA:00000100.
   

   Los personajes, por su parte, realizarán sin descanso de ningún tipo las operaciones siguientes:
   1. Mientras no haya queso en el origen de su viaje se esperarán, consumiendo CPU si es preciso.
   2. Descontarán un queso del origen de su viaje.
   3. Incrementarán en un queso el destino de su viaje.
   4. Incrementarán en una unidad el número de viajes realizados.
   5. Si el tiempo ha terminado, acabarán su ejecución. Si no, continuarán moviendo quesos.
   Cuando el tiempo acabe, se esperará, sin consumo de CPU a que los hilos hayan terminado, se imprimirá una línea horizontal hecha con guiones, se imprimirá de nuevo el estado del sistema (número de quesos en la fábrica y en el pueblo), otra línea horizontal y el número de viajes realizados por cada uno de los personajes expresados en miles de viajes y la suma total de los viajes realizados, también expresada en miles de viajes. Se tendrá en cuenta este último valor para la calificación que será mejor cuantos más viajes se hayan efectuado en esos 30s.
   
   El programa, cuyo nombre será speedy recibirá como dos únicos argumentos el número de quesos que hay inicialmente en la fábrica y en el pueblo.
   
   Junto con el fichero fuente, el alumno deberá incluir sus respuestas a las siguientes preguntas:
   1. ¿Qué sistema se ha usado para lograr la atomicidad de las operaciones sobre los semáforos?
   2. ¿Por qué hay veces en que la suma que aparece es algo inferior al número de quesos que hay en total?
   3. ¿Puede darse el caso en la práctica realizada de que la suma total de quesos que aparezca en la pantalla supere los que había inicialmente? Razónese.
   4. En el caso de que el comportamiento sea diferente con pocos quesos (unos cien) y muchos (rondando el millón), razónese por qué es así.
   5. ¿Qué aspecto fundamental de los semáforos no hemos podido lograr al programarlos nosostros mismos y no usar los proporcionados por el sistema operativo?
   
   
   

2. Plazo de presentación.

   Hasta el viernes 8 de junio de 2001, inclusive e improrrogable.
   
   

3. Normas de presentación.

   Acá están. Hay una norma adicional: presentad las prácticas impresas en ambas caras del folio para evitar un consumo innecesario de papel y energía. Aunque esta práctica sea de Windows NT, debéis entregarla en tejo, como es habitual.
   
   

4. LPEs.

   1. En la parte de teoría de la asignatura vimos algunas maneras de implementar la exclusión mutua por hardware o por software sin ayuda del sistema operativo. Cualquiera de ellas nos servirá para lograr atomicidad sobre las operaciones sobre nuestros semáforos. Se puede usar también cualquier otra solución no vista en clase de demostrado cumplimiento de respeto de la exclusión mutua. En este caso, hay que incluir su demostración o una referencia a una publicación en que aparezca dicha demostración.
   2. En el caso de usar soluciones por software, considérese que cualquiera de las soluciones vistas en teoría es para dos procesos y habrá que generalizarla. Una posible generalización para el caso de los cuatro hilos (gatos y ratones) si queremos una zona de exclusión mutua para los cuatro es limitarla por dos secciones críticas anidadas, la exterior para separar ratones y gatos y la interior para separar primos entre sí:

      <<SECCIÓN CRÍTICA PARA GATOS Y RATONES-Comienzo>>
          /* Aquí hay o gatos o ratones, pero no los dos juntos */
          <<SECCIÓN CRÍTICA PARA PRIMOS-Comienzo>>
              /* Aquí no puede haber primos juntos, pero como fuera
                 no puede haber ratones y gatos juntos, aquí no puede
                 haber más de un hilo cada vez */
              ...
          <<SECCIÓN CRÍTICA PARA PRIMOS-Fin>>
      <<SECCIÓN CRÍTICA PARA GATOS Y RATONES-Fin>>
      

      Esta solución pudiera producir inanición en algún caso, pero no afecta al funcionamiento del programa. Las secciones críticas se refieren a las obtenidas mediante un algoritmo de Dekker o Peterson.
   3. Probablemente, no se pueda almacenar en una variable de tipo LONG el número total de viajes. Usad una unsigned long long o almacenad en dos variables, una para los miles de viajes y otra para el resto de viajes que hay hasta el próximo millar.
   4. Se pueden, aunque no es obligatorio, usar las funciones del grupo Interlocked... de WIN32. Sólo se podrá usar la función de la API Sleep para los hilos animales, aunque de nuevo no es obligatorio, con el argumento nulo [Sleep(0)], sabiendo que tiene como efecto colateral el ceder el resto de ráfaga de CPU. Sí se puede usar Sleep para la salida por pantalla o para contar los 30s totales de ejecución.
   5. Se podrán usar zonas de memoria compartida si es que es necesario.
   6. En los semáforos no se usará ningún mecanismo de colas cuando se tenga que "desbloquear" un proceso. Cuando otro proceso ejecute un signal, el primero de los que están esperando por el semáforo que lo descubra, se quedará con él.
   
   
   

5. Prácticas propuestas años anteriores.

   • Curso 1999-2000: El país Pokemon