Monitores

De Departamento de Informatica
Saltar a: navegación, buscar

Contenido

Introducción

En un sistema pueden existir algunos procesos que necesitan comunicarse entre sí, compitiendo además por los recursos del sistema, una zona de datos específicos o un dispositivo de E/S, y dicha competición se debe regular a través de la sincronización de los procesos. Las técnicas de sincronización son el fundamento del procesamiento concurrente. Existen dos métodos básicos de comunicación entre procesos: “Compartición de datos” e “Intercambio de información”. En este tema se trata inicialmente el problema de la comunicación entre procesos mediante “Compartición de datos”. Los “Semáforos” constituyen el mecanismo básico fundamental para el problema de la sincronización pero dado que en la utilización de éstos pueden existir errores de temporización debido a su incorrecto uso y a que son difíciles de detectar, es que nace la idea de “Monitores” que proporcionan un mecanismo alternativo al de los Semáforos.


Desventajas al utilizar Semáforos:

  • El uso y la función de las variables no es explícito.
  • Están basados en variables globales → No es modular.
  • Las operaciones sobre las variables dispersas y no protegidas.
  • Acceso no estructurado ni encapsulación → Fuente de errores.

Conceptos Fundamentales

Partamos definiendo algunos conceptos fundamentales:

Condiciones de Carrera (del inglés race condition):

  • Se da principalmente cuando varios procesos acceden al mismo tiempo a un recurso compartido, por ejemplo una variable, cambiando su estado y obteniendo de esta forma un valor no esperado de la misma.
  • Cuando dos o más procesos leen o escriben en un área de memoria compartida, el resultado final de este proceso depende de los instantes de ejecución que contenga cada uno.
  • Una solución a este problema es que el acceso simultáneo a las variables compartidas sea llevado por un proceso a la vez, garantizando la exclusión mutua.

Exclusión Mutua:

  • Su finalidad es garantizar la integridad del sistema y ésta se genera cuando un proceso excluye temporalmente a otros procesos para utilizar un recurso compartido.

Si Pi se está ejecutando en su Sección Crítica, entonces ningún Pj ( con j ≠ i ) puede ejecutarse en su Sección Crítica.

Sección Crítica:

  • Es la parte del programa o segmento de código con un comienzo y un final claramente marcados que permiten la modificación de recursos (variables) compartidos por diversos procesos.
  • Condiciones para que la exclusión mutua sea válida:
  • Sólo pueden realizar modificaciones un proceso a la vez, no pueden desarrollarse dos procesos dentro de sus respectivas regiones críticas si hay recursos compartidos. Se debe garantizar la exclusión mutua entre los diferentes procesos.
  • No hacer suposiciones sobre la velocidad relativa de los procesos en conflicto.
  • Cualquier proceso fuera de la sección crítica no debe interrumpir el acceso a ésta.
  • Si hay más de un proceso deseando entrar a la sección crítica no se generarán bucles infinitos ya que se concederá a la entrada un tiempo finito.


Para solucionar el problema de la exclusión mutua tenemos tres tipos de soluciones:

  • Soluciones software.
  • Soluciones hardware (Optimistas, Pesimistas).
  • Soluciones aportadas por el Sistema Operativo (Semáforos, Monitores,Mensajes).

A continuación nos referiremos a una de las tres soluciones aportadas por el Sistema Operativo llamado Monitores.

¿Qué son los Monitores?

Un monitor es un mecanismo de alto nivel de Software para control de concurrencia que contiene una colección de datos y los procedimientos necesarios para realizar la asignación de un determinado recurso o grupo de recursos compartidos por varios procesos.

Son una estructura de un lenguaje de programación similar a los semáforos en cuanto a funcionalidad, pero son más simples de manejar y controlar, son más estructurados, es decir un tipo de dato abstracto que encapsula datos privados y proporciona métodos públicos (Monitor = Encapsulación). La idea de un Monitor fue presentada primero por Dijkstra en 1971 donde hizo una propuesta de una unidad de programación denominada “Secretary” para encapsular datos compartidos, junto con los procedimientos para acceder a ellos. Posteriormente por Brinch Hansen (1973) que propuso las clases compartidas ("shared class"), una construcción análoga a la anterior. Luego ésto fue mejorado por Hoare y en 1974 fue quien acuñó el nombre de “Monitor”. Posteriormente, Hansen incorpora los monitores al lenguaje Pascal concurrente en el año 1975.

