Tema_9_Clase_10_-_Programacion_Concurrente

Vista previa del material en texto

CLASE 10
MODELO DE DESARROLLO DE PROGRAMAS Y PROGRAMACION 
CONCURRENTE
FAC.DE INGENIERIA - UNJu
Introducción a Concurrencia
PROGRAMACION CONCURRENTE
Rama de la informát.q 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ápido. 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 programa, pero el acceso concurrente 
puede hacer q la acción de un proceso interfiera en las acciones de otro de una forma 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 puede realizar 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 concurrentem.y usan 1 única variable x 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 realizaran como 1 única instrucción HW, no se plantearía 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 habría problema.
Pero sí se produce interferencia de un proceso en el otro si la actualización de la variable se realiza 
mediante la ejecución de otras instrucciones más sencillas, lo cual 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 
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 que 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 verán los indicadores contrarios como 
ocupados y permanecerán a la espera de que 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 que el proceso desactive su propio indicador durante la 
fase de bloqueo siempre que encuentre que 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 1 var. adicional turno, útil cuando se produce 1 problema de petición simultánea de 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 1 variable turno p/establecer la prioridad relativa de los 2 procesos y su 
actualización se realiza en la sección crítica, lo q evita q pueda haber interferencias entre los 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.
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 que registra si un recurso está disponible o no. Un 
semáforo binario sólopuede tomar dos valores: 0 y 1. Si, para un semáforo binario, S = 1 entonces el recurso 
está disponible y la tarea lo puede utilizar; 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 
que están en espera del recurso.
Sólo se permiten tres operaciones sobre un semá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 que hace la llamada y pone 
en cola de tareas
• señal (S)
if la cola de tareas está vacía then S := 1
else reanuda 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.
(* Sincronización con semáforo*)
module Sincronización;
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 unos datos que consume P2. P1 almacena datos en algún sitio 
hasta que P2 está listo p/usarlos. X ej., P1 genera información con destino a 1 impresora y P2 es el proceso 
gestor de la impresora q se encarga de imprimirlos. Para almacenar los datos se dispone de un buffer o 
zona de memoria común al productor y al consumidor. Se supone que para almacenar y tomar datos se 
dispone de las funciones Poner(x) y Tomar(x). Para saber el estado del buffer se usan las funciones Lleno, 
q devuelve el TRUE si el buffer está lleno, y 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
Inconvenientes: 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 número total de recursos disponibles (N) y las operaciones de espera y 
señal se diseñan de modo que se impida el acceso al recurso protegido por el semáforo cuando el valor 
de éste es menor o igual que cero. Cada vez que se solicita y obtiene un recurso, el semáforo se 
decrementa y se incrementa cuando que uno de ellos se libera. Si la operación de espera se ejecuta 
cuando el semáforo tiene un valor menor que 1, el proceso debe quedar en espera de que la ejecución 
de una operació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 que entre un proceso cada 
vez, debiéndose esperar a que salga el que está dentro antes de que 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 por un programa de aplicación que desee usar el recurso.
Los monitores no proporcionan por si mismos un mecanismo para la sincronización de tareas y por ello su 
construcción debe completarse usando señales o variable de condición para sincronizar los procesos.
Florencia
Resaltado
Florencia
Resaltado
Florencia
Resaltado
Florencia
Resaltado
Florencia
Resaltado
MONITOR - SINTAXIS
monitor: nombre_monitor;
declaración de los tipos y procedimientos que 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 una solución al problema de la concurrencia de procesos que integra la sincronización y la 
comunicación entre ellos y resulta adecuado tanto para sistemas centralizados como distribuidos. 
La comunicación mediante mensajes necesita siempre de un proceso emisor y de uno receptor así como 
de información que intercambiarse. Por ello, las operaciones básicas para comunicación mediante 
mensajes que proporciona todo sistema operativo son: enviar(mensaje) y recibir(mensaje).
Las acciones de transmisión de información y de sincronización se ven como actividades inseparables.
La comunicación por mensajes requiere que se establezca un enlace entre el receptor y el emisor, la 
forma del cual puede variar grandemente de sistema a sistema. Su implementación depende de:
1- El modo de nombrar los procesos.
2- El modelo de sincronización.
3- Almacenamiento y estructura del mensaje.
Florencia
Resaltado
MODELOS DE SINCRONIZACIÓN 
Las diferencias en los modelos usados para 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 procesoque envía sólo prosigue su tarea cuando el mensaje ha sido recibido.
b) Asíncrona. El proceso que envía un mensaje sigue su ejecución sin preocuparse si el mensaje se recibe 
o no.
c) Invocación remota. El proceso que envía el mensaje sólo prosigue su ejecución cuando ha recibido 
una respuesta del receptor.
Florencia
Resaltado
Florencia
Resaltado
INTERBLOQUEO
Consiste en q dos o más procesos entran en un estado q imposibilita a cualquiera de ellos salir del estado 
en que se encuentra. A dicha situación se llega porque cada 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 que 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