PDF de programación - Sincronización y Comunicación

3

Sincronización y
comunicación
• El Problema de la Sección
Crítica.
• Soluciones con:
– Espera ocupada.
– Soporte hardware a la
sincronización
– Soluciones con
bloqueo: Semáforos.
• Paso de mensajes.

SOI

1

Procesos
Procesos
independientes
independientes

Hasta ahora hemos hablado de procesos
como entidades independientes:

No comparten estado (unos aislados de
los otros)
Su ejecución es determinista = la
ejecución del mismo programa con los
mismos datos produce los mismos
resultados.
Cada proceso puede avanzar a un ritmo
arbitrario.

SOI

2

Procesos cooperantes
Procesos cooperantes

En este tema hablaremos de
procesos/hebras que cooperan:

Comparten estado, normalmente
mediante variables compartidas
entre los diferentes
procesos/hebras.
Ejecución no determinista o difícil
de reproducir, dado que esta
sometida a condiciones de carrera.

SOI

3

Uso de procesos
Uso de procesos
cooperantes
cooperantes

Los procesos que cooperan se pueden
utilizar para:

Ganar velocidad, solapando actividades
o realizando trabajo en paralelo.
Compartir información entre trabajos.
Estructurar mejor una aplicación
(recordar Argumento de la simplicidad
visto en Tema 1).

SOI

4

Concurrencia y
Concurrencia y
paralelismo
paralelismo

El paralelismo de una aplicación multi-
procesador es el grado real de ejecución
paralela alcanzado.

Está limitado por el nº de procesadores
disponibles para la aplicación.

La concurrencia de una aplicación es el
máximo grado de paralelismo alcanzable
con un “número ilimitado” de procesadores.
Depende de como está escrita la aplicación y del
número de hebras de control que pueden
ejecutarse simultáneamente.

SOI

5

Memoria compartida
Memoria compartida

En el tema, nos moveremos en el
paradigma de memoria compartida – dos
ó más procesos comparten memoria.

Procesos independientes

Espacio de
direcciones

del

Proceso 2

Espacio de
direcciones

del

Proceso 1

Espacio de direcciones

común a P1 y P2

Aplicación multihebrada

SOI

6

Cómo se puede compartir
Cómo se puede compartir

Procesos independientes – El SO suministra
medios para compartir memoria:
Unix – IPC shared memory (shmget(), ...)
Windows y Unix – archivos proyectados en
memoria.
Aplicaciones multihebradas – las hebras de
una aplicación comparten memoria de forma
natural, pues comparten el mismo espacio
de direcciones.

SOI

7

Condición de carrera
Condición de carrera

Se produce una condición de carrera (race
condition) cuando el resultado de la
ejecución de dos o más procesos, que
comparten variables comunes, depende de
la velocidad relativa a la que cada proceso
se ejecuta, es decir, del orden en el que se
ejecutan las instrucciones.
Para muestra, un botón ...

SOI

8

La carrera del 10
La carrera del 10

Dos hebras ejecutan los código que se
muestra abajo y comparten la variable
i=0 (inicialemente) ¿Cuál de ellas gana?

