PDF de programación - Tema2. Comunicación y sincronización con memoria compartida

TEMA 2. Comunicación y
TEMA 2. Comunicación y

sincronización con
sincronización con
memoria compartida
memoria compartida

Ingeniería en Informática

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

© José Miguel Santos Espino – Alexis Quesada Arencibia

ProgramaciónConcurrente

2

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

(cid:132) J. Palma, C. Garrido, F. Sánchez, A. Quesada,

2003

(cid:132) Principles of Concurrent and Distributed

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

(cid:132) Sistemas Operativos

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

© José Miguel Santos Espino – Alexis Quesada Arencibia

ProgramaciónConcurrente

3

© José Miguel Santos Espino – Alexis Quesada Arencibia

ProgramaciónConcurrente

4

Modelo del sistema
(cid:132) Conjunto de procesos cooperativos

que se ejecutan de manera asíncrona y
que comparten datos

(cid:132) Proceso cooperativo: proceso que

puede afectar o verse afectado por los
demás procesos que se ejecutan en el
sistema

© José Miguel Santos Espino – Alexis Quesada Arencibia

ProgramaciónConcurrente

5

Ejemplo: buffer limitado

N: constant integer:=...;
type elemento is ...;
buffer: array(0..N-1) of elemento;
entra,sale: mod N:=0;
contador: integer range 0..N:=0;

loop

Productor
loop

...
producir un elemento elem
...
loop
end loop;
buffer(entra):=elem;
entra:=entra+1;
contador:=contador+1;

exit when contador<N;

end loop;
© José Miguel Santos Espino – Alexis Quesada Arencibia

end loop;

Consumidor

exit when contador>0;

loop
end loop;
elem:=buffer(sale);
sale:=sale+1;
contador:=contador-1;
...
consumir elemento elem
...

ProgramaciónConcurrente

6

1

Problema

(cid:132) Ambas rutinas son correctas si se ejecutan por separado pero podrían

NO funcionar si se ejecutan de manera concurrente

(cid:132) Supongamos que contador contiene en un momento dado el valor 5 y

que las instrucciones “contador=contador+1” y “contador=contador-1”
se ejecutan de forma concurrente (¡contador podría ser 4, 5 o 6!)
contador = contador + 1
registro1 := contador;
registro1 := registro1 +1;
contador : registro1;

contador=contador-1
registro2 := contador;
registro2 := registro2 -1;

contador := registro2;

T0: productor
T1: productor
T2: consumidor
T3: consumidor
T4: productor
T5: consumidor

registro1 := contador
registro1 := registro1+1
registro2 := contador
registro2 := registro2 -1
contador := registro1
contador := registro2

(registro1= 5)
(registro1 = 6)
(registro2 = 5)
(registro2 = 4)
(contador = 6)
(contador = 4)
7

© José Miguel Santos Espino – Alexis Quesada Arencibia

ProgramaciónConcurrente

Modelo del sistema
(cid:132) N procesos intentan acceder a un recurso compartido

en un bucle infinito:
loop

Sección_No_Crítica;
Pre_Protocolo;
Sección_Crítica;
Post_Protocolo;

end loop;

(cid:132) Nunca puede haber más de un proceso en la sección

crítica (exclusión mutua)

(cid:132) Los pre y post protocolos serán algoritmos para

garantizar que se cumple la exclusión mutua

© José Miguel Santos Espino – Alexis Quesada Arencibia

ProgramaciónConcurrente

8

Requisitos de la solución,
según Ben-Ari
(cid:132) Siempre se debe cumplir la exclusión mutua.
(cid:132) Un proceso puede detenerse en su sección no

crítica, sin que afecte a los demás procesos.

(cid:132) No pueden aparecer interbloqueos.
(cid:132) No puede haber inanición: si un proceso

declara entrar en s.c., terminará entrando.
(cid:132) Progreso si no hay contención: si un solo
proceso quiere entrar en s.c., debe poder
entrar sin más.

Requisitos de la solución,
según Peterson
(cid:132) Exclusión mutua
(cid:132) Progreso: si ningún proceso está en sección

