next_inactive up previous
Up: solucion Previous: Sistema de retransmisión de

Subsecciones


Sistema de retransmisión de vídeo -- Implementación

Una posible solución corresponde al diagrama de procesos y recursos mostrado en la figura 2. El código de los procesos muestra en la figura 3 y la especificación del recurso se muestra en la figura 4.


Figura 3: Seudocódigo de los procesos


Emisor:

loop
    Codificar_Imagen(I);
    G.Transmitir(I);
end loop;



Reloj:

loop
    Esperar(R);
    G.Invalidar;
end loop;


Receptor:

G.Registrar;
Fot_Act := 1;
loop
    G.Esperar_Imagen(Fot_Act, I);
    Mostrar_Imagen(I);
    Fot_Act := Fot_Act + 1;
end loop;

Figura 4: Especificación formal del recurso pedido


\fbox{
\begin{minipage}{\textwidth}
\begin{ctadsol}
\nombrectad{TransmisiónVíde...
...t.buffer))$ \wedge$ \\
tv\sal.accedieron = 0
}
\end{ctadsol} \end{minipage}}




Se pide:

d)
Implementación en Ada 95 del sistema (procesos Emisor, Receptor, Reloj y recurso TransmisiónVídeo) usando procesos distribuidos y rendez-vous y/o paso de mensajes. [4 puntos]

e)
Implementación del recurso mediante objetos protegidos (sólo el código del tipo protegido).[3 puntos]




Observación: No será necesario tener en cuenta posibles problemas de vivacidad provocados exclusivamente por la implementación no determinista en Ada 95 de las llamadas a entries o ramas de una select. Puede suponerse que no hay un límite superior al número de receptores que pueden conectarse al sistema de transmisión.




Comentarios a la corrección:

Las calificaciones obtenidas en este apartado pueden clasificarse, grosso modo en las siguientes categorías:

Solución propuesta:

Las implementaciones de paso de mensajes y de objetos protegidos pueden utilizar una instanciación de un paquete buffer para almacenar las imágenes remitidas por el proceso Emisor. Este paquete proporciona las operaciones de inserción, borrado, y comprobación de tamaño:

   Buffer_Size : constant Natural := ...;
   package T_Buffer_Imagen is
      new Buffer(Tipo_Elemento => T_Imagen,
                 Tamano        => Buffer_Size);
   use T_Buffer_Imagen;

d)

El código de los procesos Reloj y Emisor es similar al mostrado en la figura 3. El código del proceso Receptor debe cambiarse para implementar la dependencia de la precondición con respecto de los parámetros de entrada, utilizando un canal que posibilite la suspensión y el rearranque de la tarea:

   type T_Resp_Servidor is
      record
         Imagen:     T_Imagen;
         Nueva_Foto: Natural;
      end record;

   package T_Canal_Imagen is
      new Channel(TMensaje => T_Resp_Servidor);
   use T_Canal_Imagen;

   task type Tipo_Receptor;
   task body Tipo_Receptor  is
      Foto_Actual  : Natural;
      Respuesta    : T_Resp_Servidor;
      Canal_Imagen : Channel_P := new T_Canal_Imagen.Channel;
   begin
      G.Registrar;
      Foto_Actual := 1;
      loop
         G.Esperar_Imagen(Canal_Imagen, Foto_Actual);
         Canal_Imagen.Receive(Respuesta);
         Mostrar_Imagin(Respuesta.Imagen);
         Foto_Actual := Respuesta.Nueva_foto + 1;
      end loop;
   end Tipo_Receptor;

La única dificultad en el servidor es precisamente la implementación de Esperar_Imagen. La técnica estándar es guardar en una estructura interna los datos necesarios para decidir cuándo se puede atender la petición, junto con un canal para realizar el desbloqueo y el envío. Una posibilidad general es utilizar una cola. Así, los argumentos de entrada de Esperar_Imagen se guardarían en servidor a la espera de que se puede atender la petición:

   type T_LLamada_Suspendida is
      record
         Canal_Respuesta: Channel_P;
         Foto_Pedida: Natural;
      end record;

   package T_Cola_Suspendidas is
      new Colas(Tipo_Elemento => T_LLamada_Suspendida);
   use T_Cola_Suspendidas;

