Monitores

5/13/2018 Monitores - slidepdf.com

http://slidepdf.com/reader/full/monitores-55a74f1babc6f 1/32

Tema 3. Monitores

Programación Concurrente

Depto. de Lenguajes y Sistemas InformáticosUniversidad de Granada



Contenidos

1. Concepto de Monitor

1.1. Fundamento teórico de los monitores

1.2. Sintaxis de los monitores

1.3. Exclusión mutua con monitores

1.4. Instanciación de monitores

2. Sincronización en Monitores

2.1. Primitivas de sincronización en monitores

2.2. Efecto de las operaciones sincronización sobre la exclusiónmutua del monitor

2.3. Equivalencia entre semáforos y monitores

2.4. Problemas paradigmáticos resueltos con monitores



1.1. Fundamento teórico de los monitores

• Inconvenientes mecanismos como los semáforos:– Basados en variables globales → No modular.– Uso y función de las variables no explícito.– Operaciones sobre variables recurso dispersas y no protegidas.

• No Acceso estructurado ni encapsulación → Fuente de errores.

• Monitor (Hoare 1974) : Mecanismo de alto nivel que permite– Definir objetos abstractos compartidos (una colección de datos y procedimientos

asociados que se comparten por varios procesos).– Garantizar acceso exclusivo a datos e implementar sincronización.

• Monitor = Encapsulación

– Definición recurso (datos).

– Operaciones de Manipulación (procedims.)

• Recurso: Se percibe como un módulo al que se accede concurrentemente. – El usuario ignora detalles de implementación del recurso y de las

operaciones asociadas.




1.1.1. Centralización de funciones críticas.

• Origen: S.O. concurrente → Monitor monolítico → Programa que centraliza lasfunciones críticas (asig./planif. recursos) del sistema.

• Soportados por facilidades hardware:– Ejecución en modo ininterrumpido (E.M.).– Acceso a posiciones de memoria privilegiadas.– Ejecución de instrucciones privilegiadas.

• Monitor: Versión “descentralizada” del monitor original.• Cada monitor tiene:

– Una función específica.– Datos e instrucciones propias.

• Ejemplo:– M1 : único monitor que accede a v1 → asegura E.M. ya que será

ininterrumpible (la entrada al monitor de un proceso excluye la entrada deotros).

– Único procesamiento sobre v1 programado en M1.• Diferentes monitores (o instancias de un monitor) para diferentes tareas.

– Mayor Eficiencia (+ Concurrencia)– Mayor Robustez: Modularidad




1.1.2. Estructuración en el acceso a los datos.

• Definición tipos para las operaciones y los datos (T.A.D.).

• Paradigma de Programación Modular:– Módulo: Conjunto de procedimientos relacionados + datos.– Principio de Ocultación de datos: Hacer local al módulo todo lo

que no debe ser visible.

• Ejemplo: Módulo de pila. Resolver:– Interfaz de usuario: procedimientos push y pop.– Representación (p.e. array) sólo accedida mediante interfaz.– Inicialización antes de uso.

• Lenguajes de Programación Dirigida a Objetos→ Clase.




1.2. Sintaxis de los monitores

Estructura de un monitor de nombrename y procedimientosop1,...,opN :

Monitor name;var ... Declaración de variables permanentes

procedure op1 (...);var ... Declaración de variables locales a op1{ ... Código que implementa op1 }... ... ...

procedure opN (...);var ... Declaración de variables locales a opN { ... Código que implementa opN }

begin... Código para inicializar variables permanentes

end.




1.2.1. Protección de los datos en el monitor.

• Ámbito variables permanentes del monitor : Código monitor (procedimientos y cod. inicialización).

• Acceso variables permanentes: sólo dentro de los procedimientos.

• Procedimientos sólo acceden:– Variables permanentes– Variables locales

• Valores variables permanentes se mantienen entre diferentesejecuciones de los procedimientos.

• Comunicación monitor-mundo exterior: A través de los parámetros de los procedimientos.




1.2.2. Procedimientos del Monitor. • Comunes a todos los procesos del sistema.• Nueva llamada proced. → Nuevos valores parámetros y

variables locales.• Sintaxis:

nombremonitor .nombreprocedimiento( parámetros_reales);

1.2.3. Código de inicialización• Ejecución sólo 1 vez: Inicializa vars. Permanentes.• Tras Ejecución: Monitor = objeto pasivo (datos + proceds.)• Única forma ejecutar monitor: llamar proced.




