next_inactive up previous



Examen de Programación Concurrente Junio 2003






Dpto. LSIIS. Unidad de Programación.

Supermercado: diseño [3 puntos]

Un supermercado tenía cajas registradoras en que las cajeras introducían a mano el precio de los productos. La dirección decidió adquirir unas nuevas cajas capaces de leer los códigos marcados en los productos, y de ahí, accediendo a una base de datos centralizada, extraer su nombre y precio. La interfaz de acceso es:


procedure Leer_Producto (Cod : in     Tipo_Codigo;
                         Nom :    out Tipo_Nombre;
                         Prec:    out Tipo_Precio);
-- Acceso a la base de datos para consultar el nombre
-- y el precio de un producto.

procedure Actualizar_Producto (Cod  : in Tipo_Codigo;
                               Nom  : in Tipo_Nombre;
                               Prec : in Tipo_Precio);
-- Acceso a la base de datos para actualizar el producto indicado por
-- el código Cod con el nombre Nom y el precio Prec.


Se supone que la base de datos está implícita, y por ello no aparece en ninguna de las llamadas anteriores. La base de datos no tiene capacidad para acceso concurrente (es decir, no tiene ningún tipo de bloqueo ni política de acceso exclusivo). Sin embargo, las operaciones de lectura son reentrantes, es decir, puede iniciarse una operación Leer_Producto antes de que una anterior haya finalizado. Los datos de un producto (nombre y precio) se pueden actualizar en cualquier momento a través de Actualizar_Producto desde un puesto central, pero esta actualización no debe llevarse a cabo en el mismo instante en que se realiza una lectura de ese mismo producto. Adicionalmente se requiere que los tickets entregados a los clientes sean internamente no contradictorios: no puede aparecer un mismo producto dos veces con nombre y/o precio diferente. Cada caja dispone de las siguientes operaciones:


procedure Nuevo_Ticket (I : in Natural);
-- Cuando el proceso Caja(i) ejecuta Nuevo_Ticket(i), éste se queda
-- bloqueado hasta la llegada de un nuevo cliente

procedure Siguiente_Producto (I  : in     Natural;
                              Fin:    out Bool;
                              Cod:    out Tipo_Codigo);
-- Siguiente_Producto(I, Fin, Cod) es ejecutado por Caja(I)
-- y provoca la lectura del codigo del siguiente producto.
-- Cuando no hay más productos el valor de Cod no es significativo
-- y Fin adquiere el valor True.


El grafo de procesos y recursos para el sistema a desarrollar es el siguiente:

\includegraphics[width=0.75\textwidth]{figures/bdconc}
Obsérvese que hay un solo proceso Operador que actualiza la base de datos. Se asume que hay un número máximo de cajas Max_Cajas y un número máximo de productos Max_Productos, ambos constantes. Se pide:
(a)
Implementar el código de las tareas Caja(i) y Operador, utilizando las operaciones a ser definidas en el recurso compartido. Puede asumirse la disponibilidad de operaciones habituales sobre estructuras de datos bien conocidas (listas, pilas, colas, etc.)
[1.5 puntos]
(b)
Definir formalmente (con un C-TADSOL) una interfaz de acceso concurrente a la base de datos que evite los posibles problemas mencionados en el texto anterior. No es necesario tener en cuenta problemas de vivacidad en este apartado. El C-TADSOL debe, no obstante, permitir toda la concurrencia que sea posible en los accesos a la base de datos.
[1.5 puntos]

Supermercado: vivacidad e implementación [7 puntos]

Tras un periodo de diseño se ha llegado al siguiente código para el proceso que gobierna cada caja y para el proceso operador:


Gestor : TipoGestor;

task type Caja (I: Tipo_Rango_Cajas);
task body Caja is
   S_Productos: Secuencia;
   Num_Prods_Distintos, Pos, Total_Ticket: Natural;
   Producto: Tipo_Producto;
   -- Tipo_Producto = (Codigo: Tipo_Codigo x Cantidad: Natural)
   Natural)
   Fin: Boolean;
   Nombre: Tipo_Nombre;
   Precio: Tipo_Precio;
   Cod_Producto: Tipo_Codigo;
