PDF de programación - Tema 2. Monitores

Contenidos
(cid:132) El problema de la sección crítica
(cid:132) Semáforos
(cid:132) Regiones críticas
(cid:132) Monitores

Bibliografía

(cid:132) Programación Concurrente

J. Palma, C. Garrido, F. Sánchez, A. Quesada, 2003

(cid:132)

(cid:132) Capítulo 6

(cid:132) Concurrent Programming

(cid:132) A. Burns, G. Davies. Addison-Wesley, 1993
(cid:132) Capítulo 7

(cid:132) Principles of Concurrent and Distributed Programming

(cid:132) M. Ben-Ari. Prentice Hall, 1990
(cid:132) Capítulo 5

(cid:132) Sistemas Operativos

(cid:132) A. Silberschatz, P. Galvin. Addison-Wesley, 1999
(cid:132) Capítulo 6

© Alexis Quesada Arencibia

ProgramaciónConcurrente

1

© Alexis Quesada Arencibia

ProgramaciónConcurrente

2

Monitor
(cid:132) Tipo de datos

(cid:132) Estructuras de datos
(cid:132) Conjunto de operaciones asociadas a tales

estructuras
+
(cid:132) Exclusión mutua
(cid:132) Sincronización (variables condición)

Monitor

monitor nombre_monitor;

{código del procedimiento}

var variables locales;
export procedimientos exportados;
procedure P1(parametros)
var variables locales;
begin
end;
...
procedure PN(parametros)
var variables locales;
begin
end;
{código de inicialización}

{código del procedimiento}

begin
end;

© Alexis Quesada Arencibia

ProgramaciónConcurrente

3

© Alexis Quesada Arencibia

ProgramaciónConcurrente

4

Variables condición
(cid:132) Declaración

(cid:132) var x: condition;

(cid:132) Operaciones

(cid:132) delay(x);
(cid:132) resume(x);
(cid:132) empty(x);

Variables condición
(cid:132) ¿ Qué ocurre cuando un proceso P

realiza una operación resumesobre
una variable condición x y existe un
proceso suspendido Q asociado a dicha
variable?

© Alexis Quesada Arencibia

ProgramaciónConcurrente

5

© Alexis Quesada Arencibia

ProgramaciónConcurrente

6

1

Semántica de la operación
resume
(cid:132) Desbloquear y continuar

(cid:132) Lenguaje Mesa
(cid:132) Retorno forzado

(cid:132) Concurrent Pascal

(cid:132) Desbloquear y esperar

(cid:132) Modula-2, Concurrent Euclid

(cid:132) Desbloquear y espera urgente

(cid:132) Pascal-FC, Pascal Plus

Variables condición
(cid:132) Si varios procesos están suspendidos

por la condición x y algún proceso
ejecuta x.signal, ¿ qué proceso se
reanuda?

© Alexis Quesada Arencibia

ProgramaciónConcurrente

7

© Alexis Quesada Arencibia

ProgramaciónConcurrente

8

Monitor con variables condición

colas asociadas a las
variables condición x e y

x
y

datos compartidos

cola de ingreso

...

operaciones

código de
inicialización

Ejercicios
(cid:132) En un sistema concurrente existen dos tipos de
procesos, A y B, que compiten por utilizar cierto
recurso. Al recurso se accede mediante la rutina de
solicitarlo, esperar hasta que se pueda usar, usarlo y
luego liberarlo. En cualquier momento puede haber
un máximo de N procesos de cualquier tipo usando el
recurso (N es constante). Por otro lado, para que un
proceso de tipo A pueda entrar a emplear el recurso,
debe haber al menos el doble de procesos de tipo B
que procesos de tipo A dentro del recurso. Diseñe un
algoritmo que cumpla con estas reglas de
funcionamiento empleando regiones críticas

© Alexis Quesada Arencibia

ProgramaciónConcurrente

9

© Alexis Quesada Arencibia

ProgramaciónConcurrente

10

Ejercicios

(cid:132) Supongamos dos operaciones: pedir_memoria(cantidad) y

dejar_memoria(cantidad). Cuando un proceso pide memoria, se
bloquea hasta que haya la cantidad pedida de páginas libres, una vez
que ocurre las toma. Un proceso devuelve las páginas llamando a
dejar_memoria. Implementar dichas operaciones usando RCC en los
siguientes supuestos:

(cid:132)

Implementar la sincronización sin establecer ninguna política de quién
recibe primero.

(cid:132) Modificar lo anterior para que el trabajo que pide menos memoria sea el

primero.

salir o ser atendido.

(cid:132) Cambiar la política anterior para que el primero en llegar sea el primero en

(cid:132) Suponer que pedir y dejar devuelven páginas contiguas. Es decir, si un

proceso reclama dos páginas, se retrasa hasta que haya dos páginas
adyacentes disponibles. Desarrollar implementaciones de esa versión de
pedir_memira y dejar_memoria. Elegir una representación del estado de
páginas de memoria.

© Alexis Quesada Arencibia

ProgramaciónConcurrente

11

2