1.3. Exclusión mútua con monitores

• Acceso al monitor en E.M.– Sólo un proceso en un momento dado puede ejecutar un procedimiento

• Subsiguientes llamadas esperan finalización.

–

Violación podría tener efectos caóticos sobre vars.

• Ventajas sobre Semáforos (soluc. no estructurada):– Protección Variables: evita interferencias exteriores– Estructuración acceso: Espera y señalización se programan dentro monitor. Si

el monitor es correcto, lo será cada instancia utilizada por los procesos.– E.M. garantizada automáticamente → No errores.

• Invariante: Define una relación sobre los datos del monitor.

– Se mantiene siempre excepto cuando un procedimiento está ejecutándose.– Se ha de cumplir antes de entrar y después de salir.

– Se ha de reestablecer el invariante en procedimientos antes de devolver elcontrol o suspender el proceso.




1.4. Instanciación de monitores

• Permite declarar diversos monitores con estructura ycomportamiento idénticos (Ej.: planificar varios recursossimilares).

• Declaración tipo monitor:Class Monitor nombre_clase

.... .......

• Instanciación de monitores: monitor1, monitor2: nombreclase;•

Práctica: se permite declarar varias instancias e inclusoconjuntos parametrizados de monitores.• Implementación con procedimientos reentrantes:

– Basta asignar nuevas instancias de las variables globales para cada instancia de un monitor.




2.1. Primitivas de sincronización en monitores

• Sincronización: Facilidad de bloqueo-activación de acuerdoa una condición.

• Propósitos de las instrucciones de sincronización ensemáforos:– Bloqueo-activación– Cuenta (representación condición)

• En monitores:– Sólo Bloqueo-activación– Representación condición mediante datos protegidos del

monitor




2.1. Primitivas de sincronización en monitores (cont.)

• Ejemplo de monitor: Planificador de un único recurso (sem. binario)

monitor recurso;

var ocupado: boolean;noocupado: condicion;

procedure adquirir;{if ocupado then noocupado.wait; ocupado := true}

procedure liberar;{ocupado := false; noocupado.signal;}

beginocupado := false /* valor inicial*/

end;




2.1.1. Semántica de las operaciones

● Wait: "estoy esperando a que algo (condición) ocurra".– Bloquea proceso.

● Signal: "estoy señalando que algo (condición) ha ocurrido".– Reactiva un proceso bloqueado en esa condición.

• Responsabilidad del programador→ que el proceso ejecute: – Wait: cuando algo (condición) no se dé – Signal: Cuando la condición acabe de activarse.




2.1.2. Variables de condición o señales

• Más de una razón para esperar:– representan distintas condiciones– Deben de ser diferenciadas por wait y signal.

• Nuevo tipo de variable:– Variable de condición o señal. Sin valor almacenado (ni V, ni F).– Una variable condición por cada razón de bloqueo.

• Operaciones

Nombre_variable_condición.wait Nombre_variable_condición.signal

• Representación variable condición

– Cola (inicialmente vacía) de procs esperando en condición. Invisiblea procs.

• Más de un proceso puede estar dentro del mismo monitor, aunque sólouno ejecutándose (resto bloqueados en variables condición).




2.1.3. Propiedad FIFO de las colas de condición

• Más de un proc. esperando en condición → – condición.signal reactivará el proc. que lleve más tiempo

esperando.

• Cada proc. en cola obtendrá eventualmente su turno→ Noinanición.

● condición.queue – Función booleana = V → Hay algún proc. esperando en

condición.




2.1.4. Colas de condición con prioridad

• Propiedad FIFO: evita inanición.• Mayor control sobre estrategia de planificación: prioridad del proceso

en espera como nuevo parámetro.

•

Formato: Nombre_var_condición.wait (prioridad:integer);

• Signal reanuda proceso que especificó el valor más bajo de prioridad.• Precaución diseño monitor: Evitar riesgos como la inanición.• Justificación:

– Ningún efecto sobre la lógica del programa: Funcionamientosimilar con/sin colas de prioridad. Sólo mejora características dep.del tiempo.

– Ordenación automática cola: técnica de planificación rápida ysencilla, excepto si la cola es muy larga.

– Almacenamiento requerido por proceso: una palabra




2.1.4. Colas de condición con prioridad (cont.)

