up previous
Up: Examen de Programación Concurrente Previous: Diseño de un controlador

Subsecciones



Implementación de un controlador para un cruce de trenes [4 puntos]

Se ha llegado al siguiente diseño (aunque hay otros posibles, igualmente válidos) para el problema planteado en la pregunta [*]:


\includegraphics[width=0.9\textwidth]{im/recurso-estacion}


Hay un proceso AdmisionPeticion(i) por cada estación que se encarga de esperar a que un tren esté cargado y transmite esta información al recurso. El proceso ControladorSalida(i) permite la salida de un tren en la estación i poniendo el semáforo correspondiente a verde. El proceso ControladorCruce(i) señala que el cruce está libre porque ya ha pasado el tren. El seudocódigo de los procesos es:


\begin{lstlisting}{}
TASK AdmisionPeticion(i)
LOOP
Terminal.LeerPeticion(i, ClaseTren, Via);
Estacion.TrenListo(i, ClaseTren, Via);
END;
END;
\end{lstlisting}

\begin{lstlisting}{}
TASK ControladorCruce(i)
LOOP
Sensor.EsperarPasoTren(i);
Estacion.YaPasoTren;
END;
END;
\end{lstlisting}


\begin{lstlisting}{}
TASK ControladorSalida(i)
LOOP
Estacion.PermisoSalirEst(i, Via);
Semaforo.DarSalida(i, Via);
END;
END;
\end{lstlisting}

La especificación del C-TAD es la siguiente:


C-TAD ControlEstacion 

C-Operaciones
ACCION Inicializar: TipoControlEstacion
ACCION TrenListo: TipoControlEstacion \ensuremath{\times} TipoNumEst \ensuremath{\times} TipoTren \ensuremath{\times} TipoVia
ACCION PermisoSalirEst: TipoControlEstacion \ensuremath{\times} TipoNumEst \ensuremath{\times} TipoVia
ACCION YaPasoTren: TipoControlEstacion

TRANSACCIONES
Inicializar
TrenListo
PermisoSalirEst
YaPasoTren

CONCURRENCIA
ninguna

DOMINIO
Tipo: TipoControlEstacion = ( CruceOcupado: $\mathsf{booleano}$ \ensuremath{\times}
ColaUrg: $\mathsf{Secuencia(Secuencia(\emph{TipoVia}))}$ \ensuremath{\times}
ColaNorm: $\mathsf{Secuencia(Secuencia(\emph{TipoVia}))}$ )
TipoVia = 1..MaxVias
TipoNumEst = 1..2
TipoTren = Urgente $\vert$ Normal

Invariante: $\forall t \in\emph{TipoControlEstacion} \ensuremath{\bullet}(\mathsf{Longitud}(t.ColaUrg) = 2 \;\wedge\mathsf{Longitud}(t.ColaNorm) = 2)$


CPRE: cierto
Inicializar(Cnt)
POST: Prepara el estado inicial del recurso
POST: $Cnt.CruceOcupado^{sal} = \mathsf{falso} \; \wedge$
$\mathsf{Longitud}(Cnt.ColaUrg^{sal}(1)) = 0 \; \wedge\mathsf{Longitud}(Cnt.ColaUrg^{sal}(2)) = 0 \; \wedge$
$\mathsf{Longitud}(Cnt.ColaNorm^{sal}(1)) = 0 \; \wedge\mathsf{Longitud}(Cnt.ColaNorm^{sal}(2)) = 0$


CPRE: cierto
TrenListo(Cnt, Est, Tipo, Via)
POST: Indica que un tren se encuentra listo para salir.
Se guarda la v'ia en la cola correspondiente a su tipo y estaci'on
POST: $Cnt^{sal} = Cnt^{ent} \; \backslash $$(Tipo = Urgente \rightarrow \emph{Insertar}(Cnt.ColaUrg(Est),Via)) \; \wedge$
$(Tipo = Normal \rightarrow \emph{Insertar}(Cnt.ColaNorm(Est),Via))$
Donde: $\emph{Insertar}(s, e) = (s^{sal} = s^{ent} \backslash\mathsf{Longitud}(s^{sal}) = \mathsf{Longitud}(s^{ent}) + 1 \wedge s^{sal}(\mathsf{Longitud}(s^{sal})) = e)$


