Upload
sula12010
View
24
Download
0
Embed Size (px)
Citation preview
Sistemas de Tiempo Real Marga Marcos, © 2001-2006
Índice:
» Concepto de proceso» Ejecución concurrente» Representación de procesos» Comunicación y sincronización basadas en
variables compartidas» Comunicación y sincronización basadas en
mensajes
Tema 2: Nociones de Programación Concurrente
29
Sistemas de Tiempo Real Marga Marcos, © 2001-2006
Tema 2: Nociones de Programación Concurrente
Comunicación y sincronización• Normalmente los procesos no son independientes.
Generalmente cooperan (para un fin común) o compiten(por recursos)
• Es necesario comunicarlos y sincronizarlos» dos procesos se comunican cuando se transfieren
información» dos procesos se sincronizan cuando se imponen
restricciones en el orden en que ejecutan sus acciones• Los dos conceptos están relacionados• Formas de abordar el problema:
» variables compartidas» mensajes
30
Sistemas de Tiempo Real Marga Marcos, © 2001-2006
Tema 2: Nociones de Programación Concurrente
Comunicación y sincronización con variables compartidas
• en un sistema monoprocesador la forma más directa de comunicación entre dos ó más procesos es compartirvariables
• el acceso incontrolado a variables compartidas puede producir resultados anómalos
» se dice que se da una condición de carrera cuando el resultado de una ejecución depende del orden en que se ejecutan las acciones de dos ó más procesos
» estas situaciones se deben evitar
31
Sistemas de Tiempo Real Marga Marcos, © 2001-2006
Tema 2: Nociones de Programación Concurrente
Comunicación y sincronización con variables compartidas» ejemplo: X:=X+1
• no es una operación indivisible» cargar valor de X en un registro» incrementar el valor del registro en 1» almacenar el valor de registro en X
» el resultado final puede ser 1 o 2 (condición de carrera)
P1 P2
Contador=0
Incrementar contadorLDA contadorINCSTA contador
Incrementar contadorLDA contadorINCSTA contador
32
Sistemas de Tiempo Real Marga Marcos, © 2001-2006
Tema 2: Nociones de Programación Concurrente
Comunicación y sincronización con variables compartidas» exclusión mutua
• el resultado depende de las velocidades relativas de los dos procesos
• para evitar condiciones de carrera hay que asegurar que las operaciones sobre variables compartidas se ejecutan de forma atómica (indivisible)
• una secuencia de instrucciones que se ejecuta de forma indivisible se denomina sección crítica
• la forma de sincronización que se utiliza para proteger una sección crítica se denomina exclusión mutua
33
Sistemas de Tiempo Real Marga Marcos, © 2001-2006
Tema 2: Nociones de Programación Concurrente
Comunicación y sincronización con variables compartidas» sincronización condicional
• cuando una acción de un proceso debe esperar a que otro proceso haya ejecutado otras acciones o se encuentre en un determinado estado, se necesita sincronización condicional
• ejemplo: productor/consumidor en tampón limitado
• no se debe hacer put cuando el tampón está lleno• no se debe hacer get cuando el tampón está vacío• acceso al tampón en exclusión mutua
productor consumidortampónput get
34
Sistemas de Tiempo Real Marga Marcos, © 2001-2006
Tema 2: Nociones de Programación Concurrente
Comunicación y sincronización con variables compartidas» Mecanismos de sincronización:
• espera activa• semáforos• regiones críticas condicionales• monitores• sincronización en C/POSIX
35
Sistemas de Tiempo Real Marga Marcos, © 2001-2006
Tema 2: Nociones de Programación Concurrente
Mecanismos de sincronización: espera activa. Utiliza un indicador compartido
process P1; (* proceso que espera *)...while flag=down donullend;...end P1;process P2; (* proceso que señala *)...flag:=up;...end P2;
sincronización condicional
process P
loop
protocolo de entradasección críticaprotocolo de salidasección no crítica
end;
end P;exclusión mutua
36
Sistemas de Tiempo Real Marga Marcos, © 2001-2006
Tema 2: Nociones de Programación Concurrente
Mecanismos de sincronización: espera activa. Exclusión mutua. 1ª aproximación: 2 indicadores
process P1; loopflag1:=up;(* anuncia que intenta entrar *)while flag2=up donull(* espera ocupada si el otro proceso estádentro de su sección crítica *)end;<sección crítica>(* protocolo de salida *)flag1:=down;<sección no crítica>endend P1;
process P2; loopflag2:=up;(* anuncia que intenta entrar *)while flag1=up donull(* espera ocupada si el otro proceso estádentro de su sección crítica *)end;<sección crítica>(* protocolo de salida *)flag2:=down;<sección no crítica>endend P2; 37
Sistemas de Tiempo Real Marga Marcos, © 2001-2006
Tema 2: Nociones de Programación Concurrente
• ejecución anómalaP1: flag1=upP2: flag2=upP2: consulta flag1P2: como está up entra en espera activaP1: consulta flag2P1: como está up entra en espera activa
• bloqueo activo:» ambos procesos quedan bloqueados en una espera activa
(livelock)
Mecanismos de sincronización: espera activa. Exclusión mutua. 1ª aproximación: 2 indicadores
38
Sistemas de Tiempo Real Marga Marcos, © 2001-2006
Tema 2: Nociones de Programación Concurrente
Mecanismos de sincronización: espera activa. Exclusión mutua. 2ª aproximaciónprocess P1; loopwhile flag2=up donull(* espera ocupada si el otro proceso estádentro de su sección crítica *)end;flag1:=up;(* anuncia que entra en su SC *)<sección crítica>(* protocolo de salida *)flag1:=down;<sección no crítica>endend P1;
process P2; loopwhile flag1=up donull(* espera ocupada si el otro proceso estádentro de su sección crítica *)end;flag2:=up;(* anuncia que entra en su SC *)<sección crítica>(* protocolo de salida *)flag2:=down;<sección no crítica>endend P2; 39
Sistemas de Tiempo Real Marga Marcos, © 2001-2006
Tema 2: Nociones de Programación Concurrente
• ejecución anómalasupongamos que P1 y P2 están en sus secciones no críticasflag1=flag2=downP1: consulta flag2 (está down)P2: consulta flag1(está down)P2: flag2=upP2: entra en su SCP1: flag1=upP1: entra en su SC
• ambos procesos están ejecutando su SC
Mecanismos de sincronización: espera activa. Exclusión mutua. 2ª aproximación
40
Sistemas de Tiempo Real Marga Marcos, © 2001-2006
Tema 2: Nociones de Programación Concurrente
Mecanismos de sincronización: espera activa. Exclusión mutua. 3ª aproximación
process P1; loopwhile turno=2 donullend;<sección crítica>turno:=2;<sección no crítica>endend P1;
process P2; loopwhile turno=1 donullend;<sección crítica>turno:=1;<sección no crítica>endend P2;
41
Sistemas de Tiempo Real Marga Marcos, © 2001-2006
Tema 2: Nociones de Programación Concurrente
Mecanismos de sincronización: espera activa. Exclusión mutua.
process P1; loopflag1=up;(* anuncia que entra en su SC *)turno=2;(* da prioridad al otro proceso *)while flag2=up and turno=2 donullend;<sección crítica>flag1:=down;<sección no crítica>endend P1;
process P2; loopflag2=up;(* anuncia que entra en su SC *)turno=1;(* da prioridad al otro proceso *)while flag1=up and turno=1 donullend;<sección crítica>flag2:=down;<sección no crítica>endend P2; 42
Sistemas de Tiempo Real Marga Marcos, © 2001-2006
Tema 2: Nociones de Programación Concurrente
• primera posibilidad: P1 antes que P2P1: turno=2P1: consulta turno y entra en lazo de esperaP2: turno=1P2: consulta turno y entra en lazo de esperaP1: sale del lazo y entra en su SC
• segunda posibilidad: P2 antes que P1P2: turno=1P2: consulta turno y entra en lazo de esperaP1: turno=2P1: consulta turno y entra en lazo de esperaP2: sale del lazo y entra en su SC
Mecanismos de sincronización: espera activa. Exclusión mutua
43
Sistemas de Tiempo Real Marga Marcos, © 2001-2006
Tema 2: Nociones de Programación Concurrente
• tercera posibilidad: P1 antes que P2P1: turno=2P2: turno=1P2: consulta turno y entra en lazo de esperaP1: entra en su SC
• cuarta posibilidad: P2 antes que P1P2: turno=1P1: turno=2P1: consulta turno y entra en lazo de esperaP2: entra en su SC
Mecanismos de sincronización: espera activa. Exclusión mutua
44
Sistemas de Tiempo Real Marga Marcos, © 2001-2006
Tema 2: Nociones de Programación Concurrente
• una forma de realizar la exclusión mutua es utilizar un indicador compartido
» se puede hacer si el acceso al indicador es atómico (p.e. instrucción test-and-set)
• los protocolos son difíciles de diseñar, entender y probar• son ineficientes y no permiten gestionar colas de espera• una tarea poco fiable que haga mal uso de una variable
compartida puede corromper el programa completo
Mecanismos de sincronización: espera activa
while test_and_set(flag) loopnull;end loop;-- sección críticaflag:=false;
45
Sistemas de Tiempo Real Marga Marcos, © 2001-2006
Tema 2: Nociones de Programación Concurrente
Comunicación y sincronización con variables compartidas» Mecanismos de sincronización:
• espera activa• semáforos• regiones críticas condicionales• monitores• sincronización en C/POSIX
46
Sistemas de Tiempo Real Marga Marcos, © 2001-2006
Tema 2: Nociones de Programación Concurrente
• Un semáforo es una variable que toma valores enteros no negativos
• Además de asignarle un valor inicial, sobre él sólo se pueden realizar dos operaciones:
» wait(S) si S>0 decrementa su valor en 1si S≤ 0, suspende el proceso hasta que S>0
» signal(S) si S=0 y existe algún proceso en la cola lo despiertasi no, incrementa S en 1
• las operaciones wait y signal son indivisibles• otros nombres para estas operaciones:
» P/V (passieren / vrijmachen)» Secure / Release» Down / Up
Mecanismos de sincronización: semáforos
47
Sistemas de Tiempo Real Marga Marcos, © 2001-2006
var sin_con:semaphore;(* inicialmente 0 *)process P1; (* proceso que espera *)S1Await(sin_con)S1Bend P1;process P2;(* proceso que señala *)S2Asignal(sin_con);S2Bend P2;
Tema 2: Nociones de Programación Concurrente
sincronización condicional
• S1B no se ejecuta hasta que P2 avisa que se cumplela condición
48
Mecanismos de sincronización: semáforos
Sistemas de Tiempo Real Marga Marcos, © 2001-2006
process P2; loopwait(mutex);<sección crítica>signal(mutex);<sección no crítica>end;end P2;
Tema 2: Nociones de Programación Concurrente
exclusión mutua
var mutex:semaphore;(* inicialmente 1 *)process P1; loopwait(mutex);<sección crítica>signal(mutex);<sección no crítica>end;end P1;
mutex es un semáfor binario
Mecanismos de sincronización: semáforos
49
Sistemas de Tiempo Real Marga Marcos, © 2001-2006
Tema 2: Nociones de Programación Concurrente
Procesos suspendidoswait(S):if S>0 thens:=s-1elsenum_suspendidos=num_suspendidos+1;suspender proceso;
signal(S):if num_suspendidos>0 thennum_suspendidos:=num_suspendidos-1;pasar un proceso a estado ejecutable;elses:=s+1;
Mecanismos de sincronización: semáforos
50
Sistemas de Tiempo Real Marga Marcos, © 2001-2006
Tema 2: Nociones de Programación Concurrente
51
inexistente
creado
ejecutable
iniciadoEsperandoinicio hijo
completado
esperando terminación pupilo
suspendido
Sistemas de Tiempo Real Marga Marcos, © 2001-2006
Tema 2: Nociones de Programación Concurrente
» es fácil cometer errores
• un solo wait o signal mal colocado puede hace funcionar incorrectamente al programa
• es mejor utilizar mecanismos más abstractos y fiables» regiones críticas» monitores» objetos protegidos
Problemas de los semáforosMecanismos de sincronización: semáforos
52
Sistemas de Tiempo Real Marga Marcos, © 2001-2006
Tema 2: Nociones de Programación Concurrente
» Vivacidad• las propiedades de vivacidad son del tipo “alguna vez
ocurrirá algo”. Los mecanismos de sincronización basados en semáforos pueden originar problemas de vivacidad
» interbloqueo (deadlock). Dos o mas procesos están suspendidos esperando una condición producida en otro proceso de forma circular
» bloque “vivo” (livelock). Dos o mas procesos se ejecutan sin realizar ningún progreso (no consiguen recursos)
» inanición (starvation). Los procesos se ejecutan pero algunos no consiguen el recurso nunca
Mecanismos de sincronización: semáforos
53
Sistemas de Tiempo Real Marga Marcos, © 2001-2006
Tema 2: Nociones de Programación Concurrente
Si los procesos acceden al recurso en el mismo orden no hay problema
Proceso P1
wait(S1);wait(S2);...signal(S2);signal(S1);
Mecanismos de sincronización: semáforos
54
Proceso P2
wait(S1);wait(S2);...signal(S2);signal(S1);
Sistemas de Tiempo Real Marga Marcos, © 2001-2006
Tema 2: Nociones de Programación Concurrente
Los procesos acceden en orden inverso: Interbloqueo
Proceso P1
wait(S1);wait(S2);...signal(S2);signal(S1);
Mecanismos de sincronización: semáforos
55
Proceso P2
wait(S2);wait(S1);...signal(S1);signal(S2);
Sistemas de Tiempo Real Marga Marcos, © 2001-2006
Tema 2: Nociones de Programación Concurrente
Comunicación y sincronización con variables compartidas» Mecanismos de sincronización:
• espera activa• semáforos• regiones críticas condicionales• monitores• sincronización en C/POSIX
56
Sistemas de Tiempo Real Marga Marcos, © 2001-2006
Tema 2: Nociones de Programación Concurrente
• Una región crítica es una secuencia de instrucciones que se ejecuta en exclusión mutua
» el compilador produce el código de bajo nivel necesario» identifica a la variable compartida a la que se accede
• La sincronización condicional se consigue mediante guardas
» sólo se puede entrar en la región crítica cuando la guarda es verdadera
Mecanismos de sincronización: Regiones críticas condicionales
57
V: shared T;
region V when condición do...end region;
Sistemas de Tiempo Real Marga Marcos, © 2001-2006
Tema 2: Nociones de Programación Concurrente
» implementación complicada
• las guardas de los procesos suspendidos en regiones que contengan la misma variable deben ser evaluadas cada vez que se libere una región que contiene esa var
• es decir, los procesos suspendidos deben pasar a ejecutables y evaluar su guarda
• potencialmente muchos cambios de contexto• una mejor solución son los monitores
Problemas de las regiones críticasMecanismos de sincronización: Regiones Críticas Condicionales
58
Sistemas de Tiempo Real Marga Marcos, © 2001-2006
Tema 2: Nociones de Programación Concurrente
Comunicación y sincronización con variables compartidas» Mecanismos de sincronización:
• espera activa• semáforos• regiones críticas condicionales• monitores• sincronización en C/POSIX
59
Sistemas de Tiempo Real Marga Marcos, © 2001-2006
Tema 2: Nociones de Programación Concurrente
• un monitor es un módulo que agrupa datos y operaciones sobre ellos
» las operaciones (procedimientos) se ejecutan en exclusión mutua
» el compilador produce el código de bajo nivel necesario• la sincronización condicional se realiza mediante variables
de condición» dos operaciones: signal y wait
• wait: el proceso se suspende (siempre) y se pone en una cola asociada a la condición
• signal: reanuda el primer proceso que espera en la cola. Si no hay ninguno, no tiene efecto
» un proceso que espera una condición libera el monitor
Mecanismos de sincronización: Monitores
60
Sistemas de Tiempo Real Marga Marcos, © 2001-2006
Tema 2: Nociones de Programación Concurrente
Mecanismos de sincronización: Monitores
61
Monitor buffer;export append, take;var (* declaración de variables necesarias *)
procedure append (I: integer);...end;
procedure take (var I:integer);...end;begin
(* inicio variables del monitor *)end;
Sistemas de Tiempo Real Marga Marcos, © 2001-2006
Tema 2: Nociones de Programación Concurrente
Mecanismos de sincronización: Monitores
62
Monitor buffer;export append, take;const size = 32;var buf : array[0...size-1] of integer;
top, base : 0..size-1;SpaceAvailable, ItemAvailable : conditionNumberInBuffer : integer;
procedure append (I: integer);beginif NumberInBuffer = size thenwait(SpaceAvailable);
buf[top] := I;NumberInBuffer := NumberInBuffer+1;top := (top+1) mod size;signal(ItemAvailable)
end append;
Sistemas de Tiempo Real Marga Marcos, © 2001-2006
Tema 2: Nociones de Programación Concurrente
Mecanismos de sincronización: Monitores
63
procedure take (var I: integer);beginif NumberInBuffer = 0 thenwait(ItemAvailable);I := buf[base];base := (base+1) mod size;NumberInBuffer := NumberInBuffer-1;signal(SpaceAvailable)
end take;
begin (* inicialización *)NumberInBuffer := 0;top := 0;base := 0end;
Sistemas de Tiempo Real Marga Marcos, © 2001-2006
Tema 2: Nociones de Programación Concurrente
» las variables de condición son mecanismos de bajo nivel
» la semántica de signal presenta problemas:• cuando un proceso ejecuta signal puede haber dos procesos
activos en el monitor• hay varias formas de evitar que se viole la exclusión mutua
» signal última instrucción del subprograma» forzar salida del monitor al ejecutar signal» suspender al proceso que ejecuta signal si se reanuda otro
proceso
Problemas de los MonitoresMecanismos de sincronización: Monitores
64