Ejemplo: Reloj con alarma. El proc. llamador se retardan unidades detiempo.

monitor despertador;

var ahora: integer; despertar: condicion;

procedure despiertame (n: integer);var alarma: integer;{alarma := ahora + n; while ahora<alarma do despertar.wait (alarma);despertar.signal; /* Por si otro proceso coincide en la alarma */ }

procedure tick;{ahora := ahora + 1; despertar.signal;}

beginahora := 0;end;




2.1.4. Colas de condición con prioridad (cont.)

Ejemplo: Asignación recurso "siguiente trabajo el más corto".

monitor asignador;var libre: boolean; turno: condicion;

procedure petición (tiempo: integer);{if not libre then turno.wait (tiempo); libre:=false;}

procedure liberar;

{libre := true; turno.signal;}

beginlibre:= true;end;




2.2. Efecto de las operaciones de sincr. sobre la E.M. del monitor

• Requisito de reanudación inmediata

– Un Signal deberá ir seguida inmediatamente por la reanudación de un proceso en espera,sin que exista la posibilidad de que intervenga la llamada a un procedimiento de un tercer proceso.

• Única forma de garantizar que procesos en espera puedan adquirir un recurso que

acaba de ser liberado → Evita inanición.

• Propuesta de Hoare

– Un proceso suspendido debido a ejecución de signal, entrará en una cola de suspendidosen Signal. Cada proceso antes de salir del monitor y liberar la E.M., comprueba si hay procesos en esta cola, si los hay, heredarán la E.M. Los procesos suspendidos al ejecutar una operación signal tienen prioridad sobre los que intentan entrar.

• Propuesta de Brinch-Hansen

– Signal sólo como última instrucción del cuerpo.

– Evita cola de suspendidos en signal → + Eficiencia




2.2.1. Problema de Anidación de llamadas en monitores

• Sistema estructurado como colección jerárquica de monitores: procs. de un monitor pueden llamar a otro

• Problema:– Una llamada de monitor anidada se suspende en el último monitor. La

E.M. en el último se abandonará pero no en el monitor desde el quese llama.

–

Los procesos que intenten llamar a procedimientos de cualquier monitor de la cadena se bloquearán.

– Menor concurrencia → Menor rendimiento.




2.2.1.1. Problema de Anidación. Propuestas de solución

a) Prohibir llamadas anidadas.

b) Liberar exclusión mútua en todos los monitores implicados en la cadena y bloquear proceso.–

Una vez señalado, el proceso necesitará readquirir el acceso exclusivo a todos losmonitores.– Requerirá que el invariante del monitor se establezca antes de cualquier llamada que

pueda bloquear.

c) Monitores = herramienta de estructuración para recursos compartidos. E.M. →sólo forma de preservar integridad del recurso.

– Hay casos en los cuales las operaciones de un monitor pueden ejecutarseconcurrentemente sin efectos adversos.

– Definir construcción que permita especificar que ciertas operaciones se podrán ejecutar concurrentemente y la exclusión mútua se liberará.




2.3. Equivalencia entre semáforos y monitores

• Los monitores pueden ser implementados por semáforos.

• Garantizar la E.M.de los cuerpos los procedimientos

– Para cada monitor → Semáforo binario mutex (inic. a 1) para asegurar exclusión mútua entre los cuerpos de procedimientos.

• mutex:bin_sem=1• ENTRADA Proc. → P(mutex)

• SALIDA Proc. → Normalmente V(mutex)




2.3. Equivalencia entre semáforos y monitores (cont.)

Propuesta de Hoare: – Semáforo urgente (inic. a 0) para cola de bloqueados en Signal– Contador procs. esperando enurgente (conturgente, inic. a 0).

• Procesos que invocan un signal ejecutan:if (existen procs. bloqueados en wait) {conturgente ++;

P(urgente) }

• Para liberar procs. bloqueados en signal, antes de liberar laexclusión mútua, cada proceso ejecuta:

if conturgente>0 V(urgente)else V(mutex);




2.3. Equivalencia entre semáforos y monitores (cont.)

• Para cada variable condición del monitor:

– Semáforo semcondición (inic. a 0) para cola de bloqueados en Wait

– Contador de nº procs. esperando condición (contcondición inic. a 0).

condición.wait contcondición + +;if conturgente>0

V(urgente)else V(mutex);

P(semcondición);contcondición - -;

condición.signal conturgente + +;if contcondición>0