Los Monitores se caracterizan porque proveen sincronización de procesos con exclusión mutua, es decir, que sólo se permite que un proceso puede estar activo, en el caso que se tenga un recurso o un grupo de recursos que están siendo compartidos por un conjunto de procesos, otorgando una solución al problema que produce la concurrencia.

Los procesos no pueden usar directamente la representación de un tipo Monitor por lo tanto un procedimiento definido dentro de un monitor sólo tiene acceso a las variables declaradas localmente y a los parámetros formales. De manera similar, sólo los procedimientos locales pueden tener acceso a las variables locales de un Monitor.

Resumiendo las Características básicas de un Monitor son:

  • Es un Módulo de software.
  • Tipo Abstracto de Dato (TAD).
  • Mecanismo de alto nivel (impuesto por el compilador).
  • Estructura Fundamental de Sincronización.
  • Exclusión mutua (impuesta por la estructura del Monitor): sólo un proceso puede acceder al Monitor en cada momento, cualquier otro que lo invoque debe esperar.
  • Variables de datos locales sólo se acceden a través de los procedimientos del Monitor.
  • Un proceso entra al monitor invocando uno de sus procedimientos.

Visionesquematicamonitor.PNG

Figura: Vista esquemática de un Monitor

Estructura

Los monitores tiene distintas formas de declaración y creación según el lenguaje de programación utilizado, así que a continuación utilizamos la siguiente notación genérica:

Estructura

Datos (privados)
  • Recurso compartido
  • Colas (“condition variable” = assertion)
  • Variables internas
Procedimientos (públicos)
  • entry()
  • signal()
  • wait()
Secuencia de inicio

Sintaxis de un monitor:

monitor monitor-nombre{

//declaracion variables compartidas
procedure P1 (…) { … }
…
procedure Pn (…) {……}
//Código inicialización
Initialization code ( …) { … }
…
} 


El tipo de dato "Monitor" contiene la declaración de variables compartidas cuyos valores definen el estado de una instancia de dicho tipo. Tiene un cuerpo de procedimientos o funciones que operan dichas variables. La representación de un tipo Monitor no puede ser utilizada directamente por los distintos procesos, es por eso que dentro de un Monitor sólo se puede acceder a variables locales y a sus parámetros formales.


Esquema del código de un monitor:

Monitor-name:monitor;
      begin
            <declaración de variables>
            <cond-var>: condition;
      procedure <proc-name>;
            begin;
            …<cond-var>.<signal o wait>...
            ...If <cond-var>.queue then …
            end;
            ...
      begin
            <init-code>
      end;


Estructuramonitor.png Figura muestra la estructura de un monitor


Importante destacar!

  • Asegura que sólo un proceso a la vez puede estar activo dentro del Monitor.
  • El programador no necesita codificar explícitamente.
  • Se agrega el constructor condition para sincronización.

Variables de Condición

El programador no necesita codificar explícitamente sincronizaciones pues como mencionamos anteriormente la estructura del Monitor asegura y permite que se esté realizando un solo proceso a la vez . Sin embargo, necesitamos establecer mecanismos adicionales de sincronización porque la estructura Monitor no es lo suficientemente potente para modelarlos. Se define una sincronización con la estructura condition, donde el programador puede definir una o más variables de este tipo:

condition x, y; 

Existen dos operaciones las cuales pueden ser llamadas por la variable conditon: wait() y signal().

  • x.wait();
Indica que el proceso que ha invocado esta operación queda suspendido hasta que otro proceso invoque la operación x.signal();
  • x.signal()
Permite que se reanude exactamente uno de los procesos suspendidos. En el caso de no haber ningún proceso suspendido, la operación signal() no tiene efecto, y el estado de x será el mismo que si la operación nunca se hubiera llamado.

Cuando un proceso invoca la operación x.signal(), asumimos que hay un proceso en estado suspendido asociado a la condición x. Entonces si el proceso suspendido Q reanuda su ejecución, el proceso P que ha efectuado la señalización deberá esperar; de otro modo, P y Q se activarán simultáneamente dentro del Monitor. Por otro lado, conceptualmente ambos procesos podrían continuar con su ejecución. Existen dos posibilidades:

  1. Señalizar y esperar: el proceso P espera hasta que el proceso suspendido Q salga del Monitor o espere a que se produzca otra condición.
  2. Señalizar y continuar: el proceso suspendido Q espera hasta que el proceso P salga del Monitor o espere a que se produzca otra condición.

