Examen de Programación Concurrente sep02

Dpto. LSIIS. Unidad de Programación

# Ordenación por burbuja -- Soluciones

## Diseño

### Código de las tareas

    Vector : TVector; -- de TDato
    Gestor : AccesoVector;
    ...
    task type Intercambiador (I : Indice);
    task body Intercambiador is
       Intermedio : TDato;
       Fin, Permutado : Boolean;
    begin
       loop
          if I mod 2 = 0 then
             Gestor.InicioEtapaPar (Fin);
          else
             Gestor.InicioEtapaImpar (Fin);
          end if;
          if not Fin then
             if Vector (I) > Vector (I+1) then
                Intermedio := Vector (I);
                Vector (I) := Vector (I+1);
                Vector (I+1) := Intermedio;
                Permutado := True;
             else
                Permutado := False;
             end if;
             if I mod 2 = 0 then
                Gestor.FinEtapaPar (Permutado);
             else
                Gestor.FinEtapaImpar (Permutado);
             end if;
           end if;
           exit when Fin;
        end loop;
    end Intercambiador;
    task type TProductor;
    task body TProductor is
       VectorLocal : TVector;
    begin
       <obtener VectorLocal>
       for I in Indice loop
          Vector (I) := VectorLocal (I);
       end loop;
       Gestor.IniciarOrdenacion ();
    end TProductor;

    task type TConsumidor;
    task body TConsumidor is
       VectorLocal : TVector;
    begin
       Gestor.EsperarFinOrdenacion ();
       for I in Indice loop
          VectorLocal (I) := Vector (I);
       end loop;
       <procesar VectorLocal>
    end TConsumidor;

    Productor : TProductor;
    Consumidor : TConsumidor;
    type TIntercambiador is access Intercambiador;
    Intercambiadores : array Indice of TIntercambiador;

### Recurso AccesoVector

InicioEtapaImpar y FinEtapaImpar se especifican de manera análoga a InicioEtapaPar y FinEtapaPar.

