Monitores

Un monitor es la versión concurrente de una estructura de datos: posee un estado interno más un conjunto de operaciones. A pesar de que las operaciones se invocan concurrentemente, el monitor las ejecuta secuencialmente.

Los monitores fueron inventados por Hoare para un dialecto de Pascal, de ahí su sintaxis a la Pascal.

Sintaxis:

type <nombre> = monitor
  <variables>
  procedure entry <proc1>( <argumentos1> );
    <cuerpo>
  procedure entry <proc2>( <argumentos2> );
    <cuerpo>
    ...
  begin
    <inicializaciones>
  end

Las operaciones son <proc1>, <proc2>, ... El código asociado a todas estas operaciones es una sección crítica y por lo tanto nunca hay dos instancias en ejecución. Sin embargo el monitor puede suspender la ejecución de una operación para eventualmente ejecutar otra y más tarde retomar la operación suspendida. Esto se logra mediante variables de tipo condition.

Declaración: var x: contition

Las siguientes acciones sobre variables condicionales deben ser invocadas dentro de una de las operaciones del monitor.

• x.wait: El proceso que llega a ejecutar esta acción se suspende hasta que otro proceso invoque x.signal dentro del mismo monitor. El proceso queda en una cola FIFO que forma parte de x.

• x.signal: Si no hay procesos encolados en esta variable, la acción se ignora (no confundir con semáforos). Si x tiene procesos encolados, el proceso que invoca x.signal cede el monitor al primer proceso que quedó en espera. El proceso que ha cedido el monitor podrá recuperarlo cuando el proceso que lo recibió salga del monitor, salvo que este último lo ceda con otro signal a un tercer proceso.

Resolvamos el problema del productor/consumidor con monitores. Inicialmente:

Var buffer: BUFFER;

Para depositar un ítem x, un productor ejecuta buffer.Put(x); mientras que para extraer un ítem, un consumidor ejecuta buffer.Get(x); donde x se pasa por referencia.

El tipo BUFFER se define como un monitor en el siguiente código:

type BUFFER= monitor

  var pool: array[0..N-1] of Item;
      in, out, count: Integer;
      noempty, nofull: condition;

  Procedure entry Put(x: Item);
  begin
    if (count=n) then nofull.wait;
    pool[in]:= x;
    in:= (in+1) mod N;
    count:= count+1;
    noempty.signal;
  end

  Procedure entry Get(var x: Item);
  begin
    if (count=0) then noempty.wait;
    x:= pool[out];
    out:= (out+1) mod N;
    count:= count+1;
    nofull.signal;
  end;

El problema de los escritores y lectores

En este problema varios procesos concurrentes comparten una misma estructura de datos y necesitan consultarla o actualizarla (modificarla). Un proceso lector es aquel que está consultando la estructura y un proceso escritor es aquel que la está modificando. Las características de este problema son las siguientes:

• Se permite varios procesos lectores al mismo tiempo.

• Sólo se permite un escritor en un instante dado. Mientras el escritor modifica la estructura no puede haber procesos lectores ni otros procesos escritores.

Veamos una solución usando monitores. El monitor M controlará el acceso a la estructura de datos. Se definen entonces las siguientes operaciones en el monitor:

• M.EnterRead: Un proceso anuncia que entra en un trozo de código en que va a consultar la estructura de datos. Es decir el proceso se convierte en lector.

• M.ExitRead: El lector anuncia que sale del código de consulta.

• M.EnterWrite: Un proceso anuncia que entra a un segmento de código en que va a actualizar la estructura de datos. Es decir el proceso se convierte en un escritor.

• M.ExitWrite: El escritor anuncia que sale del código de actualización.

Solución

Var M: Monitor
  var readers: integer;
      writing: boolean;
      canread: condition;
      canwrite: condition;
  Procedure Entry EnterRead
  begin
    if (writing) then
       canread.wait;
    Incr(readers);
    canread.signal
  end;
  Procedure Entry ExitRead
  begin
    Decr(readers);
    if (readers=0) then
      canwrite.signal
  end;
  Procedure Entry EnterWrite
  begin
    if ((readers>0)
        or writing) then
      canwrite.wait; { (1) }
    writing:= true
  end;
  Procedure Entry ExitWrite
  begin
    writing:= false;
    canwrite.signal; { (2) }
    if (not writing) then
      canread.signal { (3) }
  end
  begin
    writing:= false;
    readers:= 0
  end

Observe que en (2) se presentan dos posibilidades. En la primera hay escritores esperando por lo que el proceso cede el monitor al escritor bloqueado en (1) y sólo lo recuperará cuando el escritor salga del monitor. Al recuperar el monitor writing será verdadera. La segunda posibilidad es que no hayan escritores en espera. En este caso el proceso no cede el control y writing será falso, por lo tanto si hay lectores esperando, éstos serán desbloqueados en (3).

Esta solución tiene inconvenientes, puesto que los escritores pueden sufrir hambruna ( starvation). Un proceso sufre hambruna cuando otros procesos pueden concertarse para hacer que nunca logre obtener un recurso. En este caso, si siempre hay lectores ( readers>0) consultando la estructura, los escritores serán bloqueados para siempre.

El problema de la hambruna de los escritores se puede resolver haciendo que no entren más lectores cuando hay escritores esperando. Esto se puede lograr con pequen as modificaciones a la solución presentada. Sin embargo ahora el problema es que los escritores pueden causar hambruna a los lectores.

Cuando una solución no provoca hambruna a ninguna tarea se dice que esta solución es equitativa (en inglés fair). Una solución equitativa del problema de los lectores y escritores es que éstos sean atendidos en orden FIFO, pero atendiendo concurrentemente todos los lectores que lleguen durante un lapso en que no llegan escritores. Lamentablemente, no es sencillo implementar esta solución con monitores. Luego implementaremos esta solución usando mensajes y tareas en nSystem.