begin
   loop
      Nuevo_Ticket (I);
      Num_Prods_Distintos := 0;
      Crear_Vacia (S_Productos);
      -- bucle de registro de productos comprados
      loop
         Siguiente_Producto (I, Fin, Cod_Producto);
         exit when Fin; -- No hay más productos
         Producto.Codigo := Cod_Producto;
         Pos := Buscar (S_Productos, Producto);
         if Pos/=0 then
            Enesimo (S_Productos, Pos, Producto);
            Producto.Cantidad := Producto.Cantidad + 1;
            Reemplazar (S_Productos, Pos, Producto);
         else
            Producto.Cantidad := 0;
            Num_Prods_Distintos := Num_Prods_Distintos + 1;
            Insertar (S_Productos, Num_Prods_Distintos, Producto);
         end if;
      end loop;

      -- Se imprime el ticket
      Total_Ticket := 0;
      for K in 1..Num_Prods_Distintos loop
         Enesimo (S_Productos, K, Producto);
         Gestor.Iniciar_Lectura (Producto.Codigo);
         Leer_Producto (Producto.Codigo, Nombre, Precio);
         Gestor.Terminar_Lectura (Producto.Codigo);
         << Imprimir nombre del producto, precio y cantidad >>
         Total_Ticket := Total_Ticket + Precio*Producto.Cantidad;
      end loop;
      << Imprimir Total_Ticket >>
      Destruir (S_Productos);
   end loop;
end Caja;


task type Operador;
task body Operador is
    Codigo: Tipo_Codigo;
    Nombre: Tipo_Nombre;
    Precio: Tipo_Precio;
begin
   loop
      << Leer Codigo, Nombre y Precio por consola >>
      Gestor.Iniciar_Actualizacion (Codigo);
      Actualizar_Producto (Codigo, Nombre, Precio);
      Gestor.Terminar_Actualizacion (Codigo);
   end loop;
end Operador;


Los procesos anteriores utilizan las operaciones del siguiente CTADSOL:
\begin{ctadsol}
\nombrectad{GestorBD}
\\
\operaciones
\operacion{Inicia...
...on(g, cod)}
\post{$g\sal = g\ent \but \neg g\sal.actualizando$}
\end{ctadsol}
Se pide:

(c)
Estudiar posibles problemas de vivacidad del diseño anterior, excluyendo los achacables a la política de selección de entries o de tareas de Ada. Explicar cómo resolverlos.
[2 puntos]
(d)
Dar una implementación del CTADSOL mediante objetos protegidos y usando el lenguaje Ada, incorporando las soluciones a los problemas de vivacidad que se hayan identificado en el punto (c). Asumir, tanto en este punto como en el (e), que el rango de códigos es muy grande, así como la disponibilidad de operaciones habituales sobre estructuras de datos bien conocidas (listas, pilas, colas, etc.)
[2.5 puntos]
(e)
Dar una implementación del CTADSOL mediante objetos activos y paso de mensajes usando el lenguaje Ada, incorporando las soluciones a los problemas de vivacidad que se hayan identificado en el punto (c).
[2.5 puntos]

Solución propuesta

Apartado c) Vivacidad

El acceso a los datos de un único producto lo podríamos ver como un problema de lectores/escritores en el que sólo hay un único escritor (tarea operador). Por otro lado, los problemas de vivacidad que podrían surgir si varias tareas tratan de ejecutar operaciones correspondientes a distintos productos serían achacables a la política de selección de entries de Ada. En consecuencia, nos centraremos en el análisis de la vivacidad en los problemas derivados del acceso a los datos de un único producto. Habida cuenta del paralelismo existente entre el problema que tenemos entre manos y el problema de lectores/escritores, al realizar este análisis, nos apoyaremos en los resultados, explicados en clase, del análisis de vivacidad del problema de lectores/escritores. Al analizar el grafo de estados del problema de lectores/escritores con sincronización de seguridad, se llegó a la conclusión de que se podían presentar tres situaciones de inanición:
1.
Si siempre que sale el último lector, entra otro lector.
2.
Si siempre hay algún lector en la BD, los escritores no podrán entrar nunca.
3.
Si siempre que sale un escritor, entra otro escritor.
De entre estos tres problemas, el único que no es achacable a la política de selección de entries de Ada es el segundo, por lo tanto, y volviendo al problema del supermercado, tendremos que evitar que las cajas acaparen el acceso a los datos de un producto, e impidan que el operador actualice los datos de dicho producto indefinidamente. Con el fin de evitar la inanición del operador, se podría utilizar una política basada en turnos, análoga a la que se utiliza en el problema de lectores/escritores. Si nos ceñimos a la política de turnos propuesta para el problemas de lectores/escritores, necesitaríamos una variable turno para regular el acceso a los datos de cada producto. Sin embargo, y dado que no nos tenemos que preocupar de los problemas de vivacidad debidos al indeterminismo de Ada, una única variable turno bastará para evitar la situación de inanición planteada en el punto 2. La política de turnos que emplearemos consistirá en lo siguiente: A continuación, se muestran cómo van a quedar las POSTs y las CPREs ampliadas que cambian al incorporar la política de turnos.


