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:

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:
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:

- Si el turno es para las lecturas y hay cajas esperando para leer los datos de un producto, cuando acabe el operador su actualización, podrán leer las cajas. Cabe destacar que dado que sólo hay un operador, todos las cajas que estén esperando para leer los datos de un producto estarán esperando para leer los datos de un mismo producto.
- Si el turno es para la actualización y está esperando el operador para actualizar los datos de un producto P, no empezarán más cajas a leer los datos de P hasta que el operador no haya actualizado los datos de P.
- El cambio de turnos se realizará de la siguiente manera: Si termina una actualización, se cede el turno a las cajas. Y si termina una lectura, se cede el turno a una actualización. Asimismo, el turno no debe influir si no hay tareas de un tipo esperando para leer o actualizar.

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 |
TerminarActualizacion |

Operación ejecutada | CPRE ampliada
IniciarLectura(cod) | « el operador no espera para actualizar el producto cod »
IniciarActualizacion(cod) | « 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;

- Supermercado: diseño [3 puntos]
- Supermercado: vivacidad e implementación [7 puntos]
- Solución propuesta
  - Apartado c) Vivacidad
  - Apartado d) Objeto Protegido
  - Apartado e) Paso de mensajes