next_inactive up previous



Examen de Programación Concurrente sep02






Dpto. LSIIS. Unidad de Programación

Ordenación por burbuja -- Soluciones

Diseño

\epsfig{figure=grafo.eps,height=4cm}

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


\begin{ctadsol}
\nombrectad{AccesoVector}
\\
\operaciones
\operacion{Inicia...
...edge$ a.HayDatos}
\nomop{EsperarFinOrdenacion (a)}
\post{Cierto}
\end{ctadsol}

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;





Manuel Carro
2002-09-26