Operación ejecutada POST ampliada
TerminarLectura $(g^{sal}.nolecturas(cod) = g^{ent}.nolecturas(cod) + 1) \wedge
\neg g^{sal}.turnolector$
TerminarActualizacion $g^{sal}.actualizando \wedge g^{sal}.turnolector$



Operación ejecutada CPRE ampliada
IniciarLectura(cod) $\neg (g.prodactualz \wedge g.actualizando) \wedge
(g.turnolector\; \vee $ « el operador no espera para actualizar el producto cod »$)$
IniciarActualizacion(cod) $g.nolecturas(cod)=0 \wedge (\neg g.turnolector\; \vee $ « no hay cajas esperando para leer el producto cod »$)$


Apartado d) Objeto Protegido

La principal dificultad de esta implementación estriba en las operaciones IniciarLectura y IniciarActualizacion, ya que las CPREs de ambas dependen del parámetro de entrada cod. Para implementar la operación IniciarLectura utilizaremos una familia de entries indexada con el tipo Tipo_PID_Lectura; este tipo definirá el rango de identificadores para las llamadas de IniciarLectura aplazadas. Para esta familia no sería una buena idea utilizar el tipo Tipo_Codigo por cuanto el rango de códigos es muy grande. Por otro lado, para implementar la operación IniciarActualizacion emplearemos una única entry privada, puesto que sólo se puede aplazar una llamada a IniciarActualizacion a causa de que sólo existe una única tarea Operador.

   Max_Cod_Prod : constant Natural := 100;

   Max_Cajas : constant Natural := 20;
   -- coincide con el num. de tareas lectoras
   Max_Lecturas : constant Natural := 20;


   subtype Tipo_Rango_Cajas is Natural range 1..Max_Cajas;
   subtype Tipo_Codigo is Natural range 0..Max_Cod_Prod;
   subtype Tipo_Pid_Lectura is Natural range 1..Max_Lecturas;

   type Tipo_Producto is
      record
         Codigo   : Tipo_Codigo;
         Cantidad : Natural;
      end record;


   type Tipo_Acceso_Prods is array (Tipo_Codigo) of Natural;

   type Tipo_Lecturas_Aplzs is array (Tipo_Pid_Lectura) of Tipo_Codigo;

   ---------------------------------------------------------------------------

   protected type Tipo_Gestor is

      entry Iniciar_Lectura (
            Codigo : in     Tipo_Codigo );

      entry Iniciar_Actualizacion (
            Codigo : in     Tipo_Codigo );

      entry Terminar_Lectura (
            Codigo : in     Tipo_Codigo );

      entry Terminar_Actualizacion (
            Codigo : in     Tipo_Codigo );

   private

      -- Estado interno del recurso

      No_Lecturas: Tipo_Acceso_Prods := (others => 0);
      Lecturas_Aplzs: Tipo_Lecturas_Aplzs := (others => 0);
      -- sup. q el cero no se utiliza como codigo
      Codigo_Aplz: Tipo_Codigo := 0;
      Actualizando: Boolean := False;
      Prod_Actualz: Tipo_Codigo;
      Turno_Lector: Boolean := False;

      -- entries para operaciones aplazadas

      entry Iniciar_Lectura_Aplz (
            Tipo_Pid_Lectura ) (
            Codigo : in     Tipo_Codigo );

      entry Iniciar_Actualizacion_Aplz (
            Codigo : in     Tipo_Codigo );

   end Tipo_Gestor;

   ---------------------------------------------------------------------------

   protected body Tipo_Gestor is

      function Siguiente_Libre return Tipo_Pid_Lectura is
         I : Natural := 1;
      begin
         while Lecturas_Aplzs(I) /= 0 loop
            I := I + 1;
         end loop;
         return I;
      end Siguiente_Libre;