Variablesdecondicion.PNG Figura:Monitor con variables de condición

Ventajas y Desventajas

Con las características presentadas podemos llegar a la conclusión que los monitores otorgan más confiabilidad al programador y escalabilidad, conveniencia y eficacia en la sincronización de procesos.

Ventajas del uso de Monitores:

  • Exclusión mutua automática: Al ejecutar un “wait” (dormir) al proceso que está dentro del monitor, inmediatamente se permite que entre otro proceso que esté en la cola esperando a entrar.
  • Ejecución simultánea o concurrencia modular: Evitando conflictos de compartición de recursos al existir exclusión mutua.
  • Modularidad: Sólo en el Monitor se tiene visibilidad sobre los objetos que están declarados en él.
  • Encapsulamiento o abstracción: Su estructura encierra variables compartidas o recursos, es decir, que no se les permite entrar directamente a estructuras internas del Monitor desde procedimientos que hayan sido declarados externos a éste.
  • Facilidad de mantención: La sincronización de procesos se realiza en el interior del Monitor, por lo que es más fácil de verificar, y por ende se facilita su mantenimiento.

Ventajas comparando con estructuras de bajo nivel:

  • Construcción de alto nivel: Donde hablamos de Modularidad.
  • Exclusión mutua automática: En este caso también podemos mencionarla.
Lenguajes de alto nivel, como por ejemplo JAVA, facilitan la programación concurrente incorporando métodos que manejan Monitores (por ejemplo en JVM se utiliza el concepto de monitores para realizar el acceso con exclusión mutua a sus objetos).


Desventajas del uso de Monitores:

  • Sincronización depende del programador: Razón por la cual existe la probabilidad de errores.
  • Riesgo de deadlock,(Inter Bloqueo): Por ejemplo consideremos dos procesos P1 y P2 y dos recursos críticos R1 y R2. Supongamos ahora que cada proceso necesita acceder a ambos recursos para llevar a cabo una parte de su función. En tal caso, es posible que el Sistema Operativo asigne R1 a P2 y R2 a P1. Cada proceso está esperando a uno de los dos recursos y ninguno liberará el recurso que ya posee hasta que adquiera el otro y ejecute su sección crítica. En este caso se dice que ambos procesos están interbloqueados. Otra situación en la que se produce interbloqueo es cuando dos procesos están bloqueados en un receive() y esperan un mensaje que nunca les va a llegar.
  • Probabilidades de starvation: Es decir, que se tengan procesos de baja prioridad que nunca lleguen a ejecutarse.
  • Muy costoso: Al bloquearse muchos procesos, se produce una pérdida de eficiencia.
  • Riesgo de thrashing o hiperpaginación: sucede cuando se utiliza una gran cantidad de recursos de manera creciente para hacer una cantidad cada vez más baja de trabajo. Generalmente se refiere a cuando se cargan y descargan constantemente partes de la imagen de un proceso desde y hacia la Memoria Principal y la Memoria Virtual o espacio de intercambio.

Ejemplos Prácticos

Productor/consumidor con un buffer circular: Se utiliza cuando los sistemas operativos asignan a los procesos una cantidad fija de memoria, vista como un arreglo circular, esta memoria está organizada de tal forma que actúa como enlace para la comunicación entre productor/consumidor, ajustando las diferencias de velocidad entre productor/consumidor y con esto coordinando la transferencia de información. El productor almacena en este arreglo o buffer, mientras que el consumidor va vaciando o consumiendo lo que el productor almacenó, en un orden FIFO.

Para tener un control y organización del acceso con concurrencia de forma que exista una ejecución de manera secuencial, se deben utilizar algoritmos de sincronización de procesos. En este caso presentamos una solución utilizando monitores.

Productoconsumidormonitor.PNG


Figura: Producto consumidor en monitor

Productor/Consumidor implementado con un monitor

 
monitor ProductorConsumidor 
    condition full, empty; 
    int count; 

    procedure enter; 
    begin 
        if count = N then wait(full); 
        enter_item; 
        count:= count + 1; 
        if count = 1 then signal(empty); 
    end; 

    procedure remove; 
    begin 
        if count = 0 then wait(empty); 
        remove_item; 
        count:= count - 1; 
        if count = N - 1 then signal(full); 
    end; 

    count:= 0; 