{ V(semcondición);P(urgente); }

conturgente - - ;




2.3.1. Equivalencia entre semáforos y monitores. Mejoras

• Salida del cuerpo de un procedimiento sin wait ni signal V(mutex)

– conturgente no ha cambiado.

• Salida cuando signal es la última instrucción del cuerpo:

if contcondición > 0 V(semcondición)(*) else if conturgente>0 V(urgente)else V(mutex);

• No hay otro wait o signal en el cuerpo (*) puede omitirse.

• Propuesta de Brinch-Hansen

– signal última operación del cuerpo conturgente y urgente se omiten– Esta simplificación sugiere que todas las operaciones signal deberían siempre

ser la última operación de un proc. del monitor.




2.3.2. Semáforos v.s. Monitores

• Equivalentes en potencia expresiva.

•

Motivación de uso Monitores: Claridad y fiabilidad.

• Característica que no se puede implementar en semáforos:Suposición FIFO sobre la cola.




2.4. Problemas paradigmáticos resueltos con monitores2.4.1. Productor/consumidor utilizando un buffer circular

program productorconsumidor;

monitor buffercircular;

CONST tamaño=...;VAR b:array [0..tamaño-1] of integer; in, out, n: integer; novacio, nolleno:

condicion;

procedure añadir (v:integer);{if (n==tamaño) nolleno.wait; /* Espera a que no esté lleno*/

b[in] = v; in = (in + 1) % tamaño; n ++; novacio.signal;} procedure tomar(var v:integer);{if (n==0) novacio.wait; /* Espera a que no esté vacío */v = b[out]; out = (out + 1) % tamaño; n --; nolleno.signal;}

{in = out = n = 0}




2.4.1. Productor/consumidor utilizando un buffer circular (cont.)

procedure productor;VAR v: integer;{while (true) {producir(v);añadir(v)}

procedure consumidor;VAR v:integer;{while (true) {tomar(v);consumir(v) }

{ cobegin /* programa principal*/productor; consumidor;

coend; }




2.4.2.Problema de los lectores/escritores sin prioridades (FIFO).

program lectoresescritores;

monitor leerescribir;VAR lectores: integer; escribiendo: boolean; okleer, okescribir: condicion;

procedure comenzarleer;

{if (escribiendo or okescribir.queue) okleer.wait;lectores + +; okleer.signal} procedure finleer; {lectores - -; if (lectores==0) okescribir.signal;}

procedure comenzarescribir;{if (lectores!=0 or escribiendo) okescribir.wait;escribiendo= true }

procedure finescribir;{escribiendo = false; if (okleer.queue) okleer.signal else okescribir.signal }

{lectores =0;escribiendo = false}




2.4.2.Problema de los lectores/escritores sin prioridades (FIFO).cont.

procedure procesolector;{ while (true) {comenzarleer; leerdatos; fin leer;}

procedure procesoescritor;{ while (true) { comenzarescribir; escribirdatos; finescribir }

{cobegin

procesolector; procesolector; ...procesoescritor; procesoescritor; ...

coend; }




2.4.3. Implementación con semáforos del productor/consumidor

• Propuesta de Brinch Hansen(/*signal es la última instrucción*/

program productorconsumidor;CONST tamaño=...;VAR b: array [0..tamaño-1] of integer; in, out, n: integer;

s: semaphore; /para E.M.*/semnovacio, semnolleno: semaphore; /* binarios */contnovacio, contnolleno: integer;

procedure añadir (v:integer);{ P(s); if (n==tamaño) { contnovacio+ +; V(s); P(semnovacio); contnovacio --}

b[in] = v; in := (in + 1) % tamaño; n + +;if contnolleno>0 V(semnolleno) else V(s);}

procedure tomar(var v:integer);{ P(s); if (n==0) {contnolleno + +; V(s); P(semnolleno); contnolleno - -}v := b[out]; out := (out + 1) % tamaño; n := -- ;

if contnovacio>0 V(semnovacio) else V(s); }




2.4.3. Implementación con semáforos del productor/consumidor

procedure productor;var v: integer;{while (true) {producir(v); añadir(v)}

procedure consumidor;var v:integer;{while (true) {tomar(v); consumir(v)}

{in =out=n = 0; s = 1;contnolleno = semnolleno = 0;contnovacio = semnovacio = 0;cobegin

productor;

idd }


Documents

Monitores