PRÁCTICAS DE LABORATORIO DE SISTEMAS OPERATIVOS

TERCERA PRÁCTICA OBLIGATORIA (2002-03)

Batalla

  1. Enunciado.

    El programa propuesto constará de un único fichero fuente, batalla.c, cuya adecuada compilación producirá el ejecutable batalla. En esencia, la acción del programa se desarrolla sobre un tablero parecido al del ajedrez, pero de 16x8 escaques. Sobre este tablero evolucionan dos equipos de fichas, las blancas y las negras. Cada equipo está formado por un rey inmortal y un número variable de torres. Estas figuras se mueven siguiendo las mismas reglas que sus homónimas del ajedrez: el rey a cualquiera de las ocho casillas más próximas y las torres, cualquier número de casillas horizontal o verticalmente siempre que no se salte sobre otra ficha intermedia. La imagen que se verá en la simulación será parecida a la siguiente:



    No obstante, el juego difiere respecto al del ajedrez en lo siguiente: El juego durará 30 segundos, terminados los cuales se contabilizarán el número de movimientos producidos, siendo mejor el resultado de la práctica cuantos más movimientos se hayan realizado.

    Batalla acepta un máximo de dos argumentos por la línea de órdenes. Si no se introducen argumentos, se imprimirá un mensaje con la forma de uso del programa por el canal de error estándar. En el caso de teclear un argumento, dicho argumento será un número entero mayor o igual que cero relacionado con la rapidez con que se producen los acontecimientos en el programa. Cero indica la máxima rapidez y números mayores suponen una rapidez progresivamente menor. Finalmente, si son dos los parámetros introducidos, el primero es idéntico al caso anterior y el segundo será una "D", indicando que se desea que el programa produzca información de depuración por el canal de errores estándar.

    Para facilitar la tarea, tenéis a vuestra disposición una biblioteca de funciones de enlazado dinámico batalla.dll y un fichero de cabeceras, batalla.h. Gracias a la biblioteca, muchas de las funciones no las tendréis que programar sino que invocarlas a la DLL, tal como se explica en la sesión decimoquinta. La biblioteca creará un hilo adicional a los vuestros para su funcionamiento interno. Una descripción detallada de las funciones de la biblioteca aparece más abajo en esta misma página.

    El programa, desde vuestro punto de vista, constará de tantos hilos como fichas se encuentren sobre el tablero en cada momento. Cuando una ficha aparece, se tendrá que que crear un nuevo hilo para que mueva esa ficha. Cuando una ficha es comida, debe finalizar el hilo asociado con esa ficha.

    Características adicionales que programar



    Biblioteca batalla.dll

    Con estra práctica se trata de que aprendáis a sincronizar y comunicar hilos en WIN32. Su objetivo no es la programación. Es por ello que se os suministra una biblioteca dinámica de funciones ya programadas para tratar de que no tengáis que preocuparos por la presentación por pantalla, la gestión de estructuras de datos (colas, pilas, ...) , etc. También servirá para que se detecten de un modo automático errores que se produzcan en vuestro código. Para que vuestro programa funcione, necesitáis la propia biblioteca batalla.dll y el fichero de cabeceras batalla.h.
    Ficheros necesarios:


    La única función que debéis usar de la biblioteca es:

    Cuando un hilo desea mover su ficha, debe mandar un mensaje al hilo de la biblioteca, cuyo identificador devolvió la función inicio. Las características del mensaje enviado deben ser:
    1. Tipo de mensaje: WM_USER.
    2. wParam: un entero cuyo valor expresa los escaques origen y destino de la ficha movida. Observando la figura de esta página, se ve que cada cuadro viene identificado unívocamente por un par de dígitos hexadecimales, el primero para la fila (0-7) y el segundo para la columna (0-F). El rey blanco se encuentra en la posición 0x4B. Si se deseara mover en diagonal hacia abajo, posición 0x5C, wParam debe valer 0x4B5C.
    3. lParam: identificador del hilo que envía el mensaje.
    Cuando la biblioteca haya realizado el movimiento, responderá al hilo enviando, a su vez, el mismo mensaje que recibió de él o un mensaje de tipo WM_USER+1 con los mismos parámetros que los enviados si es que se produjo un error. Si se produce un error, la biblioteca dejará de atender mensajes para mejor poder depurar la situación.

    En el caso de que esté activada la opción de depuración, la biblioteca producirá por el canal de errores estándar una línea por cada movimiento que atienda. En la línea aparecerá el identificador que declaró el hilo al mandar el mensaje ordenando el movimiento, las celdas de origen y destino y un esquema del movimiento que se ha producido.

    Cuando el programa acabe, bien por un error, bien porque se han alcanzado los 30s, se debe mandar un mensaje de tipo WM_USER+1 y wParam igual a 0x1234 a la biblioteca para indicar que debe concluir el hilo gestor de mensajes. La biblioteca imprimirá el número de movimientos que ha atendido hasta ese momento.

  2. Pasos recomendados para la realización de la práctica

    En esta tercera práctica, no os indicaré los pasos que podéis seguir. El proceso de aprendizaje es duro, y ya llega el momento en que debéis andar vuestros propios pasos, aunque exista la posibilidad de caerse al principio.

  3. Plazo de presentación.

    Hasta el miércoles 18 de junio de 2003, inclusive e improrrogable.

  4. Normas de presentación.

    Acá están. Además de estas normas, en esta práctica se debe entregar un esquema donde aparezcan los mecanismos de sincronización usados, sus valores iniciales y un seudocódigo sencillo para cada hilo con las operaciones realizadas sobre ellos. Por ejemplo, si se tratara de sincronizar con eventos dos hilos C y V para que produjeran alternativamente consonantes y vocales, comenzando por una consonante, deberíais entregar algo parecido a esto: 
         EVENTOS Y VALOR INICIAL: EC* (automático), EV (automático).

     SEUDOCÓDIGO:

             C                                V
            ===                              ===
       Por_siempre_jamás               Por _siempre_jamás
          {                               {
           W(EC)                           W(EV)
           escribir_consonante             escribir_vocal
           Set(EV)                         Set(EC)
           }                               }
    Debéis indicar, asimismo, en el caso de que las hayáis realizado, las optimizaciones de código realizadas para producir más movimientos en 30s.

  5. Evaluación de la práctica.

    Dada la dificultad para la corrección de programación en paralelo, el criterio que se seguirá para la evaluación de la práctica será: si
    1. la práctica cumple las especificaciones de este enunciado y,
    2. la práctica no falla en ninguna de las ejecuciones a las que se somete y,
    3. no se descubre en la práctica ningún fallo de construcción que pudiera hacerla fallar, por muy remota que sea esa posibilidad...
    se aplicará el principio de "presunción de inocencia" y la práctica estará aprobada. La nota, a partir de ahí, dependerá de la simplicidad de las técnicas de sincronización usadas, de las optimizaciones realizadas para producir más movimientos, etc.

  6. LPEs.

    1. ¿Deben los hilos que mueven las fichas disponer de algún tipo de "inteligencia"? No es necesario siempre que se respeten las reglas. Pueden moverse al azar o siguiendo una programación, a vuestra elección. Eso sí, deben intentar moverse continuamente y deben ser posibles todos los movimientos, tanto del rey como de las torres. No valen reyes que no se muevan en diagonal o torres que se muevan de un cuadro al de al lado, por más que sean movimientos legales.
    2. No debéis usar la función TerminateThread para acabar con los hilos. El problema de esta función es que está diseñada para ser usada sólo en condiciones excepcionales y el hilo muere abruptamente. Puede dejar estructuras colgando e ir llenando la memoria virtual del proceso con basura.
    3. Para ver si una ficha está amenazada disponéis de varias posibilidades, alguna de las cuales son:
      1. Ir recorriendo el tablero hasta que encontréis una ficha enemiga y ver si dicha ficha amenaza o no.
      2. Podéis mejorar el algoritmo con una cola que almacene la posición de las fichas enemigas para no tener que recorrer el tablero. Cuando nace o muere una ficha enemiga debéis modificar el array.
      3. Es posible que llevéis un control en un array de las posiciones que están siendo amenazadas por uno u otro bando en cada momento. Cuando nace, muere o se mueve cualquier ficha, debéis recalcular el array.
      4. La mejor solución, bajo mi punto de vista, es que la ficha "se asome" y mire a ver a su alrededor si está el rey enemigo y en horizontal y vertical si hay una torre enemiga (que no esté tapada por una ficha propia). Esto es más rápido, y no requiere actualizaciones ni almacenamientos adicionales. Una delicia, vamos.
    4. Cuando ejecuto la práctica depurando me aparece La casilla origen no contiene una ficha válida. Cuando examino la casilla, compruebo que todo es correcto. ¿A qué puede ser debido?

      Este mensaje u otros similares que parecen estar equivocados tienen su razón en que estáis "manchando" la pantalla con mensajes propios o de depuración. Si estos mensajes sobreescriben el tablero, cuando la biblioteca va a mirar qué ficha hay en un determinado lugar, no reconoce ninguna ficha y da el error. Para evitar este tipo de mensajes, mejor depurad la práctica enviando la información de trazado a un fichero añadiendo al final de la línea de órdenes 2>salida. De este modo, toda la información aparecerá en el fichero salida.
    5. Tengo muchos problemas a la hora de llamar a la función inicio de la biblioteca. No consigo de ningún modo acceder a ella.

      El proceso detallado viene en la última sesión. De todos modos, soléis tener problemas en una conversión de tipos, aunque no os deis cuenta de ello. No voy a deciros qué es lo que tenéis que poner para que funcione, pues lo pondríais y no aprenderíais nada. Sin embargo y dada la cantidad de personas con problemas, aquí viene una pequeña guía:
      1. Primero debéis definir una variable puntero a función. El nombre de la variable es irrelevante, pero podemos llamarle inicio por lo que veremos más abajo. Para definir el tipo de esta variable correctamente, debéis conocer cómo son los punteros a función. En la sesión quinta, se describe una función, atexit. Dicha función en sí no es importante para lo que nos traemos entre manos, pero sí el argumento que tiene. Ese argumento es un puntero a función. Fijándoos en ese argumento, no os resultará difícil generalizarlo para poner un puntero a funciones que admiten un (LONG,BOOL) y devuelven un DWORD. Notad, además, que, al contrario que ocurre con las variables "normales", la definición de una variable puntero a función es especial por cuanto su definición no va sólo antes del nombre de la variable, sino que lo rodea. Tenéis que poner algo similar a: #$%&%$ inicio $%&$·@;, es decir, algo por delante y algo por detrás.
      2. Después de cargar la biblioteca como dice en la última sesión, debéis dar valor al puntero de función. Dicho valor lo va a proporcionar GetProcAddress. Pero, ¡cuidado!, GetProcAddress devuelve un FARPROC, que sólo funciona con punteros a funciones que devuelven int y no se les pasa nada (void). Debéis hacer el correspondiente casting. Para ello, de la definición de vuestro puntero, quitáis el nombre, lo ponéis todo entre paréntesis y lo añadís delante de GetProcAddress, como siempre.
      3. Ya podéis llamar a la función como si de una función normal se tratara. Ponéis el nombre del puntero y los argumentos entre paréntesis. Como os advertí más arriba, si habéis puesto inicio como nombre al puntero, ahora no se diferenciarán en nada vuestras llamadas a la función respecto a si dicha función no perteneciera a una DLL y la hubierais programado vosotros.
    6. Hay que tener cuidado cuando creéis los hilos de las torres. El problema también puede aparecer en el hilo de los reyes, aunque es menos habitual. El problema surge cuando debemos pasar los argumentos a la función del hilo que moverá una nueva torre. Lo habitual es que uséis una estructura y paséis a la función del hilo un puntero a dicha estructura. Sin embargo, considerad que si usáis una única estructura para pasar los parámetros a todas las torres puede ocurrir que en el caso de que se creen dos seguidas, los parámetros de la segunda machaquen a los de la primera antes de que esta pueda leerlos. Es conveniente, pues, que uséis una estructura diferente para cada torre y eso lo conseguís mediante memoria dinámica. Tampoco debéis olvidar liberar la memoria cuando el hilo muere.
    7. También tenéis problemas para "avisar" a un hilo de una torre que debe morirse (cuando la han matado). La solución podría consistir en hacer que las torres estén ejecutando su secuencia dentro de un bucle while. La condición de permanencia vendrá en función de dos variables, una es común para todos los hilos y marca si los 30s han pasado y la otra indicará si la ficha ha sido comida y será diferente para cada torre, evidentemente. Para que la ficha que come a la torre pueda cambiar el valor de esa variable, podéis almacenar un puntero a la variable en el cuadro donde se encuentre la ficha. Al comer, mediante ese puntero, podemos cambiar la variable del hilo asociado.
    8. Lo que no tiene muy fácil solución es saber cuándo se han muerto todos los hilos para poder mandar el mensaje de finalización al hilo de la biblioteca sin problemas. Es difícil conocer los HANDLEs de todos los hilos de las torres vivas en ese momento. Quizá una solución sea almacenar en las casillas del tablero el HANDLE del hilo que la está moviendo, pero puede ser complicado. En cualquier caso, se puede dar una solución ad hoc, no es tan importante para la práctica como otros asuntos. Tanto estas ideas como las anteriores son sólo eso, ideas para aquellos que no logréis evolucionar. No quiere decir que forzosamente debáis usarlas en lugar de otras posibilidades.


  7. Prácticas propuestas años anteriores.

© 2003 Guillermo González Talaván.