Skip to content

Requerimientos del Hito 2 (Team)

Jump to bottom
Leo edited this page Sep 22, 2020 · 1 revision

Ingresar toda la información que crean que puede ser de ayuda en este documento!

Requerimientos del Hito 2:

  • Al iniciar el proceso, se deberá crear un hilo por cada entrenador existente y el proceso Team deberá conocer cuáles y qué cantidad de Pokémon de cada especie requiere en total para cumplir el objetivo global.

  • Al iniciar el proceso, se deberá suscribir a las colas APPEARED_POKEMON, LOCALIZED_POKEMON y CAUGHT_POKEMON. También deberá estar escuchando mediante una conexión de socket en la cual podrá recibir mensajes de apariciones de Pokémon.

  • Al aparecer un Pokémon (por cualquiera de los dos métodos antes explicados) sólo se podrá planificar a un entrenador hacia dicha posición independientemente de cuántos Pokémon de dicha especie haya en la posición en la que apareció.

  • Al planificar un entrenador, se activará el hilo del entrenador más cercano al Pokémon. Cada movimiento en el mapa responderá a un ciclo de CPU. Para simular más a la realidad esta funcionalidad, se deberá agregar un retardo de X segundos configurado por archivo de configuración.

  • Para planificar a los distintos entrenadores en este hito se utilizará el algoritmos FIFO.

Implementación

Al iniciar el proceso, se deberá crear un hilo por cada entrenador existente

  • Los hilos que representan a cada entrenador son los de pthread, cada uno de estos va a "representar" a cada entrenador y ejecutar cuando esté en el estado exec.
    Ventaja de usar pthread siendo un KLT?: _________________ (Nota: Hay que usar estos, ya que desde la cátedra lo indican)
  • Como puedo planificarlos yo, ya que el propio SO tiene su algoritmo de planificación?: Se puede lograr que ciertos hilos ejecuten y que otros queden en espera usando algunas syscalls bloqueantes(pueden variar, dependiendo de lo que estés haciendo en ese momento, pero en principio pueden ser reads por socket, semáforos,etc).
  • Yo no puedo modificar la función con la que se creo el hilo ni los argumentos ¿Como puedo lograr sin que termine el hilo que haga distintas cosas?: Podés crear hilos a los que le pasas una función y parámetros. En base a eso podés crear diferentes hilos que hagan lo que necesites.

Preguntas:

  • Un entrenador es un hilo, que no hace ninguna función (tal vez sea solo una variable pthread_t) hasta que pasa a exec. Cuando pasa a exec vos le asignas una función (ponele, capturarPokemon), y cuando sale de exec vos bloqueas el hilo para que no siga ejecutando?
  • Si los estados son listas de hilos siguiendo el mismo problema de arriba como puedo mantenerlos en espera? (puede que no sean listas también)
  • Un entrenador puede intercambiar un poquemon en estado bloqueado? De no ser asi en que caso un entrenador podria pasar directamente del estado Block al estado Exit como indica el diagrama de estados de la pag 25?

Estado de los hilos (Entrenadores)

Cada entrenador al iniciar en el sistema entrará en estado New. A medida que el Team empiece a recibir distintos Pokémon en el mapa despertara a los distintos entrenadores en estado New o en Blocked (que estén esperando para procesar) pasándolos a Ready. Siempre se planificará aquel entrenador que se encuentre sin estar realizando ninguna operación activamente y, en caso de existir más de uno, sea el que más cerca se encuentre del objetivo.

  • Como puedo planificarlos yo, ya que el propio SO tiene su algoritmo de planificación?: Se puede lograr que ciertos hilos ejecuten y que otros queden en espera usando algunas syscalls bloqueantes(pueden variar, dependiendo de lo que estés haciendo en ese momento, pero en principio pueden ser reads por socket, semáforos,etc). Podrías tener alguna estructura tuya que se parezca a un TCB y te permita saber en qué estado está cada uno de los hilos/entrenadores. De esta forma podes emular un algoritmo de planificación.

Suscripción a las colas

Completar_____________________

Tamaño del mapa

El mapa de coordenadas no tiene un "espacio", no es algo que vos creas o instancias, sino que vas a "simularlo" mediante tus Teams y GameCard. Con respecto a esto, Teams trabajan todos sobre el mismo mapa.

Como cargar el archivo de configuracion

Cargar el archivo de configuración en base a esta informacion Problema al cargar configuración de Team Solución

Resumen video Planificación

¿Qué hace el proceso Team?

  • Administrador de entrenadores
    • Posee una lista de entrenadores con objetivos.
    • Posee un Objetivo Global el cual cumplir el objetivo de los distintos entrenadores.
  • Mapa de dos coordenadas
    • Su objetivo es planificar a los entrenadores en dicho mapa.
  • Detección de Deadlock
    • Un Deadlock ocurre cuando un entrenador (proceso) tiene un Pokémon (recurso) que otro entrenador necesita, y a su vez, este último tiene otro Pokémon que el primer entrenador necesita.
  • Generación de metricas
    • Permite la comparación de métodos de planificación que el mismo posee.