## Implementación mediante objetos protegidos

    with Ada.Text_Io;
    use Ada.Text_Io;

    procedure Burbuja_obj is

       N                    : constant Natural := 6;
       Num_Intercambiadores : constant Natural := N - 1;
       subtype Tipo_Rango_Intercambiador is Natural range 0..
          Num_Intercambiadores;

       type Tipo_Dato is new Natural;
       type Tipo_Vector is array (0 .. N - 1) of Tipo_Dato;

    -------------------------------------------------------
    -------------------------------------------------------
    -------  DEFINICIÓN DEL OBJETO PROTEGIDO --------------
    -------------------------------------------------------
    -------------------------------------------------------

       protected type Tipo_Acceso_Vector is
          entry Iniciar_Ordenacion;
          entry Esperar_Fin_Ordenacion;
          entry Inicio_Etapa_Par (
                Fin :    out Boolean );
          entry Fin_Etapa_Par (
                Par_Permutado : in     Boolean );
          entry Inicio_Etapa_Impar (
                Fin :    out Boolean );
          entry Fin_Etapa_Impar (
                Par_Permutado : in     Boolean );

       private
          -- Variables que definen el estado del recurso

          -- Inicialización del recurso
          Hay_Datos : Boolean := False;
          Ordenado : Boolean := False;
          Sin_Cambio : Integer := -1;
          Permutado : Boolean := False;

          Pares, Impares : Natural;
          Fin_Pares, Fin_Impares : Natural;
       end Tipo_Acceso_Vector;

       protected body Tipo_Acceso_Vector
             is
          entry Iniciar_Ordenacion when True is -- CPRE de Iniciar_Ordenacion
          begin
             Hay_Datos := True;
             Pares := N/2; -- Se empieza con la fase par
             Fin_Pares := N/2;
             Impares := 0;
          end Iniciar_Ordenacion;

          entry Esperar_Fin_Ordenacion when Ordenado is -- CPRE de Esperar_Fin_Ordenacion
          begin
             null; -- la POST es true, así que no se hace nada
          end Esperar_Fin_Ordenacion;

          entry Inicio_Etapa_Par (
                Fin :    out Boolean ) when (
                Hay_Datos and Pares > 0) or Ordenado is -- CPRE de Inicio_Etapa_Par
          begin
             Fin := Ordenado;
             Pares := Pares-1;
          end Inicio_Etapa_Par;

          entry Fin_Etapa_Par (
                Par_Permutado : in     Boolean ) when Pares = 0 is -- CPRE de Fin_Etapa_Par
          begin
             Fin_Pares := Fin_Pares - 1;
             -- Ha acabado un intercambiador de pares

             Permutado := Permutado or Par_Permutado;

             if Permutado then
             -- si se han intercambiado un par de elems, no acaba la ordenación
                Sin_Cambio := 0;
             else
                if Fin_Pares=0 then -- acabaron todos los pares
                   Sin_Cambio := Sin_Cambio + 1;
                end if;
             end if;

             if Sin_Cambio=1 then
             -- esta cond. se cumplirá si ha finalizado una etapa
             -- que no es la primera, y no se han intercambiado un par de elems

                Ordenado := True;  -- terminó la ordenación
             else -- hay que seguir
                if Fin_Pares = 0 then -- acabaron todos los pares
                   Impares := (N-1)/2; -- cambio de fase
                   Fin_Impares := (N-1)/2;
                   Permutado := False; -- inicializamos permutado
                end if;
             end if;

          end Fin_Etapa_Par;

          entry Inicio_Etapa_Impar (
                Fin :    out Boolean ) when (
                Hay_Datos and Impares > 0) or Ordenado is -- CPRE de Inicio_Etapa_Impar
          begin
             Fin := Ordenado;
             Impares := Impares -1;
          end Inicio_Etapa_Impar;

          entry Fin_Etapa_Impar (
                Par_Permutado : in     Boolean ) when Impares = 0 is -- CPRE de Fin_Etapa_Impar
          begin

             Fin_Impares := Fin_Impares - 1;
             -- Ha acabado un intercambiador de impares

             Permutado := Permutado or Par_Permutado;

             if Permutado then
             -- si se han intercambiado un par de elems, no acaba la ordenación
                Sin_Cambio := 0;
             else
                if Fin_Impares=0 then -- acabaron todos los impares
                   Sin_Cambio := Sin_Cambio + 1;
                end if;
             end if;

             if Sin_Cambio=1 then
             -- esta cond. se cumplirá si ha finalizado una etapa
             -- que no es la primera, y no se han intercambiado un par de elems

                Ordenado := True; -- terminó la ordenación
             else -- hay que seguir
                if Fin_Impares = 0 then -- acabaron todos los impares
                   Pares := N/2; -- cambio de fase
                   Fin_Pares := N/2;
                   Permutado := False; -- inicializamos permutado
                end if;
             end if;
          end Fin_Etapa_Impar;

       end Tipo_Acceso_Vector;

       Gestor : Tipo_Acceso_Vector;
       Vector : Tipo_Vector;

       -- Tareas
       task type Tipo_Intercambiador (I : Tipo_Rango_Intercambiador);
       task body Tipo_Intercambiador is
          Intermedio : Tipo_Dato;
          Fin,
          Permutado  : Boolean;
       begin
          Put("empieza " & Tipo_Rango_Intercambiador'Image(I));
          loop
             if I mod 2 = 0 then
                Gestor.Inicio_Etapa_Par (Fin);
             else
                Gestor.Inicio_Etapa_Impar (Fin);
             end if;

             if not Fin then
                if Vector(I) > Vector(I+1) then
                   Intermedio := Vector(I);
                   Vector(I) := Vector(I+1);
                   Vector(I+1) := Intermedio;
                   Permutado := True;
                   Put_Line("Intercambia " & Tipo_Dato'Image(Vector(I)) &
                      Tipo_Dato'Image(Vector(I+1)));
                else
                   Permutado := False;
                end if;
                if I mod 2 = 0 then
                   --Gestor.Dec_Pares;
                   Gestor.Fin_Etapa_Par (Permutado);
                else
                   --Gestor.Dec_Impares;
                   Gestor.Fin_Etapa_Impar (Permutado);
                end if;
             end if;
             exit when Fin;
          end loop;
          Put("Fin");
       end Tipo_Intercambiador;

       task type Tipo_Productor;
       task body Tipo_Productor is
       begin

          --Vector := (1, 2, 3, 4, 5, 6);
          Vector := (6, 5, 4, 3, 2, 1);
          Gestor.Iniciar_Ordenacion;

       end Tipo_Productor;

       task type Tipo_Consumidor;
       task body Tipo_Consumidor is
       begin

          Gestor.Esperar_Fin_Ordenacion;
          for I in Tipo_Vector'range loop
             Put (Tipo_Dato'Image(Vector(I)) & " ");
          end loop;

       end Tipo_Consumidor;

       type Tipo_Pintercambiador is access Tipo_Intercambiador;
       type Tipo_Pintercambiadores is array (Tipo_Rango_Intercambiador) of Tipo_Pintercambiador;

       Intercambiadores : Tipo_Pintercambiadores;
       Productor        : Tipo_Productor;
       Consumidor       : Tipo_Consumidor;

    begin
       for I in Tipo_Rango_Intercambiador'range loop
          Intercambiadores(I) := new Tipo_Intercambiador(I);
       end loop;
    end Burbuja_obj;

## Implementación mediante paso de mensajes

    with Ada.Text_Io;
    use Ada.Text_Io;

    procedure Burbuja_Msg is

       N                    : constant Natural := 6;
       Num_Intercambiadores : constant Natural := N - 1;
       subtype Tipo_Rango_Intercambiador is Natural range 0..
          Num_Intercambiadores;

       type Tipo_Dato is new Natural;
       type Tipo_Vector is array (0 .. N - 1) of Tipo_Dato;

    -------------------------------------------------------
    -------------------------------------------------------
    -------  DEFINICIÓN DEL RECURSO ACTIVO  ---------------
    -------------------------------------------------------
    -------------------------------------------------------

       task type Tipo_Acceso_Vector is
          entry Iniciar_Ordenacion;
          entry Esperar_Fin_Ordenacion;
          entry Inicio_Etapa_Par (
                Fin :    out Boolean );
          entry Fin_Etapa_Par (
                Par_Permutado : in     Boolean );
          entry Inicio_Etapa_Impar (
                Fin :    out Boolean );
          entry Fin_Etapa_Impar (
                Par_Permutado : in     Boolean );
       end Tipo_Acceso_Vector;

       task body Tipo_Acceso_Vector is
          -- Variables que definen el estado del recurso

          -- Inicialización del recurso
          Hay_Datos  : Boolean := False;
          Ordenado   : Boolean := False;
          Sin_Cambio : Integer := - 1;
          Permutado  : Boolean := False;

          Pares,
          Impares    : Natural;
          Fin_Pares,
          Fin_Impares : Natural;

       begin
          loop
             select
                when True =>
                accept Iniciar_Ordenacion do -- CPRE de Iniciar_Ordenacion
                   Hay_Datos := True;
                   Pares := N/2; -- Se empieza con la fase par
                   Fin_Pares := N/2;
                   Impares := 0;
                end Iniciar_Ordenacion;
             or
                when Ordenado =>
                accept Esperar_Fin_Ordenacion do -- CPRE de Esperar_Fin_Ordenacion

                   null; -- la POST es true, así que no se hace nada
                end Esperar_Fin_Ordenacion;
             or
                when (
                   Hay_Datos and Pares > 0) or Ordenado =>
                accept Inicio_Etapa_Par (
                      Fin :    out Boolean ) do -- CPRE de Inicio_Etapa_Par
                   Fin := Ordenado;
                   Pares := Pares-1;
                end Inicio_Etapa_Par;
             or
                when Pares = 0 =>
                accept Fin_Etapa_Par (
                      Par_Permutado : in     Boolean ) do -- CPRE de Fin_Etapa_Par
                   Fin_Pares := Fin_Pares - 1;
                   -- Ha acabado un intercambiador de pares

                   Permutado := Permutado or Par_Permutado;

                   if Permutado then
                      -- si se han intercambiado un par de elems, no acaba la ordenación
                      Sin_Cambio := 0;
                   else
                      if Fin_Pares=0 then -- acabaron todos los pares
                         Sin_Cambio := Sin_Cambio + 1;
                      end if;
                   end if;

                   if Sin_Cambio=1 then
                      -- esta cond. se cumplirá si ha finalizado una etapa
                      -- que no es la primera, y no se han intercambiado un par de elems

                      Ordenado := True;  -- terminó la ordenación
                   else -- hay que seguir
                      if Fin_Pares = 0 then -- acabaron todos los pares
                         Impares := (N-1)/2; -- cambio de fase
                         Fin_Impares := (N-1)/2;
                         Permutado := False; -- inicializamos permutado
                      end if;
                   end if;

                end Fin_Etapa_Par;
             or
                when (
                   Hay_Datos and Impares > 0) or Ordenado =>
                accept Inicio_Etapa_Impar (
                      Fin :    out Boolean ) do -- CPRE de Inicio_Etapa_Impar
                   Fin := Ordenado;
                   Impares := Impares -1;
                end Inicio_Etapa_Impar;
             or
                when Impares = 0 =>
                accept Fin_Etapa_Impar (
                      Par_Permutado : in     Boolean ) do -- CPRE de Fin_Etapa_Impar

                   Fin_Impares := Fin_Impares - 1;
                   -- Ha acabado un intercambiador de impares

                   Permutado := Permutado or Par_Permutado;

                   if Permutado then
                      -- si se han intercambiado un par de elems, no acaba la ordenación
                      Sin_Cambio := 0;
                   else
                      if Fin_Impares=0 then -- acabaron todos los impares
                         Sin_Cambio := Sin_Cambio + 1;
                      end if;
                   end if;

                   if Sin_Cambio=1 then
                      -- esta cond. se cumplirá si ha finalizado una etapa
                      -- que no es la primera, y no se han intercambiado un par de elems

                      Ordenado := True; -- terminó la ordenación
                   else -- hay que seguir
                      if Fin_Impares = 0 then -- acabaron todos los impares
                         Pares := N/2; -- cambio de fase
                         Fin_Pares := N/2;
                         Permutado := False; -- inicializamos permutado
                      end if;
                   end if;
                end Fin_Etapa_Impar;
             end select;
          end loop;

       end Tipo_Acceso_Vector;

       Gestor : Tipo_Acceso_Vector;
       Vector : Tipo_Vector;

       -- TAREAS

       task type Tipo_Intercambiador (I : Tipo_Rango_Intercambiador);
       task body Tipo_Intercambiador is
          Intermedio : Tipo_Dato;
          Fin,
          Permutado  : Boolean;
       begin
          Put("empieza " & Tipo_Rango_Intercambiador'Image(I));
          loop
             if I mod 2 = 0 then
                Gestor.Inicio_Etapa_Par (Fin);
             else
                Gestor.Inicio_Etapa_Impar (Fin);
             end if;

             if not Fin then
                if Vector(I) > Vector(I+1) then
                   Intermedio := Vector(I);
                   Vector(I) := Vector(I+1);
                   Vector(I+1) := Intermedio;
                   Permutado := True;
                   Put_Line("Intercambia " & Tipo_Dato'Image(Vector(I)) &
                      Tipo_Dato'Image(Vector(I+1)));
                else
                   Permutado := False;
                end if;
                if I mod 2 = 0 then
                   --Gestor.Dec_Pares;
                   Gestor.Fin_Etapa_Par (Permutado);
                else
                   --Gestor.Dec_Impares;
                   Gestor.Fin_Etapa_Impar (Permutado);
                end if;
             end if;
             exit when Fin;
          end loop;
          Put("Fin");
       end Tipo_Intercambiador;

       task type Tipo_Productor;
       task body Tipo_Productor is
       begin

          Vector := (1, 2, 3, 4, 5, 6);
          --Vector := (6, 5, 4, 3, 2, 1);
          Gestor.Iniciar_Ordenacion;

       end Tipo_Productor;

       task type Tipo_Consumidor;
       task body Tipo_Consumidor is
       begin

          Gestor.Esperar_Fin_Ordenacion;
          for I in Tipo_Vector'range loop
             Put (Tipo_Dato'Image(Vector(I)) & " ");
          end loop;

       end Tipo_Consumidor;

       type Tipo_Pintercambiador is access Tipo_Intercambiador;
       type Tipo_Pintercambiadores is array (Tipo_Rango_Intercambiador) of Tipo_Pintercambiador;

       Intercambiadores : Tipo_Pintercambiadores;
       Productor        : Tipo_Productor;
       Consumidor       : Tipo_Consumidor;

    begin
       for I in Tipo_Rango_Intercambiador'range loop
          Intercambiadores(I) := new Tipo_Intercambiador(I);
       end loop;
    end Burbuja_Msg;

- Ordenación por burbuja -- Soluciones
  - Diseño
  - Implementación mediante objetos protegidos
  - Implementación mediante paso de mensajes