Al ejecutar un IniciarLectura, se genera dinámicamente un identificador Pid para la llamada que se va a aplazar, y se reencola esta llamada en la entry Pid de la familia IniciarLecturaAplz. Antes de reencolar, se guarda en el vector LecturasAplzs el parámetro de entrada Codigo para poder acceder a él desde la guarda de la familia de entries, que como veremos después, codificará la CPRE ampliada del apartado c.

      entry Iniciar_Lectura (
            Codigo : in     Tipo_Codigo ) when True is
         Pid : Tipo_Pid_Lectura;
      begin
         Pid := Siguiente_Libre;
         Lecturas_Aplzs(Pid):= Codigo;

         requeue Iniciar_Lectura_Aplz(Pid);
      end Iniciar_Lectura;
En el cuerpo de la entry IniciarActualizacion se guarda el parámetro de entrada en la variable CodigoAplz para poderlo consultar en la guarda de la entry privada IniciarActualizacionAplz.

      entry Iniciar_Actualizacion (
            Codigo : in     Tipo_Codigo ) when True is

      begin
         Codigo_Aplz := Codigo;
         requeue Iniciar_Actualizacion_Aplz;
      end Iniciar_Actualizacion;
Las operaciones de terminación implementan las POSTs ampliadas del apartado c.

      entry Terminar_Lectura (
            Codigo : in     Tipo_Codigo ) when True is
      begin
         No_Lecturas(Codigo) := No_Lecturas(Codigo) - 1;
         Turno_Lector := False;
      end Terminar_Lectura;

      entry Terminar_Actualizacion (
            Codigo : in     Tipo_Codigo ) when True is
      begin
         Actualizando := False;
         Turno_Lector := True;
      end Terminar_Actualizacion;
La guarda de IniciarLecturaAplz implementa la CPRE ampliada del apartado c.

      -- Entradas con operaciones aplazadas

      entry Iniciar_Lectura_Aplz (
         for Pid_Lectura in Tipo_Pid_Lectura) (
            Codigo : in     Tipo_Codigo ) when
            not (Actualizando and
            Lecturas_Aplzs (Pid_Lectura ) = Prod_Actualz) and
               (Turno_Lector or
               not (Iniciar_Actualizacion_Aplz'Count > 0 and
                  Lecturas_Aplzs (Pid_Lectura ) = Codigo_Aplz)) is
      begin
         No_Lecturas(Codigo) := No_Lecturas(Codigo) + 1;
         Lecturas_Aplzs(Pid_Lectura):= 0;
         -- esta entry de la familia queda disponible
      end Iniciar_Lectura_Aplz;