CPRE: $(HayUrgentes \; \vee HayNormales) \wedge \negCnt.CruceOcupado^{ent}$
PermisoSalirEst(Cnt, Est, Via)
POST: Cuando hay trenes esperando a salir y el cruce no est'aocupado, se desbloquea y devuelve
el numero de v'ia en la que est'a el tren con m'as alta prioridad
POST: $Cnt^{sal} = Cnt^{ent} \; \backslash \;Cnt.CruceOcupado^{sal} = \mathsf{verdad} \;\wedge (HayUrgentes\rightarrow \emph{Retirar}(Cnt.ColaUrg(Est), Via))$
$(\neg HayUrgentes \wedge HayNormales \rightarrow\emph{Retirar}(Cnt.ColaNormal(Est), Via))$
Donde: $LongUrg = \mathsf{Longitud}(Cnt.ColaUrg^{ent}(Est)) \;\wedge LongNorm = \mathsf{Longitud}(Cnt.ColaNormal^{ent}(Est)) \; \wedge$
$HayUrgentes = (LongUrg > 0) \; \wedge HayNormales = (LongNorm >0)\; \wedge$
$\emph{Retirar}(s, e) = (e^{sal} = s^{ent}(1) \wedgel = \mathsf{Longitud}(s^{ent...
...wedge \mathsf{Longitud}(s^{sal}) = l- 1 \wedge s^{sal}(1..l-1) = s^{ent}(2..l))$


CPRE: cierto
YaPasoTren(Cnt)
POST: Indica que el cruce se encuentra libre
POST: $Cnt^{sal} = Cnt^{ent} \backslashCnt.CruceOcupado^{sal} = \mathsf{falso}$


Se pide: basándose en la especificación anterior, codificar, utilizando el lenguaje CcModula y mediante la técnica de paso de mensajes síncrono y la metodología explicada en clase, un recurso activo que implemente las operaciones del C-TAD ControlEstacion. Pueden suponerse implementaciones ya realizadas (pero no necesariamente preparadas para un acceso concurrente) de los tipos de datos abstractos básicos (listas, colas, pilas, etc.). La implementación debe evitar la inanición entre estaciones: un tren que en una estación puede salir inmediatamente porque es el primero teniendo en cuenta su tipo y posición en su cola de salida, debe recibir permiso para salir en un tiempo finito.

Solución propuesta:

  CONST
       NUMESTACIONES = 2;
       MAXVIAS = 2;

  (* DECLARACION DE TIPOS *)

  TYPE
       TipoVacio = CARDINAL;
       TipoNumEst = [1..NUMESTACIONES];
       TipoVia = CARDINAL;
       TipoTren = (urgente, normal);
       TipoSalida = RECORD
                         numestacion: TipoNumEst;
                         numvia: TipoVia;
                         tipotren: TipoTren;
                    END;


  VAR
       (* DECLARACION DE LOS CANALES *)
       canTrenListo: CHANNEL; (* OF TipoSalida *)
       canPermisoSalirEst: ARRAY [1..NUMESTACIONES] OF CHANNEL; (* OF TipoVacio *)
       canYaPasoTren: CHANNEL; (* OF TipoVacio *)
       canDevVia: ARRAY [1..NUMESTACIONES] OF CHANNEL; (* OF TipoVia *)

  (* CODIGO QUE IMPLEMENTA EL RECURSO ACTIVO *)

  TASK ControlEstacion;
   VAR
     (* Estado del recurso *)
       cruceocupado: BOOLEAN;
       colaurg, colanorm: ARRAY TipoNumEst OF COLA.TipoCola;
     (* variables auxiliares *)
       i: TipoNumEst;
       viaquesale: TipoVia;
       datossalida: TipoSalida;
       vacio: TipoVacio;

  BEGIN
    (* Inicializacion del recurso *)

    GetChannel (canTrenListo);
    GetChannel (canYaPasoTren);
    FOR i := 1 TO NUMESTACIONES DO
        GetChannel (canPermisoSalirEst[i]);
        COLA.Vacia(colaurg[i]);
        COLA.Vacia(colanorm[i]);
    END;
    cruceocupado := FALSE;

    LOOP
       SELECT
          (* Canal para la operacion YaPasoTren *)

          WHEN cruceocupado, Receive (canYaPasoTren, vacio) DO
              cruceocupado := FALSE;

          (*
             Para la operacion PermisoSalirEst se emplean dos canales,
             uno para cada estacion (1 y 2). Dado que CCMODULA elige de
             forma equitativa entre todos los canales abiertos en una
             espera selectiva, se asegura la equidad entre las dos estaciones,
             y por tanto se evita la inanici¢n de una de las estaciones.
          *)

          WHEN NOT (cruceocupado) AND (NOT (COLA.EsVacia(colaurg[1])) OR
          NOT (COLA.EsVacia(colanorm[1]))),
                    Receive (canPermisoSalirEst[1], vacio) DO
              cruceocupado := TRUE;

              (* si hay trenes urgentes esperando en esta estacion,
                 deben salir antes *)
              IF NOT(COLA.EsVacia(colaurg[1])) THEN
                 COLA.Primero(colaurg[1], viaquesale);
                 COLA.Borrar(colaurg[1]);
              ELSE
                 COLA.Primero(colanorm[1], viaquesale);
                 COLA.Borrar(colanorm[1]);
              END;

              (* se devuelve la via del tren que va a salir desde
                 la estacion 1 *)
              Send (canDevVia[1], viaquesale);

          WHEN NOT (cruceocupado) AND (NOT (COLA.EsVacia(colaurg[2])) OR
          NOT (COLA.EsVacia(colanorm[2]))),
                    Receive (canPermisoSalirEst[2], vacio) DO
              cruceocupado := TRUE;

              (* si hay trenes urgentes esperando en esta estacion,
                 deben salir antes *)
              IF NOT(COLA.EsVacia(colaurg[2])) THEN
                 COLA.Primero(colaurg[2], viaquesale);
                 COLA.Borrar(colaurg[2]);
              ELSE
                 COLA.Primero(colanorm[2], viaquesale);
                 COLA.Borrar(colanorm[2]);
              END (* IF *);
              (* se devuelve la via del tren que va a salir desde
                 la estacion 2 *)
              Send (canDevVia[2], viaquesale);

          (* Canal para la operacion TrenListo *)

          WHEN TRUE, Receive (canTrenListo, datossalida) DO
              IF datossalida.tipotren = urgente THEN
                 COLA.Insertar(colaurg[datossalida.numestacion], datossalida.numvia);
              ELSE
                 COLA.Insertar(colanorm[datossalida.numestacion], datossalida.numvia);
              END;

       END (* SELECT *)
    END (* LOOP *)
  END ControlEstacion;

  (* Codigo de las operaciones del recurso *)

  PROCEDURE TrenListo (i: TipoNumEst; clasetren: TipoTren; via: TipoVia);
  VAR
    datossalida: TipoSalida;
  BEGIN
      datossalida.numestacion := i;
      datossalida.numvia := via;
      datossalida.tipotren := clasetren;
      Send (canTrenListo, datossalida);
  END TrenListo;

  PROCEDURE YaPasoTren;
  VAR
    vacio: CARDINAL;
  BEGIN
      Send (canYaPasoTren, vacio); (* se manda una sennal *)
  END YaPasoTren;



  PROCEDURE PermisoSalirEstacion (i: TipoNumEst; VAR via: TipoVia);
  VAR
    vacio: CARDINAL;
  BEGIN
      Send (canPermisoSalirEst[i], vacio);
      Receive (canDevVia[i], via);
  END PermisoSalirEstacion;


up previous
Up: Examen de Programación Concurrente Previous: Diseño de un controlador
Manuel Carro
2001-10-04