Por último, el servidor evalúa en las guardas las llamadas cuya aceptación depende sólo del estado interno, y guarda los datos correspondientes a Esperar_Imagen.

   task type Transmision_Video is
      entry Registrar;
      entry Esperar_Imagen (Canal_Resp  : in Channel_P;
                            Foto_Pedida : in Natural);
      entry Transmitir (Imagen : in T_Imagen);
      entry Invalidar;
   end Transmision_Video;

   task body Transmision_Video is
      -- Variables de estado básicas; deducidas directamente de la
      -- especificación del recurso.
      Almacen_Imagenes: T_Buffer_Imagen.Buffer;
      Accedieron:  Natural := 0;
      Registrados: Natural := 0;
      Foto_Actual: Natural := 1; -- no se ha leido ningun fotograma todavia

      Cola_Suspendidas: Cola := Crear_Vacia;
      Cola_Aux:         Cola := Crear_Vacia;

      Llamada: T_LLamada_Suspendida;
      Imagen_Actual: T_Imagen;
   begin
      loop
         select
            when True =>
               accept Registrar
               do
                  Registrados := Registrados + 1;
               end Registrar;
         or
            when not Vacio(Almacen_Imagenes) =>
               accept Invalidar do
                  null;
               end Invalidar;
               if Accedieron < Registrados then
                  Borrar(Almacen_Imagenes);
               end if;
               Accedieron := 0;
               Foto_Actual := Foto_Actual + 1;
         or
            when not Lleno(Almacen_Imagenes) =>
               accept Transmitir (Imagen : in T_Imagen)
               do
                  Poner(Almacen_Imagenes, Imagen);
               end Transmitir;
         or
            when True =>
               accept Esperar_Imagen (Canal_Resp : in Channel_P;
                                      Foto_Pedida: in Natural)
               do
                  Insertar(Cola_Suspendidas, (Canal_Resp, Foto_Pedida));
               end Esperar_Imagen;
         end select;

         while not Es_Vacia(Cola_Suspendidas) and
           not Vacio(Almacen_Imagenes) loop
            Primero(Cola_Suspendidas, Llamada);
            Borrar(Cola_Suspendidas);
            if Llamada.Foto_Pedida <= Foto_Actual then
               Accedieron := Accedieron + 1;
               Primero(Almacen_Imagenes, Imagen_Actual);
               Llamada.Canal_Respuesta.Send((Imagen_Actual, Foto_Actual));
               if Accedieron = Registrados then
                  Borrar(Almacen_Imagenes);
               end if;
            else
               Insertar(Cola_Aux, Llamada);
            end if;
         end loop;

         while not Es_Vacia(Cola_Aux) loop
            Primero(Cola_Aux, Llamada);
            Borrar(Cola_Aux);
            Insertar(Cola_Suspendidas, Llamada);
         end loop;
      end loop;
   end Transmision_Video;

Cola_Suspendidas se recorre para determinar qué llamadas suspendidas pueden rearrancarse. Aquellas que no pueden servirse en ese momento se guardan en Cola_Aux, que se recorre para dejar, de nuevo, los argumentos de las llamadas suspendidas en la cola inicial. Este segundo recorrido puede evitarse con varios métodos; por ejemplo, manteniendo en un contador el número de elementos almacenados y reintroduciendolos en la cola inicial, o incluso alternando entre dos colas que se van llenando y vaciando en sucesión. Dado que se supone un límite superior al número de procesos receptores, una estructura estática (un vector) es también aceptable.

e)