La guarda de IniciarActualizacionAplz implementa la CPRE ampliada del apartado c; cabe destacar en ella la llamada a la función ExisteLecturaAplz cuya finalidad es comprobar si existe alguna lectura aplazada del producto que se pretende actualizar.

      function Existe_Lectura_Aplz (
            C : Tipo_Codigo )
        return Boolean is
         I : Natural := 1;
      begin
         while (I<=Tipo_Pid_Lectura'Last) and then
               not (Iniciar_Lectura_Aplz(I)'Count>0 and
               Lecturas_Aplzs(I) = C) loop
            I := I + 1;
         end loop;
         return (I<=Tipo_Pid_Lectura'Last);
      end Existe_Lectura_Aplz;


      entry Iniciar_Actualizacion_Aplz (
            Codigo : in     Tipo_Codigo ) when
         No_Lecturas ( Codigo_Aplz ) = 0 and
           (not Turno_Lector or
            not (Existe_Lectura_Aplz (Codigo_Aplz) )) is
      begin
         Actualizando := True;
         Prod_Actualz := Codigo;
      end Iniciar_Actualizacion_Aplz;

   end Tipo_Gestor;
Otra posible implementación para la operación IniciarLectura podría comprobar la CPRE en el cuerpo de la entry IniciarLectura. De esta manera, si se cumple la CPRE, se ejecutará la operación en el mismo cuerpo de la entry IniciarLectura, y sólo en caso contrario, se reencolará la llamada en la familia de entries. Esto traerá consigo que todas las llamadas bloqueadas en la familia de entries sean lecturas del mismo producto; aprovechándonos de esto último, podríamos mejorar la eficiencia de la función ExisteLecturaAplz, y por tanto de la evaluación de la guarda de la entry IniciarActualizacionAplz.

Apartado e) Paso de mensajes

Para implementar el desbloqueo explícito de las operaciones IniciarLectura y IniciarActualizacion vamos a utilizar las primitivas Send y Receive que proporciona el paquete Channel. Estas primitivas sólo las utilizaremos para sincronizar, y no para transferir datos, ya que las operaciones en cuestión no poseen parámetros de salida o de entrada/salida.
   type T_Resp_Servidor is new Character; -- no se va a utilizar

   package T_Canal_Producto is new Channel(Tmensaje => T_Resp_Servidor);
   use T_Canal_Producto;
Asimismo, las lecturas aplazadas las guardaremos en una cola de llamadas. En cada elemento de esta cola guardaremos el código del producto que se desea leer, así como el canal que utilizarán la tarea Caja y la tarea Gestor para sincronizarse.
   type Tipo_Lectura_Aplz is
      record
         Codigo : Tipo_Codigo;
         CResp  : Channel_P;
      end record;

   package T_Cola_Producto is new Colas(Tipo_Elemento => Tipo_Lectura_Aplz);
   use T_Cola_Producto;
En la implementación con paso de mensajes el recurso GestorBD lo implementaremos mediante una tarea TipoGestor, que poseerá una entry por cada operación del recurso. Las entries IniciarLectura e IniciarActualizacion tienen un parámetro de entrada adicional de tipo Channel_P por medio del cual las tareas Caja y la tarea Operador le pasarán a la tarea Gestor el canal que se utilizará para implementar el desbloqueo explícito.
   task type Tipo_Gestor is
      entry Iniciar_Lectura (
            Codigo : in     Tipo_Codigo;
            CResp  : in     Channel_P   );

      entry Iniciar_Actualizacion (
            Codigo : in     Tipo_Codigo;
            CResp  : in     Channel_P   );

      entry Terminar_Lectura (
            Codigo : in     Tipo_Codigo );

      entry Terminar_Actualizacion (
            Codigo : in     Tipo_Codigo );
   end Tipo_Gestor;


   task body Tipo_Gestor is

      -- Estado interno del recurso

      No_Lecturas : Tipo_Acceso_Prods := (others => 0);
      -- sup. q el cero no se utiliza como codigo
      Actualizando   : Boolean     := False;
      Prod_Actualz   : Tipo_Codigo;
      Turno_Lector : Boolean     := False;

      -- variables para la actualizacion aplazada
      Cod_Act_Aplz   : Tipo_Codigo := 0;
      CResp_Act_Aplz : Channel_P;

      -- cola de lecturas aplazadas
      Lecturas_Aplzs : Cola := Crear_Vacia;

      -- variables auxs
      Cod_Aplz           : Tipo_Codigo;
      Cresp_Aplz         : Channel_P;
      Llamada            : Tipo_Lectura_Aplz;
      Nada               : T_Resp_Servidor;


      function Existe_Lectura_Aplz (CLecturas: Cola; c: Tipo_Codigo) return Boolean is
         Llamada : Tipo_Lectura_Aplz;
      begin
         if not Es_Vacia(CLecturas) then
            Primero (CLecturas, Llamada);
            return (Llamada.Codigo = c);
         else
            return False;
         end if;
      end Existe_Lectura_Aplz;
En el cuerpo de la rama IniciarLectura se comprueba la CPRE ampliada, y si se cumple, se desbloquea a la tarea Caja mediante un Send, y se realiza la operación IniciarLectura. Si no se cumple la CPRE, se aplaza la realización de la operación guardando en la cola Lecturas_Aplzs el registro de activación de la llamada aplazada. Cabe destacar que todas las llamadas pendientes que se guardarán en la cola se referirán al mismo producto.
   begin
      loop
         select
            when True =>
            accept Iniciar_Lectura (
                  Codigo : in     Tipo_Codigo;
                  CResp  : in     Channel_P    ) do
               if not (Actualizando and Codigo = Prod_Actualz) and
                    (Turno_Lector or not(Codigo = Cod_Act_Aplz)) then
                  CResp.Send (Nada);
                  No_Lecturas(Cod_Aplz) :=
                   No_Lecturas(Cod_Aplz) + 1;
               else
                  Insertar(Lecturas_Aplzs, (Codigo, CResp));
               end if;
            end Iniciar_Lectura;
En el cuerpo de la rama IniciarActualizacion se aplaza siempre la operación.
         or
            when True =>
            accept Iniciar_Actualizacion (
                  Codigo : in     Tipo_Codigo;
                  Cresp  : in     Channel_P    ) do
               Cod_Act_Aplz := Codigo;
               Cresp_Act_Aplz := Cresp;
            end Iniciar_Actualizacion;
Los cuerpos de las ramas TerminarLectura y TerminarActualizacion implementan las POSTs ampliadas.
         or
            when True =>
            accept Terminar_Lectura (
                  Codigo : in     Tipo_Codigo ) do
               No_Lecturas(Codigo) :=
                  No_Lecturas(Codigo) - 1;
               Turno_Lector := False;
            end Terminar_Lectura;
         or
            when True =>
            accept Terminar_Actualizacion (
                  Codigo : in     Tipo_Codigo ) do
               Actualizando := False;
               Turno_Lector := True;
            end Terminar_Actualizacion;
         end select;
En el código de desbloqueo, que se ejecuta después de la select, se comprueba en primer lugar si se puede ejecutar la actualización aplazada. Para ello se evalúa la CPRE ampliada instanciada con la información guarda en el registro de activación de la llamada aplazada. Si no se puede desbloquear la actualización pendiente, se comprueba si se pueden ejecutar las lecturas pendientes guardas en la cola Lecturas_Aplzs. Estas llamadas pendientes se encolaron, porque en el momento en el que se realizó la llamada, no se cumplió la CPRE ampliada de la operación IniciarLectura; es decir, porque o se estaba actualizando el producto que se deseaba leer, o lo estaban leyendo otras cajas, y el operador estaba esperando y tenía el turno. En ambos casos, no se debe dar paso a las lecturas pendientes hasta que no se haya ejecutado la actualización. Esto se podrá detectar en el código de desbloqueo mirando simplemente el valor de la variable Actualizando. En el supuesto de que haya finalizado la actualización, se podrán desbloquear todas las lecturas pendientes, ya que todas ellas afectaban al mismo producto. Por eso, dentro del bucle while no es necesario comprobar la CPRE de IniciarLectura.
         -- Codigo de desbloqueo

         -- se comprueba si se puede ejecutar
         -- la actualizacion aplazada

         if ((Cod_Act_Aplz /= 0) and then
               (No_Lecturas(Cod_Act_Aplz) = 0))
            and (not Turno_Lector or
                 not Existe_Lectura_Aplz (Lecturas_Aplzs, Cod_Act_Aplz)) then
            Cresp_Act_Aplz.Send (Nada);
            Actualizando := True;
            Prod_Actualz := Cod_Act_Aplz;
            Cod_Act_Aplz := 0; -- no hay actualizacion pendiente
         else
         -- se comprueba si se pueden ejecutar
         -- las lecturas aplazadas

            if not Actualizando then
               while not (Es_Vacia(Lecturas_Aplzs)) loop
                  Primero (Lecturas_Aplzs, Llamada);
                  Cod_Aplz := Llamada.Codigo;
                  Cresp_Aplz := Llamada.CResp;
                  Borrar (Lecturas_Aplzs);

                  Cresp_Aplz.Send (Nada);
                  No_Lecturas(Cod_Aplz) :=
                      No_Lecturas(Cod_Aplz) + 1;
               end loop;
            end if;
         end if;

      end loop;
   end Tipo_Gestor;




next_inactive up previous
Manuel Carro
2003-07-24