Inicialización

Al levantar el proceso Team hay que seguir los siguientes pasos:

  1. Obtener los entrenadores y localizarlos

    Entrenador 1 Entrenador 2
    1 Pikachu 1 Pikachu
    1 Squirtle
    Pos: [1,2] Pos: [5,4]

    NO SE TIENE UN MAPA GRÁFICO, TODO ES ADMINISTRACIÓN DE MEMORIA

  2. Definir Objetivo Global

    Entrenador 1 Entrenador 2
    1 Pikachu 1 Pikachu
    1 Squirtle
    Pos: [1,2] Pos: [5,4]

    Por lo tanto, el Objetivo Global sería:

    • 1 Squirtle
    • 2 Pikachu

  3. Conexión al Broker

    El proceso Team se debe suscribir a 3 colas de mensajes:

    • APPEARED
    • CAUGHT
    • LOCALIZED

    LAS SUSCRIPCIONES SON INDEPENDIENTES. UN CONNECT() POR CADA SUSCRIPCION A UNA COLA. EL PROCESO TEAM ES CLIENTE DEL BROKER. EN CASO QUE EL BROKER NO EXISTA O NO SE PUEDA CONECTAR AL BROKER, EL PROCESO TEAM DEBE FUNCIONAR IGUAL. SE DEBE INTENTAR RECONECTAR AL BROKER CADA CIERTO PERIODO DE TIEMPO (se debe crear un thread para manejar esto)

  4. Envío de Mensajes GET

    Entrenador 1 Entrenador 2
    1 Pikachu 1 Pikachu
    1 Squirtle
    Pos: [1,2] Pos: [5,4]

    Por cada especie Pokemon requerida (definido en el Objetivo Global), se envia un mensaje Get al proceso Broker:

    • GET Squirtle
    • GET Pikachu

    CADA MENSAJE ES INDEPENDIENTE. UN CONNECT() POR CADA MENSAJE PARA ENVIAR AL BROKER (no se usan los mismos sockets de la suscripción, porque de ahí es donde se reciben mensajes de las colas suscriptas)

    Una vez enviado el mensaje, el socket creado para ese mensaje ya no se usa mas (se cierra esa conexión).

  5. Conexión con Game Boy

    Se tendra un socket de escucha que le permitirá al Game Boy enviar tres tipos de mensajes:

    • APPEARED
    • CAUGHT
    • LOCALIZED

    POR CADA MENSAJE SE RECIBIRÁ UN ACCEPT() (el proceso Game Boy realizará un connect() para enviar mensajes; y desde el proceso Team se hará un accept() para aceptar esa conexión)

Diagrama de Estados

Se utilizará un diagrama de 5 estados para representar los posibles estados de los entrenadores:

  • NEW
  • READY
  • EXEC
  • BLOCK
  • EXIT

SE TENDRÁ UN GRADO DE MULTIPROGRAMACIÓN 1, ES DECIR, SOLO UN ENTRENADOR EN ESTADO EXEC

Funcionamiento interno

Ejemplo N°1 (CASO FELIZ)

Entrenador 1 Entrenador 2
1 Pikachu 1 Pikachu
1 Squirtle
Pos: [1,2] Pos: [5,4]

Al enviar un mensaje GET por alguna de las dos especias requerias, obtendremos como respuesta un mensaje de tipo LOCALIZED

LOCALIZED Charmander 3 3 // Hay que verificar si yo necesito el Pokémon Charmander, en este caso, no es asi por lo tanto 
                            DESCARTO ESTE MENSAJE
LOCALIZED Squirtle 4 4 // Si lo necesito, ACEPTO EL MENSAJE
E1
 
 
Sq
E2

SOLAMENTE VOY A QUEDARME CON EL PRIMER LOCALIZED DE CADA ESPECIE REQUERIDA. UNA VEZ HECHO ESTO, HAY QUE PLANIFICAR AL ENTRENADOR MAS CERCANO AL POKEMON, LO QUE IMPLICA PASARLO A READY

Solo se podrá pasar a un entrenador a estado READY si previamente "no estaba haciendo nada", es decir, en estado NEW o BLOCKED

Se debe aplicar el Algoritmo de planificación:

  1. Como no hay nadie en EXEC, el Entrenador 2 pasara a EXEC (es el más cercano a Squirtle)
  2. Se ejecutará un ciclo de CPU por cada posición que el Entrenador deba moverse para llegar al Pokémon (en este caso es solo 1 posición arriba)
  3. Al llegar al Pokémon, se realizará un CONNECT() al proceso Broker y se enviará el mensaje: 
    CATCH Squirtle 4 4
  4. Se recibirá el ID del mensaje que representa al mensaje enviado por parte del proceso Broker (ID mensaje en este caso sería 1)
  5. El Entrenador 2 pasará a estado BLOCKED a la espera de recibir la respuesta del mensaje (mensaje CAUGHT) 
    CAUGHT con ID correlativo 5 // No existe un mensaje en el proceso Team con ese ID, por lo tanto DESCARTO EL MENSAJE
