next_inactive up previous



Examen de Programación Concurrente sep02






Dpto. LSIIS. Unidad de Programación

Normas

Dispones de dos horas para realizar estas dos preguntas, que deberás entregar en hojas separadas.

Ordenación por burbuja[2 horas, 7 puntos]

Una posible solución se muestra en el grafo de procesos:

\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.

Se pide:

  1. [d)] Implementación mediante objetos protegidos del recurso AccesoVector, incluyendo tablas de sincronización y código del tipo protegido.[3.5 puntos]

  2. [e)] Implementación mediante rendez-vous. [3.5 puntos]





Manuel Carro
2002-09-26