La implementación propuesta de objetos protegidos utiliza el límite al número de receptores para formar una familia de entries y un vector que asigna dinámicamente un identificador diferente a cada llamada.

   type Llamada_Almacenada is
      record
         Usada:     Boolean := False;
         Esperando: Natural;
      end record;
   type T_Array_Espera is array(T_Rango_Receptores) of Llamada_Almacenada;

   protected type Transmision_Video is

      entry Registrar;
      entry Esperar_Imagen (Foto_Req : in out Natural;
                            Imagen   :    out T_Imagen);
      entry Transmitir (Imagen : in T_Imagen);
      entry Invalidar;

   private
      -- Variables de estado básicas; deducidas directamente de la
      -- especificación del recurso.
      Almacen_Imagenes: T_Buffer_Imagen.Buffer;
      Accedieron:  Natural :=0;
      Registrados: Natural :=0;
      Foto_Actual: Natural :=1; -- no se ha leido ningun fotograma todavia

      Bloqueadas: T_Array_Espera;

      -- Procedimiento interno de Espera_Imagen en casos bloqueados.
      entry Esperar_Imagen_Blq
        (T_Rango_Receptores)
        (Foto_Req : in out Natural;
         Imagen   :    out T_Imagen);
   end Transmision_Video;

   protected body Transmision_Video is

      entry Registrar when True is
      begin
         Registrados := Registrados + 1;
      end Registrar;

      entry Esperar_Imagen (Foto_Req : in out Natural;
                            Imagen   :    out T_Imagen)
      when True is
         Pos : T_Rango_Receptores := 1;
      begin
         while Bloqueadas(Pos).Usada loop
            Pos := Pos + 1;
         end loop;
         Bloqueadas(Pos).Usada     := True;
         Bloqueadas(Pos).Esperando := Foto_Req;
         requeue Esperar_Imagen_Blq(Pos);
      end Esperar_Imagen;

      entry Esperar_Imagen_Blq
        (for Pos in T_Rango_Receptores)
        (Foto_Req : in out Natural;
         Imagen   :    out T_Imagen)
      when Bloqueadas(Pos).Esperando <= Foto_Actual and
           not Vacio(Almacen_Imagenes) is
      begin
         Bloqueadas(Pos).Usada := False;
         Primero(Almacen_Imagenes, Imagen);
         Foto_Req := Foto_Actual;
         Accedieron := Accedieron + 1;
         if Accedieron = Registrados then
            Borrar(Almacen_Imagenes);
         end if;
      end Esperar_Imagen_Blq;

      entry Invalidar
      when not Vacio(Almacen_Imagenes) is
      begin
         if Accedieron < Registrados then
            Borrar(Almacen_Imagenes);
         end if;
         Accedieron := 0;
         Foto_Actual := Foto_Actual + 1;
      end Invalidar;

      entry Transmitir (Imagen : in T_Imagen)
      when not Lleno(Almacen_Imagenes) is
      begin
         Poner(Almacen_Imagenes, Imagen);
      end Transmitir;
   end Transmision_Video;




Comentarios a la corrección

Los problemas encontrados con más frecuencia son:
Utilizar un esquema de atención por orden de llegada:
si bien este esquema es fácil de implementar, disminuye gravemente la concurrencia y causa que el receptor más rápido impida que los demás accedan a la imagen preparada en ese momento.

Reutilizar variables sin protegerlas adecuadamente:
una variante del esquema anterior donde las variables internas intermedias no se protegen con un esquema en dos fases, lo que además causa incorrección grave: un mismo receptor puede recibir varias veces la misma imagen por violación de la precondición.

Utilizar estructuras de datos potencialmente infinitas:
fundamentalmente causado por utilizar el número de fotograma como base de un vector o una familia de entries: en el enunciado se especificaba que la transmisión no tenía un límite.

Añadir número receptor ad-hoc:
no es grave, pero es innecesario, y en muchos casos ni siquiera se llega a utilizar correctamente o se explica de dónde procede. En particular, el caso de la implementación de objetos protegidos no se contemplaba ningún cambio en el interfaz.

Código mal estructurado, redundante y/o difícil de justificar y mantener.

Ausencia de control de precondiciones:
en muchos casos no se comprueban las condiciones de concurrencia con construcciones que lleven a suspensión en caso necesario.

Errores sintácticos graves:
no se han tenido en cuenta los errores leves de sintaxis, pero hay algunos que no se pueden siquiera considerar como código Ada, y a los que no es posible asignar un significado claro.

Falta de comprobación de precondición completa:
muchos casos devuelven imágenes sin comprobar si en el momento del envío hay algo almacenado en el buffer.

Finalización sin servir petición:
salir de una operación sin haberla servido y, en muchos casos, sin suspender previamente.

Ausencia de código de procesos, o código de los mismos gravemente erróneo.

Inserción innecesaria de imágenes en cola peticiones:
no es necesario que en paso de mensajes se almacene la imagen (que es un parámetro de salida en una implementación razonable) junto con los parámetros asociados a la llamada.

Ausencia de modo claro de recepción de las imagenes y/o fotogramas:
en algunos procesos Receptor no se aprecia cómo pueden llegar los resultados.

Ausencia o compartición de canal de retorno:
varios procesos receptor no pueden compartir un mismo canal de llegada de datos. Igualmente, para que el servidor sepa por qué canal (privado) estará esperando un proceso, es necesario que éste se lo haga llegar primero.

Desaparición de peticiones examinadas:
algunas implementaciones del servidor no reencolan las peticiones almacenadas que no pueden ser satisfechas, de modo que desaparecen del sistema.

Uso de variables de llamada en la evaluación de una guarda:
esto no es posible en Ada 95.

Bloqueo:
algunas implementaciones tienen una posibilidad clara de llegar a una situación en que haya un bloqueo completo de, al menos, los receptores (y, por consiguiente, del emisor en algún momento).


next_inactive up previous
Subir: solucion Anterior: Sistema de retransmisión de
Manuel Carro
2003-02-18