CAUGHT con ID correlativo 1 // Si corresponde al mensaje enviado previamente, ACEPTO EL MENSAJE
    • Se marca que el Entrenador 2 tiene a Squirtle, es decir, lo sacas del mapa.
    • Se verifica si tiene todos los Pokémon que requiere el entrenador:
      • Si es asi, paso al mismo a estado EXIT.
      • Si no es asi, se verifica si tiene la cantidad máxima de Pokémon que puede conseguir. Un entrenador no puede tener más Pokémon que la suma total de lo que necesita:
        • Si es asi, se queda en estado BLOCKED a la espera de un DEADLOCK.
        • Si no es asi, se verifica si hay algún Pokémon para ir a atrapar:
          • Si es asi, lo vuelvo a planificar y pasa a estado READY.
          • Si no es asi, significa que puede aún atrapar Pokémon. En este acaso queda en estado BLOCKED hasta que aparezca otro Pokémon que debar ir a atrapar.

Ejemplo N°2 (CASO NO FELIZ)

Entrenador 1 Entrenador 2
1 Pikachu 1 Pikachu
1 Squirtle
Pos: [1,2] Pos: [5,4] 
LOCALIZED Squirtle 2 3
E1
Sq
 
 
E2

En este caso, el entrenador más cercado al Pokémon requerido es el 1, pero éste no lo necesita; sin embargo, a nivel global, el proceso Team si lo requiere por lo tanto planifica al Entrenador 1 para capturar al Pokémon.

EL OBJETIVO DEL TEAM ES MAYOR AL OBJETIVO DE LOS ENTRENADORES

Se debe aplicar el mismo Algoritmo de planificación (explicado anteriormente). En este caso, ID mensaje es 3. En este acaso, el mensaje CAUGHT queda de la siguiente forma:

CAUGHT con ID correlativo 3

El Entrenador 1 solo puede capturar 1 solo Pokémon (más alla que este no sea el que requiere). El Entrenador 1 captura a Pikachu. Acá ocurre el concepto de Deadlock (el entrenador se quedará en estado BLOCKED hasta que se pueda resolver el Deadlock). La resolución de un Deadlock se hará a través de los Intercambios.

Se debe desarrollar un Algoritmo de Detección de Deadlocks

¿Cómo detecto un Deadlock?

  1. Los entrenadores deben estar en estado BLOCKED.
  2. Deben poseer algún Pokémon que no necesitan o en exceso (¿?)
  3. Debe formarse una Espera Circular entre los distintos entrenadores (puede hacerse entre dos o más entrenadores).

¿Cómo resolver un Deadlock?

  1. Uno de los entrenadores debe ser planificado a la posición del otro.
  2. Se intecambian los Pokémon usando 5 ciclos de CPU. Cada intercambio solo involucra dos Pokémon.
  3. Se realizan las mismas operaciones que al recibir un mensaje CAUGHT.

Ejemplo N°3 (CASO NO FELIZ)

Entrenador 1 Entrenador 2
1 Pikachu 1 Pikachu
1 Squirtle
Pos: [1,2] Pos: [5,4] 
LOCALIZED Squirtle 2 3 3 5 (¿?)
E1
Sq
Sq
 
E2

Aparecieron dos Pokémon de la misma especie en dos posiciones distintas pero a nivel global solo necesito 1.

COMO MI OBJETIVO GLOBAL SOLO NECESITA 1 SQUIRTLE SOLO SE PLANIFICARÁ AL MÁS CERCANO A UN ENTRENADOR

En este caso, se planificará al Entrenador 1. Por lo tanto, ocurrirá un posible DEADLOCK a futuro.

EL OTRO DEBE MANTENERSE EN MEMORIA EN CASO QUE FALLE LA CAPTURA DEL PRIMERO (si el Entrenador 1 llegó a la posición pero el proceso Game Card niega el acceso a ese Pokémon, ahí habría que planificar al Entrenador 1 para ir a la segunda posición, es decir, 3 5 ¿?)

LOCALIZED Squirtle 2 3 3 5 (¿?)

En este caso, como a nivel global, necesito los 2 Pikachu, planifico a los dos entrenadores "disponibles" más cercanos para capturarlos.

Informacion para el domingo (Ishue 9 )

Poner aca toda la info que se pide en el Ishue 9, despues se va a acomodar bien en la wiki

Tareas relacionadas:

Fuentes:

Foro de github

Implementaciones Similares

Documentación general

Clone this wiki locally