crítica y hay procesos que desean entrar en
su s.c., sólo estos últimos participarán en la
decisión y ésta se tomará en un tiempo finito.

(cid:132) Espera limitada: hay un límite para el

número de veces que otros procesos pueden
adelantarse a un proceso que quiere entrar
en s.c.

© José Miguel Santos Espino – Alexis Quesada Arencibia

ProgramaciónConcurrente

9

© José Miguel Santos Espino – Alexis Quesada Arencibia

ProgramaciónConcurrente

10

Primer intento: variable turno

turno: integer range 1..2 := 1;

loop

SNC1;
loop

loop

SNC2;
loop

exit when turno=1;

exit when turno=2;

end loop;
SC1;
turno:=2;

end loop;

end loop;
SC1;
turno:=1;

end loop;

Discusión del primer intento
(cid:132) ¿Garantiza exclusión mutua?
(cid:132) ¿Está libre de interbloqueo?
(cid:132) ¿Está libre de inanición?
(cid:132) ¿Garantiza el progreso si no hay

contención?

© José Miguel Santos Espino – Alexis Quesada Arencibia

ProgramaciónConcurrente

11

© José Miguel Santos Espino – Alexis Quesada Arencibia

ProgramaciónConcurrente

12

2

Segundo intento: avisadores

Tercer intento

flag1,flag2: boolean := true;

flag1,flag2: boolean := true;

loop

SNC1;
loop

loop

SNC2;
loop

exit when flag2;

exit when flag1;

end loop;
flag1:=false;
SC1;
flag1:=true;

end loop;

end loop;
flag2:=false;
SC2;
flag2:=true;

end loop;

loop

SNC1;
flag1:=false;
loop

loop

SNC2;
flag2:=false;
loop

exit when flag2;

exit when flag1;

end loop;
SC1;
flag1:=true;

end loop;

end loop;
SC2;
flag2:=true;

end loop;

© José Miguel Santos Espino – Alexis Quesada Arencibia

ProgramaciónConcurrente

13

© José Miguel Santos Espino – Alexis Quesada Arencibia

ProgramaciónConcurrente

14

Solución de Peterson

flag1,flag2: boolean := true;
turno: integer range 1..2 := 1;

loop

SNC1;
flag1:=false;
turno:= 2;
loop

loop

SNC2;
flag2:=false;
turno:= 1;
loop

exit when flag2 or

exit when flag1 or

turno=1;

turno=2;

end loop;
SC1;
flag1:=true;

end loop;

end loop;
SC2;
flag2:=true;

end loop;

Soluciones hardware
(cid:132) Entorno uniprocesador: prohibir las

interrupciones mientras se modifican
variables compartidas
(cid:132) Problema: Entorno multiprocesador

(cid:132) Instrucciones atómicas test-and-set o

SWAP.

© José Miguel Santos Espino – Alexis Quesada Arencibia

ProgramaciónConcurrente

15

© José Miguel Santos Espino – Alexis Quesada Arencibia

ProgramaciónConcurrente

16

Soluciones hardware
(cid:132) Permiten evaluar y asignar un valor a una

variable de forma atómica.
(cid:132) test-and-set(B): Pone B a truey devuelve el

antiguo valor de B.

(cid:132) SWAP(A,B): Intercambia los valores de A y B.
(cid:132) Si disponemos de estas instrucciones, se

simplifica muchísimo el problema de la
sección crítica.

Soluciones al problema de la SC
con instrucciones HD atómicas

loop

SNC1;
loop

exit when

Test_and_Set(llave)=false;

end loop;
SC1;
llave:=false;

end loop;

loop

SNC1;
llave:=true;
loop

Swap(cerradura,llave);
exit when llave=false;

end loop;
SC1;
cerradura:=false;

end loop;

© José Miguel Santos Espino – Alexis Quesada Arencibia

ProgramaciónConcurrente

17

© José Miguel Santos Espino – Alexis Quesada Arencibia

ProgramaciónConcurrente

18

3