Tema 11 Clase 11 - Programacion Concurrente

Vista previa del material en texto

CLASE 11
MODELO DE DESARROLLO DE PROGRAMAS Y PROGRAMACION CONCURRENTE
FAC.DE INGENIERIA - UNJu
Introducción a Concurrencia
PROGRAMACION CONCURRENTE
Trata de las notaciones y técnicas de programac.q se usan p/expresar paralelismo potencial entre tareas 
p/resolver los problemas de comunicación y sincronización entre procesos.
Concurrencia es la capacidad del 
CPU para procesar más de un 
proceso al mismo tiempo
Paralelismo: toma 1único problema, y mediante concurrencia 
llega a 1solución más rápida. A partir del problema inicial, divide 
el problema en fracciones + pequeñas, y luego c/fracción es 
procesada de forma concurrente, aprovechando la capacidad 
del procesador p/resolver el problema
VARIABLES COMPARTIDAS
Es el método + sencillo de comunicación entre los procesos de un progr., el acceso concurrente 
puede hacer q la acción de1proceso interfiera en las acciones de otro de1forma no adecuada.
Problema de los Jardines: 
Se desea controlar el nro.de visitantes a unos jardines. 
La entrada y la salida a los jardines se realiza por 2 puntos q disponen de puertas giratorias. 
Se asocia el proceso P1 a un punto de entrada y el proceso P2 al otro punto de entrada. 
Ambos procesos se ejecutan concurr.y usan 1 única variable p/llevar la cta.del nro de visitantes.
La entrada de un visitante por una de las puertas hace q se ejecute x:=x+1
La salida de un visitante hace que se ejecute x:=x-1
Si ambas instrucciones se realizan como 1 única instrucción HW, no se plantea ningún problema 
En un sistema multiprocesador si se arbitran mecanismos q impiden q varios procesadores 
accedan a la vez a una misma posición de memoria tampoco hay problema.
Pero sí se produce interferencia de 1proceso en el otro la actualización de la variable se realiza 
mediante la ejecución de otras instrucciones + sencillas, se soluciona con 1 REGION CRITICA.
REGIONES CRITICAS
Son bloques de código q al ser declarados como regiones críticas respecto de 1 variable, el 
programador o el compilador introduce mecanismos de sincronización necesarios p/q su 
ejecución se realice en un régimen de exclusión mutua respecto de otras regiones críticas 
declaradas respecto de la misma variable.
Se definen para garantizar la actualización segura a una variable compartida. Si una variable se 
declara como variables compartida (Shared), su acceso solo se puede realizar en regiones 
críticas y por tanto, todos los accesos son realizador en régimen de exclusión mutua.
BLOQUEO MEDIANTE EL USO DE VARIABLES COMPARTIDAS
Implementación del bloqueo a 1sección crítica mediante el uso de 1variable compartida 
indicador o flag. 
(* Exclusión Mutua:Uso de un indicador*)
module Exclusion_Mutua_1;
varflag: boolean;
process P1 
begin
loop
while flag = true do 
(* Espera a q el dispositivo se libere *) 
end; 
flag :=true; 
(* Uso del recurso Sección Crítica *)
flag := false; 
(* resto del proceso *) 
end
end P1;
process P2 
begin
loop
while flag = true do 
(* Espera a que el dispositivo se libere *) 
end; 
flag :=true; 
(* Uso del recurso Sección Crítica *) 
flag := false; 
(* resto del proceso *) 
end
end P2;
begin (* Exclusion_Mutua_1*) 
flag := false; 
cobegin
P1; P2; 
coend
end Exclusion_Mutua_1.
BLOQUEO MEDIANTE EL USO DE VARIABLES COMPARTIDAS
El programa no resuelve el problema de la exclusión mutua ya q al ser la comprobación y la puesta del 
indicador operaciones separadas, puede ocurrir q se entrelace el uso del recurso x ambos procesos.
Solución: usar dos indicadores para resolver el problema de la exclusión mutua
(* Exclusión Mutua:Uso de dos indicadores*)
module Exclusion_Mutua_2;
varflag1,flag2: boolean;
procedure bloqueo(var mi_flag, su_flag: boolean); 
begin
mi_flag := true; (*intención de usar el recurso*) 
while su_flag do ; 
end (* espera a que se libere el recurso *) 
end bloqueo;
procedure desbloqueo(var mi_flag: boolean); 
begin
mi_flag := false; 
end desbloqueo;
process P1 
begin
loop
bloqueo(flag1,flag2); 
(* Uso del recurso Sección Crítica *) 
desbloqueo(flag1); 
(* resto del proceso *) 
end
end P1;
process P2 
begin
loop
bloqueo(flag2,flag1); 
(* Uso del recurso Sección Crítica *) 
desbloqueo(flag2); 
(* resto del proceso *) 
end
end P2;
begin (* Exclusion_Mutua_2*) 
flag1 := FALSE; 
flag2 := FALSE;
cobegin
P1; 
P2; 
coend
end Exclusion_Mutua_2.
BLOQUEO MEDIANTE EL USO DE VARIABLES COMPARTIDAS
Inconvenientes:
• Durante la espera de la liberación del recurso, el proceso permanece ocupado (busy wait). 
• Si ambos procesos realizan la llamada al bloqueo de forma simultánea, c/proceso puede 
poner su propio indicador y comprobar el estado del otro. Ambos ven los indicadores 
contrarios como ocupados y permanecerán a la espera de q el recurso quede liberado, pero 
esto no podrá suceder al no poder entrar ninguno en su sección crítica. Esta acción se llama:
Interbloqueo o deadlock: se produce porque la desactivación del indicador asociado a un 
proceso se produce una vez que se ha completado el acceso a la sección crítica. 
Se puede intentar resolver el problema haciendo q el proceso desactive su propio indicador 
durante la fase de bloqueo siempre q encuentre q el indicador del otro proceso está activado. 
procedure bloqueo(var mi_flag, su_flag: boolean); begin
mi_flag := true; 
while su_flag do 
mi_flag := false; 
mi_flag := true; 
end
end bloqueo;
ALGORITMO DE PETERSON (1981)
Introduce 1var.adicional turno, p/el problema d petición simultánea d acceso a la región crítica. 
(* Exclusión Mutua:Solución de Peterson*)
Module Exclusion_Mutua_P;
var flag1,flag2: boolean; turno: integer;
procedure bloqueo(var mi_flag, su_flag: boolean; 
su_turno:integer); 
begin
mi_flag := true; 
turno := su_turno; 
while su_flag and (turno = su_turno) do ; end
end bloqueo;
procedure desbloqueo(var mi_flag: boolean); 
begin
mi_flag := false; 
end desbloqueo;
process P1 
begin
loop bloqueo(flag1,flag2,2); 
(* Uso del recurso Sección Crítica *) 
desbloqueo(flag1); (* resto del proceso *) 
end
end P1;
process P2 
begin
loop bloqueo(flag2,flag1,1); 
(* Uso del recurso Sección Crítica *) 
desbloqueo(flag2); 
(* resto del proceso *) 
end
end P2;
begin (* Exclusion_Mutua_P*) 
flag1 := FALSE; 
flag2 := FALSE; 
cobegin
P1; P2; 
coend
end Exclusion_Mutua_P.
ALGORITMO DE DEKKER – DIJKSTRA (1968)
También implementa 1var.turno p/establecer la prioridad relativa d2procesos y su actualización 
se realiza en la sección crítica, lo q evita q pueda haber interferencias entre procesos
(* Exclusión Mutua:Solución de Dekker*)
moduleExclusion_Mutua_D;
varflag1,flag2: boolean; turno: integer;
procedure bloqueo(var mi_flag, su_flag: boolean; su_turno: 
integer); begin
mi_flag := true; 
while su_flag do (* otro proceso en la sección crítica *) 
if turno = su_turno then
mi_flag := false; 
while turno =su_turno do ; (* espera q el otro acabe *)
end; 
mi_flag := true; end; 
end; 
end bloqueo
procedure desbloqueo (var mi_flag: boolean; 
su_turno: integer); begin
turno := su_turno; mi_flag := false 
end desbloqueo;
process P1 
begin
loop bloqueo(flag1,flag2,2); 
(* Uso del recurso Sección Crítica *)
desbloqueo(flag1); (* resto proceso*) 
end
end P1;
process P2 
begin
loop
bloqueo(flag2,flag1,1); 
(* Uso del recurso Sección Crítica *) 
desbloqueo(flag2); 
(* resto del proceso *) end
end P2;
begin (* Exclusion_Mutua_P*) 
flag1 := FALSE; flag2 := FALSE; turno := 1; 
cobegin P1; P2; coend
end Exclusion_Mutua_D.0
SEMAFOROS (DIJKSTRA,1968)
Resuelve la mayoría de los problemas de sincronización entre procesos y forma parte del diseño 
de muchos sistemas operativos y de lenguajes de programación concurrentes.
Un semáforo binario es un indicador (S) de condición q registra si un recurso está disponible o no. 
1semáf.binario sólo puede tomar 2valores: 0 y 1. Si el semáf.binario S=1 el recurso está disponible 
y la tarea lo puede usar; si S=0 el recurso no estádisponible y el proceso debe esperar. 
Los semáforos se implementan con una cola de tareas o de condición a la cual se añaden los 
procesos q están en espera del recurso.
Sólo se permiten 3operaciones sobre 1semáforo
• inicializa (S: SemaforoBinario; v: integer)
Poner el valor del semáforo S al valor de v (0 o 1)
• espera (S)
if S = 1 then S := 0
else suspende la tarea q hace la llamada y 
pone en cola de tareas
• señal (S)
if la cola de tareas está vacía then S := 1
else reanudar la primer tarea de la cola de tareas
Transiciones para el Estado de ESPERA
SEMAFOROS – EXCLUSION MUTUA
La operación de espera se usa como procedimiento de bloqueo antes de acceder a 1
sección crítica 
y
la operación señal como procedimiento de desbloqueo. Se usan tantos semáforos como 
clases de secciones críticas se establezcan. El proceso P1 se escribe:
process P1 
begin
loop
espera (S) ; 
Sección Crítica 
señal (S) ;
(* resto del proceso *) 
end
end P1;
SEMAFOROS – SINCRONIZACION
Espera y señal no se usan en un mismo proceso sino q se dan en 2 procesos separados; el q 
ejecuta la operación de espera queda bloqueado hasta q el otro proceso ejecuta la 
operación de señal.
Si un proceso quiere q se le notifique q ha tenido lugar un suceso determinado y q otro proceso 
es capaz de detectar q ha ocurrido dicho suceso; el ej. siguiente muestra como implementar 
una sincronización entre los dos procesos usando un semáforo.
module Sincronización; (* Sincronización con semáforo*)
var sincro: semaforo;
process P1 (* Proceso que espera *) 
begin
.... 
espera(sincro); 
.... 
end P1;
process P2 (* Proceso que señala *) 
begin
.... 
señal(sincro); 
.... 
end P2;
begin (* Sincronización*) 
inicializa(sincro, 0); 
cobegin
P1; 
P2; 
coend
end Sincronizacion.
SEMAFOROS – PROBLEMA PRODUCTOR - CONSUMIDOR
Se tienen 2 procesos P1 y P2; P1 produce datos q consume P2. P1 almacena datos en algún sitio 
hasta q P2 está listo p/usarlos. X ej., P1 genera informac.con destino a 1 impresora y P2 es el 
proceso gestor de la impresora q imprime. P/almacenar los datos se dispone de 1buffer o zona 
de memoria común al productor y al consumidor. Se supone q/p almacenar y tomar datos se 
dispone de las fciones Poner(x) y Tomar(x). P/saber el estado del buffer se usa la fciones Lleno, 
q devuelve TRUE si el buffer está lleno, Vacio q devuelve TRUE si el buffer está vacío. 
(* Problema del Productor-Consumidor: Sin Semáforos*)
module Productor_Consumidor;
var BufferComun: buffer;
process Productor; 
var x: dato; 
begin
loop
produce(x); 
while Lleno do (* espera *) end; 
Poner(x); 
end
end Productor;
process Consumidor; 
var x: dato; 
begin
loop
while
Vacio do (* espera *) 
end; 
Tomar(x); 
Consume(x) 
end
end Consumidor;
begin
cobegin
Productor; 
Consumidor; 
coend end Productor_Consumidor;
SEMAFOROS – PROBLEMA PRODUCTOR - CONSUMIDOR
Inconven: 1.- Poner(x) y Tomar(x) usan el mismo buffer ==> Problema de la exclusión mutua.
2.- Ambos procesos usan una espera ocupada cuando no pueden acceder al buffer
(* Problema del Productor-Consumidor: Con Semáforos*)
module Productor_Consumidor;
var BufferComun: buffer; 
AccesoBuffer, Nolleno, Novacio: semaforo;
process Productor; 
var x: dato; 
begin loop
produce(x); 
espera(AccesoBuffer); 
if Lleno then señal(AccesoBuffer); 
espera(Nolleno); 
espera(AccesoBuffer) 
end; 
Poner(x); señal(AccesoBuffer); 
señal(Novacio) 
end
end Productor;
process Consumidor; 
var x: dato; begin
loop
espera(AccesoBuffer); 
if Vacio then
señal(AccesoBuffer); 
espera(Novacio);
espera(AccesoBuffer) end; 
Tomar(x); 
señal(AccesoBuffer); 
señal(Nolleno); 
Consume(x) 
end
end Consumidor;
begin
inicializa(AccesoBuffer, 1); 
inicializa(Nolleno, 1); 
inicializa(Novacio, 0); 
cobegin
Productor; Consumidor; coend
end Productor_Consumidor;
SEMAFOROS PARA N RECURSOS DISPONIBLES
El semáforo se inicializa con el nro.total de recursos disponibles (N) y las operaciones de 
espera y señal se diseñan de modo q se impida el acceso al recurso protegido x el semáforo 
cuando el valor de éste es menor o igual que cero. C/vez q se solicita y obtiene 1recurso, el 
semáforo se decrementa y se incrementa cuando 1de ellos se libera. Si la operación de 
espera se ejecuta cuando el semáforo tiene 1valor menor que 1, el proceso debe quedar en 
espera de que la ejecución de 1operación señal libere alguno de los recursos.
• inicializa (S: SemaforoBinario; v: integer) Pone el valor del semáforo S al valor de v (N)
numero_suspendidos := 0
• espera (S)
if S > 0 then S := S-1
else numero_suspendidos:=numero_suspendidos+1;
suspende la tarea q hace la llamada y poner en la cola de tareas
• señal (S)
if numero_suspendidos > 0 then
numero_suspendidos := numero_suspendidos - 1
pasa al estado listo un proceso suspendido
else S := S + 1
MONITOR
Es un conj.de procedim.q proporciona el acceso con exclusión mutua a un recurso o conj.de
recursos compartidos por 1grupo de procesos. Los procedimientos van encapsulados dentro 
de 1 módulo q tiene la propiedad especial de q sólo un proceso puede estar activo c/vez q se 
ejecuta un proced.del monitor. 
El monitor se puede ver como una valla alrededor del recurso de modo que los procesos que 
quieran utilizarlo deben entrar dentro de la valla, pero en la forma que impone el monitor. 
Muchos procesos pueden querer entrar en distintos instantes de tiempo, pero sólo se permite q 
entre un proceso c/vez, debiéndose esperar a que salga el q está dentro antes de q otro 
pueda entrar. 
La exclusión mutua está implícita: la única acción q debe realizar el programador del proceso 
q usa un recurso es invocar una entrada del monitor. Si el monitor se ha codificado 
correctamente NO puede ser utilizado incorrectamente x un programa de aplicación q desee 
usar el recurso.
Los monitores NO proporcionan x si mismos 1 mecanismo p/sincronizar tareas y x ello su 
construcción se completa usando señales o variable de condición p/sincronizar los procesos.
MONITOR - SINTAXIS
monitor: nombre_monitor;
declaración de los tipos y procedimientos q se importan y exportan declaración de las 
variables locales del monitor y de las variables de condición
procedure Prc1(..); 
begin
... 
end;
procedure Prc2(..); 
begin
... 
end; .... 
procedure Prcm(..); 
begin
... 
end;
begin inicialización del monitor end.
….
export Prc1, Prc2,....,Prcn
MENSAJES
Proporcionan 1solución al problema de la concurrencia de procesos q integra la sincronizac. y 
la comunicación entre ellos y resulta adecuado tanto p/sist.centralizados como distribuidos. 
La comunicación mediante mensajes necesita siempre de un proceso emisor y de 1receptor 
así como de informac.q intercambiarse. X ello, las operaciones básicas p/la comunicación 
mediante mensajes q proporciona todo sist.operativo son: enviar(mensaje) y recibir(mensaje).
Las acciones de transmisión de informac.y de sincronización se ven como activid.inseparables.
La comunicación x mensajes requiere q se establezca un enlace entre el receptor y el emisor, 
la forma del cual puede variar grandemente de sist.a sist. Su implementación depende de:
1- El modo de nombrar los procesos.
2- El modelo de sincronización.
3- Almacenamiento y estructura del mensaje.
MODELOS DE SINCRONIZACIÓN 
Las diferencias en los modelos usados p/la sincronización de los procesos se debe a las 
distintas formas que puede adoptar la operación de envío del mensaje:
a) Síncrona: El proceso q envía sólo prosigue su tarea cuando el mensaje ha sido recibido.
b) Asíncrona: El proceso q envía un mensaje sigue su ejecución sin preocuparse si el mensaje 
se recibe o no.
c) Invocación remota: El proceso q envía el mensaje sólo prosigue su ejecución cuando ha 
recibido una respuesta del receptor.
INTERBLOQUEO
Consiste en q 2 o + procesos entran en 1estado q imposibilita a cualquiera de ellos salir del 
estado en q se encuentra. A dicha situación se llegaxq c/proceso adquiere algún recurso 
necesario p/su operación a la vez q espera a que se liberen otros recursos que retienen otros 
procesos, llegándose a 1 situación que hace imposible q ninguno de ellos pueda continuar. 
• Concurrencia VS Paralelismo: goo.gl/1M9jsX
• Sincronizac.basada en memoria compartida: Reg.críticas goo.gl/F3WRGk
• Programación Concurrente UBA http://materias.fi.uba.ar/sweb/1c-
2006/concurrencia.pdf
BIBLIOGRAFÍA RECOMENDADA