next up previous
Next: About this document Up: El peluquero dormilón Previous: El peluquero dormilón

El peluquero dormilón (SOLUCIÓN)

 

El problema del peluquero dormilón (originalmente, el barbero dormilón) es un clásico de la Programación Concurrente. En él se propone la discusión sobre cómo gestionar el ``transito'' por una pequeña peluquería (recurso compartido), por parte de dos tipos de procesos: el peluquero y los clientes. El enunciado sugiere que durante la ejecución la interacción entre el peluquero y un cliente se puede producir muy a menudo y que, por tanto, deben establecerse los mecanismos de sincronización adecuados para evitar que los dos ``colisionen'' dentro la peluquería; es decir, asegurar uno sólo es el que se mueve en cada momento.

Etapa 1.
A continuación se presenta una primera solución del problema, describiendo, mediante seudocódigo, la actividad de los procesos.

MODULE PeluqueroDormilon;

CONST
  NumClientes = 6;
VAR
  I : [1..NumClientes];

TASK Peluquero;
BEGIN
  LOOP
    << Esperar al próximo cliente. Si no hay ninguno dormir >>
    << Cortar el pelo. >>
    << Abrir la puerta y esperar a que salga el cliente >>
  END (* LOOP *)
END Peluquero;

TASK Cliente;
BEGIN
  << Pregunto si hay sitio en la peluquería >>
  IF NOT << Hay sitio >> THEN 
    << Me largo a otra peluquería >>
  ELSE
    << Espero a que me toque >>
    << Me siento en el sillón y me cortan el pelo >>
    << Me voy de la peluquería >>
  END (* IF *)
END Cliente;

BEGIN
  COBEGIN
    Peluquero;
    FORALL I:= 1 TO NumClientes DO
      Cliente
    END; (* FORALL *)
  COEND
END PeluqueroDormilon.

Etapa 2.
Vamos a detectar en la especificación anterior los puntos de sincronización entre los procesos, asociándoles una operación de monitor.

MODULE PeluqueroDormilon;

  .........................

MONITOR Peluqueria;

PUBLIC
  EsperarCliente,
  PedirCorteDePelo,
  FinalCorteDePelo,
  AbrirPuertaEsperarSalida,
  ClienteSale;

PROCEDURE EsperarCliente;
BEGIN
  IF << alg£n cliente espera >> THEN
    << atender cliente >>
  ELSE
    << dormir >>
  END (* IF *)
END EsperarCliente;

PROCEDURE PedirCorteDePelo (VAR meAtienden : BOOLEAN);
BEGIN
  meAtienden := TRUE;
  IF << No hay sitio en la peluquería >> AND
     NOT << Peluquero dormido >> THEN
    meAtienden := FALSE
  ELSIF << Peluquero dormido >> THEN
    << Despertar al peluquero >>
  ELSE
    << Esperar en una de las sillas libres >>
  END (* IF *)
END PedirCorteDePelo;


PROCEDURE FinalCorteDePelo;
BEGIN 
  << Esperar a que el peluquero termine y abra la puerta >>
END FinalCorteDePelo;

PROCEDURE ClienteSale;
BEGIN
  << Avisar al peluquero de que el cliente ha salido >>
END ClienteSale;


PROCEDURE AbrirPuertaEsperarSalida;
BEGIN
  << El peluquero ha abierto la puerta y avisa al cliente >>
  << Esperar a que salga el cliente >>
END AbrirPuertasEsperarSalida;

END MONITOR;


TASK Peluquero;
BEGIN
  LOOP
    Peluqueria.EsperarCliente;
    (* ... Cortar el pelo ... *)
    Peluqueria.AbrirPuertaEsperarSalida;
  END (* LOOP *)
END Peluquero;

TASK Cliente;
VAR
  haySitio : BOOLEAN;
BEGIN
  (* .. Pregunto si me va a poder atender el peluquero .. *)
  Peluqueria.PedirCorteDePelo (haySitio);
  IF NOT haySitio THEN 
    (* .. Me largo a otra peluquería .. *)
  ELSE
    (* .. Me siento y espero a que me corten el pelo .. *)
    Peluqueria.FinalCorteDePelo;
    (* .. Me voy de la peluquería .. *)
    Peluqueria.ClienteSale
  END
END Cliente;

BEGIN 
  ........

END PeluqueroDormilon.

Etapa 3.
Damos un paso más hacia la solución final, dando la implementación de las operaciones del monitor, indicando donde se produce el bloqueo y desbloqueo de los diferentes procesos.

PROCEDURE EsperarCliente;
BEGIN
  IF sillasLibres = NumSillas THEN
    dormido := TRUE;
    Delay (siesta);
    dormido := FALSE
  ELSE
    Continue (clienteEsperando)
  END (* IF *)
END EsperarCliente;