end monitor; 

procedure productor; 
begin 
    while true do 
    begin 
        produce_item; 
        ProductorConsumidor.enter; 
    end 
end; 
procedure consumidor; 
begin 
    while true do 
    begin 
          ProductorConsumidor.remove; 
          consume_item; 
    end 
end; 
begin 
    parbegin
        productor; 
        consumidor; 
    parend
end 


Buffer Circular de Productor/Consumidor implementado con un monitor

 module MonitorBufferCircular; 
  var bufferCircular: array[0..Espacios-1] of cosas; 
      espacioEnUso  : [0..Espacios]; 
      EspacioAllenar: [0..Espacios-1]; 
      EspacioAvaciar: [0..Espacios-1]; 
      BCircularTieneDatos,  
      BCircularTieneEspacio:condition; 

procedure llenarEspacio(datosEspacio:cosas); 
begin
    if espacioEnUso = espacios then
        wait(BCircularTieneEspacio); 
    end;
    bufferCircular[EspacioAllenar]:=datosEspacio; 
    inc(espacioEnUso); 
    EspacioAllenar:=  
                    (EspacioAllenar+1) mod espacios; 
    signal(BCircularTieneDatos); 
end llenaEspacio; 

procedure vaciaEspacio; 
begin
    if espacioEnUso = 0 then
        wait(BCircularTieneDatos); 
    end;
    datosEspacio:=bufferCircular[EspacioAvaciar]; 
    dec(espacioEnUso); 
    EspacioAvaciar:=(EspacioAvaciar+1) mod espacios; 
    signal(BCircularTieneEspacio); 
end vaciaEspacio; 

begin
    espacioEnUso:= 0; 
    EspacioAllenar:= 0; 
    EspacioAvaciar:= 0; 
end monitorBufferCircular 


Ejemplo Básico:

 
monitor Contador{
      //operaciones públicas
      public Contador(){
            valor=0;
      }
      public void incrementa(){
            valor++;
      }
      public int actual(){
            return valor;
      }
      int valor;	
      //variable interna privada
};
Contador.incrementa();
V=Contador.actual();


Definición de un monitor para N recursos:

	 	 	
Allocator = Monitor
  var free = condition;
  var recursos = integer;
  Procedure RESERVE()
      if recursos <= 0 then wait(free); /* No hay recursos, entonces espera */
    recursos --;
   end;
   procedure RELEASE()
    recursos ++;
    if recursos = 1 then signal(free);
   end;
/* sólo se pudieron poner en cola procesos si no habían recursos */
   begin
    recursos = n;
   end;

Si varios procesos intentan manipular el monitor al mismo tiempo, van entrando de uno en uno: no puede haber más de un proceso trabajando con el monitor en cada momento.


Comparando la solución con semáforos:

En los ejemplos mostrados también existe una solución implementada con semáforos. En el caso que se utilicen semáforos, su estructura está constituida por una cola y también por el valor asociado a las variables de condición. En cambio con la utilización de monitores, la estructura es más simple, porque sólo se tiene una cola de procesos.

Referencias

http://sistemasoperativo252m.blogspot.com/2011/01/2_8537.html - Monitores Sistemas Operativos[Revisada 3 de Noviembre 2012]

http://trevinca.ei.uvigo.es/~formella/doc/cd05/node80.html - Monitores[Revisada 11 de Noviembre 2012]

Artículos

http://www.ctr.unican.es/asignaturas/procodis_3_II/Doc/Procodis_2_05.pdf - Sincronización basada en memoria compartida-Monitores

http://www.talgo32.es/archivos/SO1/uned/ResTema3.pdf - Sincronización y comunicación de procesos

http://sopa.dis.ulpgc.es/so/teoria/pdf/so-07-Concurrencia.pdf - Concurrencia

http://www3.uji.es/~redondo/so/capitulo3_IS11.pdf - Concurrencia entre procesos

http://antares.itmorelia.edu.mx/~fmorales/SisDisII/monitores.pdf - Monitores

http://web.dit.upm.es/~pepe/libros/concurrency.pdf - Java concurrencia

Herramientas personales
Espacios de nombres
Variantes
Acciones
Navegación
Herramientas