void incremento(int i) {
while(i< 10) {
i= i + 1;

};
printf("Hebra 1 ha
ganado\n");

}

SOI

void decremento(int i) {
while(i > -10) {

i= i - 1;

};
printf("Hebra 2 ha
ganado\n");

}

9

Código real del ejemplo
Código real del ejemplo

#include <windows.h>
#include <stdio.h>
volatile INT i=0; /* eliminar optimización compilador*/
void Incremento(void *) {
while(i < 10) {

i= i + 1;
printf("Hebra 1 ha ganado\n");}
void Decremento(void *) {
while (i > -10) {
i= i- 1;
printf("Hebra 2 ha gandado\n"); }

void main(void) {
/*ejecución aquí*/
HANDLE Hebras[2];
Hebras[0]=CreateThread(0,0,Incremento,NULL,0, NULL);
Hebras[1]=CreateThread(0,0,Decremento,NULL,0, NULL);
WaitForMultipleObjects(2, handles, TRUE, INFINITE);
} /* El valor de la variable depende de la ejecución*/

SOI

10

El productor-consumidor
El productor-consumidor

Paradigma de los procesos cooperantes: el
proceso productor genera información
(bloque de disco, mensaje de red, carac-
teres de teclado, etc.) que es utilizada por
el proceso consumidor (aplicación o SO)-
o a la inversa.

Productor

Consumidor

búfer

(finito o infinito)

SOI

11

Solución en memoria común
Solución en memoria común

Vamos a dar la solución al problema del
productor-consumidor con búfer acotado.
Datos compartidos:

/*tamaño del bufer */

int n;
struct item {...} ;
typedef bufer {0..n-1} item;
int ent, sal: 0..n-1;
ent = 0; /*inicialmente*/
sal = 0; /*inicialmente*/

SOI

12

Solución (cont.)
Solución (cont.)

Proceso productor
while (true) {
...
produce itemp;
...
while (ent+1 % n==
sal) {/*nada*/};

bufer[ent]=itemP;
ent = ent+1 % n;
};

Proceso consumidor
while (true) {
while (ent == sal){/
*nada*/};
itemC=bufer[sal];
sal = sal+1 % n;
...
consume itemC;
...
};

SOI

13

Conclusión del ejemplo
Conclusión del ejemplo

La solución en memoria compartida del
problema del búfer acotado es correcta
pero sólo permite la existencia de n-1
ítems en el búfer a la vez. ¿Por qué?
Para solventarlo, modificamos el código
añadiendo una variable común, contador,
inicializada a cero y que se incrementa cada
vez que se añade un nuevo ítem al búfer, y
se decrementa cada vez que retiramos un
elemento.

SOI

14

2ª versión del
2ª versión del
productor-consumidor
productor-consumidor

/*tamaño del bufer */

Datos compartidos:
int n;
struct item {...} ;
typedef bufer {0..n-1} item;
int ent, sal: 0..n-1;
ent = 0;
sal = 0;
cont: 0..n; /*lleva la cuenta del numero
bufer*/
cont := 0;

/*inicialmente*/
/*inicialmente*/
de items que hay en el
/*inicialmente*/

SOI

15

Nuevo código
Nuevo código

Proceso productor

while (true) }

...
produce itemP;
...
while (cont == n)
bufer[ent]=itemP;
ent=ent+1 % n;
cont= cont+1;

{/*nada*/;

};

Proceso consumidor

while (true) {

while (cont = 0)
{/nada*/};
itemC=bufer[sal];
sal=sal+1 % n;
cont = cont-1;
...
consume itemC;
...

};

SOI

16

Intercalados y
Intercalados y
variables compartidas
variables compartidas

Operación n:=n+1
en seudoensamblador:
I11: load M into R1
I12: add 1 to R1
I13: store R1 in M
Operación n:=n-1
en seudoensamblador:
I21: load M into R2
I22: sub 1 to R2
I23: store R2 in M

Sea inicialmente n=5:
El intercalado:
I11, I12 , I13 ,I21 ,I22 ,I23
daría el valor final n=5.
Otro intercalado:
I11, I21 , I12 ,I13 ,I22 ,I23
daría finalmente n=4.
Otro intercalado:
I21, I21 , I22 ,I23 ,I12 ,I13
daría finalmente n=6.
¡ Hay condición de
carrera !

17

SOI

Conclusión de la
Conclusión de la
nueva versión
nueva versión

La corrección de la solución depende de que
todas las declaraciones donde se manipulan
variables compartidas se ejecuten de forma
atómica (o indivisible). En este ejemplo,
cont==?, cont:=cont+1 y cont:=cont-1).
Conclusión: el acceso concurrente a los datos
compartidos provoca inconsistencias, salvo
que dispongamos de un mecanismo para
asegurar la ejecución ordenada de los
procesos cooperantes; esto es, que sólo
permita los intercalados correctos.

SOI

18

Otro ejemplo
Otro ejemplo

Tendemos a pensar que solo las operaciones de ++
ó –- producen problemas, pero éstos se dan en
cualquier manipulación de variables compartidas.
Un fragmento de código erróneo que solemos usar
en los primeros ejercicios es el siguiente:

var: variable compartida;
x= sin(5);
if (var > 0)
…
y = cos(3)
var = 3*x + 2*y;
else
…;
…
Hebra_2
Hebra_1
¿Qué intercalados se pueden producir?

SOI

19

El problema de la
El problema de la
Sección Crítica
Sección Crítica

Sean n procesos compitiendo todos para
usar algunos datos compartidos.
Cada proceso tiene un segmento de
código, denominado Sección Crítica (SC),
en el que accede a los datos compartidos.
Problema: asegurar que cuando un proceso
está ejecutando su SC, ningún otro proceso
puede ejecutarse en la suya, es decir,
asegurar que múltiples instrucciones, las
SCs, parezcan una única instrucción.

SOI

20

Sección crítica
Sección crítica

Hebras

SOI

Sección crítica

21

Estructura de la solución
Estructura de la solución

Estructura de Pi:
while (true){
entrada a sección

sección crítica
salida de sección
resto de código
};

Construiremos una
solución que de la forma :
Protocolo de entrada a SC
– controla el acceso de
los procesos a las SCs.
Protocolo de salida de la
SC – notifica salida de un
proceso de su SC.
Y cumpla las propiedades
…

SOI

22

1º requisito de una
1º requisito de una
solución al p.s.c.
solución al p.s.c.

Exclusión mutua - Si Pi se está ejecutando
en su SC, entonces ningún Pj (con j „ i)
puede ejecutarse en su SC.

Pk

Pj

Pi

Secciones

críticas

SOI

23

2º requisito de una
2º requisito de una
solución al p.s.c.
solución al p.s.c.

Progreso (o libre de interbloqueo) - Si no
hay Pjs en sus SCs y existe Pi que desea
entrar en su SC, entonces la selección de
Pi no debe posponerse indefinidamente.

Pk

Pj

Pi

Secciones

críticas

SOI

24

3º requisito de una
3º requisito de una
solución al p.s.c.
solución al p.s.c.

Espera limitada (o libre inanición) - Debe
existir un límite al número de veces que
se les permite a los Pj’s entrar en sus SC’s
después de que un Pi haya realizado un
petición de entrar en la suya y antes de
que petición se satisfaga.
Pi

¡¡ Limitada !!

Pk

Pj

Sección
crítica

SOI

25

Condiciones de entorno
Condiciones de entorno
y propiedades
y propiedades

Una solución correcta al problema de la SC:
No debe suponer nada a cerca de las
velocidades relativas de los n procesos.
Supone que ningún proceso se ejecuta a
velocidad cero.
Imparcialidad: no hacer esperar más a
unos que a otros.
Eficiencia: no gastar más recursos de los
necesarios.
¡Ah sí!, y que sea lo más simple posible.

+Propiedades deseables de la solución:

SOI

26

Soluciones para la
Soluciones para la
Exclusión Mutua
Exclusión Mutua

Exclusión frente al hardware - Deshabilitar
las interrupciones para proteger nuestra SC
de la rutina de servicio de interrupción.
Exclusión frente a otros procesos:

Espera ocupada-los procesos comprueban
constantemente si es seguro entrar a la SC
Bloqueo -los procesos se bloquean al
intentar en