PROCEDURE PedirCorteDePelo (VAR meAtienden : BOOLEAN);
BEGIN
  meAtienden := TRUE;
  IF (sillasLibres = 0) AND NOT dormido THEN
    meAtienden := FALSE
  ELSIF dormido  THEN
    Continue (siesta)
  ELSE
    DEC (sillasLibres);
    Delay (clienteEsperando);
    INC (sillasLibres);
  END; (* IF *)
END PedirCorteDePelo;

PROCEDURE FinalCorteDePelo;
BEGIN
  Delay (puertaAbierta);
END FinalCorteDePelo;

PROCEDURE ClienteSale;
BEGIN
  Continue (salidaCliente);
END ClienteSale;


PROCEDURE AbrirPuertaEsperarSalida;
BEGIN
  Continue (puertaAbierta);
  Delay (salidaCliente)
END AbrirPuertaEsperarSalida;


BEGIN  (* MONITOR *)
  dormido := TRUE;
  sillasLibres := NumSillas
END MONITOR;

Etapa 4.
Solución final. Para ello se desdobla la operación AbrirPuertaEsperarSalida en dos: AbrirPuerta y EsperarSalida, para evitar que después de una operación Continue se realice otra operación. Al realizar este desdoblamiento, debemos añadir cierta información de control que permita saber si un cliente ha salido o no ha salido ya (hayCliente). Finalmente, se tendría el siguiente grafo de interacción:

< M W >
MODULE PeluqueroDormilon;

CONST
  NumClientes = << .. >>;

MONITOR Peluqueria;

PUBLIC
  SiguienteCliente,
  PedirCorteDePelo,
  FinalCorteDePelo,
  AbrirPuerta,
  CerrarPuerta,
  ClienteSale;

CONST
  NumSillas = << .. >>;

VAR
  clienteEsperando  : CONDITION;
  siesta            : CONDITION;
  puertaAbierta     : CONDITION;
  salidaCliente     : CONDITION;
  dormido           : BOOLEAN;
  sillasLibres      : CARDINAL;
  hayCliente        : BOOLEAN;

PROCEDURE SiguienteCliente;
BEGIN
  IF sillasLibres = NumSillas THEN
    dormido := TRUE;
    Delay (siesta);
    dormido := FALSE
  ELSE
    Continue (clienteEsperando)
  END (* IF *)
END SiguienteCliente;

PROCEDURE PedirCorteDePelo (VAR meAtienden : BOOLEAN);
BEGIN
  meAtienden := TRUE;
  IF sillasLibres = 0 THEN
    meAtienden := FALSE
  ELSIF dormido  THEN
    hayCliente := TRUE;
    Continue (siesta)
  ELSE
    DEC (sillasLibres);
    Delay (clienteEsperando);
    INC (sillasLibres);
    hayCliente := TRUE
  END; (* IF *)
END PedirCorteDePelo;

PROCEDURE FinalCorteDePelo;
BEGIN
  Delay (puertaAbierta);
END FinalCorteDePelo;

PROCEDURE ClienteSale;
BEGIN
  hayCliente := FALSE;
  Continue (salidaCliente);
END ClienteSale;

PROCEDURE AbrirPuerta;
BEGIN
  Continue (puertaAbierta);
END AbrirPuerta;

PROCEDURE CerrarPuerta;
BEGIN
  IF hayCliente THEN
    Delay (salidaCliente);
  END (* IF *)
END CerrarPuerta;

BEGIN  (* MONITOR *)
  dormido := TRUE;
  hayCliente := FALSE;
  sillasLibres := NumSillas
END MONITOR;


TASK Peluquero;
BEGIN
  LOOP
    Peluqueria.EsperarCliente;
    (* ... Cortar el pelo ... *)
    Peluqueria.AbrirPuerta;
    (* ... Despedir al cliente .. *)
    Peluqueria.CerrarPuerta
  END (* LOOP *)
END Peluquero;


TASK Cliente;
VAR
  haySitio : BOOLEAN;
BEGIN
  (* .. Pregunto si me va a poder atender el peluquero .. *)
  Peluqueria.PedirCorteDePelo (haySitio);
  IF NOT haySitio THEN 
    (* .. Me largo a otra peluquería .. *)
  ELSE
    (* .. Me siento en el sillon y espero a que me corten el pelo .. *)
    Peluqueria.FinalCorteDePelo;
    (* .. Me voy de la peluqueria .. *)
    Peluqueria.ClienteSale
  END
END Cliente;

VAR
  I : [1..NumClientes];

BEGIN
  COBEGIN
    Peluquero;
    FORALL I:= 1 TO NumClientes DO
      Cliente
    END; (* FORALL *)
  COEND
END PeluqueroDormilon.



Angel Herranz Nieva
Thu Oct 31 20:08:57 MET 1996