PDF de programación - Programación concurrente - Master de Computación I - Conceptos y recursos para la programación concurrente

Programación concurrente

Master de Computación

I Conceptos y recursos para la programación concurrente:
I.6 Sincronización basada en memoria compartida.

J.M. Drake
M. Aldea

Procesos concurrentes y memoria compartida.

• Si los diferentes procesos de un programa concurrente tienen
acceso a variables globales o secciones de memoria
compartidas, la transferencia de datos a través de ella es una
vía habitual de comunicación y sincronización entre ellos.

• Las primitivas para programación concurrente basada en
de
memoria
sincronización entre procesos y de exclusión mutua utilizando
la semántica de acceso a memoria compartida.

compartida

resuelven

los

problemas

• En esta familias de primitivas, la semántica de las sentencias
hace referencia a la exclusión mutua, y la implementación de
la sincronización entre procesos se hace de forma indirecta.

ProCon’12: I.6: Sincronización basada en memoria compartida J.M. Drake, M. Aldea

2

Mecanismos basados en memoria compartida

• Semáforos: Son componentes pasivos de bajo nivel de
abstracción que sirven para arbitrar el acceso a un recurso
compartido.

• Secciones críticas: Son mecanismos de nivel medio de
abstracción orientados a su utilización en el contexto de un
lenguaje de programación y que permiten la ejecución de un
bloque de sentencias de forma segura.

• Monitores: Son módulos de alto nivel de abstracción que

sirven para arbitrar el acceso a un recurso compartido.

ProCon’12: I.6: Sincronización basada en memoria compartida J.M. Drake, M. Aldea

3

Definición de semáforo.

• Un semáforo es un tipo de datos.

• Como cualquier tipo de datos, queda definido por:

 Conjunto de valores que se le pueden asignar.
 Conjunto de operaciones que se le pueden aplicar.

• Un semáforo tiene asociada una lista de procesos, en la que

se incluyen los procesos suspendidos a la espera de su cambio
de estado.

ProCon’12: I.6: Sincronización basada en memoria compartida J.M. Drake, M. Aldea

4

Valores de un semáforo.

• En función del rango de valores que puede tomar, los semáforos se

clasifican en:
 Semáforos binarios: Pueden tomar solo los valores 0 y 1.

var mutex: BinSemaphore;

 Semáforos contadores: Puede tomar cualquier valor Natural (entero no

negativo).

var escribiendo: Semaphore;

• Un semáforo con el valor 0 representa un semáforo cerrado, y con un

valor mayor que cero representa un semáforo abierto.

• Mas adelante demostraremos que un semáforo contador se puede

implementar utilizando semáforos Binarios.

• Los sistemas suelen ofrecer como componente primitivo semáforos

contadores, y su uso, lo convierte de hecho en semáforo binario.

ProCon’12: I.6: Sincronización basada en memoria compartida J.M. Drake, M. Aldea

5

Operaciones seguras de un semáforo.

• Un semáforo

var p: semaphore;

admite dos operaciones seguras:
 wait(p): Si el semáforo no es nulo (abierto) decrementa en uno el
valor del semáforo. Si el valor del semáforo es nulo (cerrado), el
thread que lo ejecuta se suspende y se encola en la lista de procesos en
espera del semáforo.

 signal(p): Si hay algún proceso en la lista de procesos del semáforo,
activa uno de ellos para que ejecute la sentencia que sigue al wait que
lo suspendió. Si no hay procesos en espera en la lista incrementa en 1
el valor del semáforo.

ProCon’12: I.6: Sincronización basada en memoria compartida J.M. Drake, M. Aldea

6

Operación no segura de un semáforo.

• Un semáforo

var p: semaphore;

admite una operación no segura:

 initial(p, Valor_inicial): Asigna al semáforo p el valor inicial que se

pasa como argumento.

• Esta operación es no segura y por tanto debe ser ejecutada en

una fase del programa en la que se tenga asegurada que se
ejecuta sin posibilidad de concurrencia con otra operación
sobre el mismo semáforo.

ProCon’12: I.6: Sincronización basada en memoria compartida J.M. Drake, M. Aldea

7

Operación wait.

• Pseudocódigo de la operación: wait(p);

if p>0
then p:= p-1;
else Suspende el proceso y lo encola en la lista del semáforo.

• Está protegida contra expulsión entre el chequeo del valor
del semáforo y la asignación del nuevo valor o la suspensión.

• El nombre de la operación wait es equívoco. En contra de su
significado semántico natural, su ejecución a veces provoca
una suspensión pero en otros caso no implica ninguna
suspensión.

ProCon’12: I.6: Sincronización basada en memoria compartida J.M. Drake, M. Aldea

8

Operación signal.

• Pseudocódigo de la operación: signal(p);

if Hay algún proceso en la lista del semáforo
then Activa uno de ellos
else p:= p+1;

• Está protegida contra expulsión entre la comprobación de si

hay proceso bloqueado y la activación o asignación.

• La ejecución de la operación signal(p) nunca provoca una

suspensión del thread que lo ejecuta.

• Si hay varios procesos en la lista del semáforo, la operación

signal solo activa uno de ellos
 se elige de acuerdo con un criterio propio de la implementación

(FIFO, LIFO, Prioridad, etc.).

ProCon’12: I.6: Sincronización basada en memoria compartida J.M. Drake, M. Aldea

9

Ejemplo: Exclusión mutua.
program Exclusion_Mutua;

var mutex: binsemaphore;
process type Proceso;
begin
repeat

wait(mutex);
(* Código de la sección crítica *)
signal(mutex);

forever;
end;

var p, q, r: Proceso;
begin
initial(mutex,1);
cobegin p; q; r; coend;
end;

ProCon’12: I.6: Sincronización basada en memoria compartida J.M. Drake, M. Aldea

10

Ejemplo: Sincronización productor-consumidor (mal)

Productor

Consumidor

unbounded

var datoDisponible: Semaphore:= 0;

process Productor;

var dato: Tipo_Dato;
begin
repeat
produceDato(var dato);
dejaDato(dato);
signal(datoDisponible);

forever;
end:

process Consumidor;
var dato: Tipo_Dato;
begin
repeat
wait(datoDisponible);
tomaDato(var dato);
consume(dato);
forever;
end;

ProCon’12: I.6: Sincronización basada en memoria compartida J.M. Drake, M. Aldea

11

Ejemplo: Sincronización productor-consumidor (bien)

datoDisponible: Semaphore:=0;
mutex: BinSemaphore:=1;

process type Productor;
var dato:Tipo_Dato;
begin
repeat

dato:=Produce_Dato;
wait(mutex);
dejaDato(dato);
signal(mutex);
signal(datoDisponible);

forever;
end;

process type Consumidor;
var dato:Tipo_Dato;
begin
repeat
wait(datoDisponible);
wait(mutex);
dato:=tomaDato;
signal(mutex);
consume(dato);
forever;
end;

ProCon’12: I.6: Sincronización basada en memoria compartida J.M. Drake, M. Aldea

13

Productor consumidor con buffer limitado (1).
program Productor_Consumidor;
const LONG_BUFFER = 5;
type Tipo_Dat= ....;
var datoDisponible:Semaphore;
hueco:Semaphore;
mutex: BinSemaphore;
buffer: record datos:array[0..LONG_BUFFER-1]of Tipo_Dato;

nextIn, nextOut: Natural:=0; end;

procedure dejaDato(d:Tipo_Dat); procedure tomaDato(d:Tipo_Dat);
begin begin
buffer.dato[buffer.nextIn]:=D; d:=buffer.dato[buffer.nextOut];
buffer.nextIn:=(buffer.nextIn+1) buffer.nextOut:= (buffer.nextOut+1)

mod LONG_BUFFER;

mod LONG_BUFFER;

end; end;

ProCon’12: I.6: Sincronización basada en memoria compartida J.M. Drake, M. Aldea

14

Productor consumidor con buffer limitado (2).

process productor;
var dato:Tipo_Dat;
begin
repeat
dato:=produceDato;


wait(hueco);
wait(mutex);
dejaDato(dato);
signal(mutex);
signal(datoDisponible);



forever;
end;

begin

process consumidor;
var dato: Tipo_Dat;
begin
repeat
wait(datoDiponible);
wait(mutex);
tomaDato(dato);
signal(mutex);
signal(hueco);
Consume(dato);
forever;
end;

initial(mutex,1); initial(hueco, LONG_BUFFER); initial(datoDisponible,0);

cobegin productor; consumidor; coend;
end.

ProCon’12: I.6: Sincronización basada en memoria compartida J.M. Drake, M. Aldea

15

Implementación de semáforos contadores con binarios

type SemCont = record
mutex, espera: BinSemaphore;

cuenta: Natural;

end;
procedure initialCont(var s:SemCont, v:Natural);
begin initial(s.mutex,1); v.cuenta:= v;
if (v=0) then initial(s.espera,0) else initial(s.espera,1);
end;
procedure waitCont(var s:SemGral); procedure signalCont(var s:SemCont);
begin begin
wait(s.espera); wait(s.mutex)
wait(s.mutex); s.cuenta:= s.cuenta +1;
s.cuenta:= s.cuenta – 1; if (s.cuenta=1) then signal(s.espera);
if (s.cuenta>0) then signal(s.espera); signal(s.mutex);
signal(s.mutex); end;
end;

ProCon’12: I.6: Sincronización basada en memoria compartida J.M. Drake, M. Aldea

16

Cena de filósofos chinos (1)

program Cena_filósofos_chinos;
const N = 5;
var palillo: array [1..N] of BinSemaphore;

sillasLibres: Semaphore;

process type TipoFilosofo(nombre: Integer); begin ... end;
var filosofo: array [1..N] of TipoFilosofo;
i: Integer;

begin
for i:=1 to N do initial(palillo[I],1);
initial(sillasLibres,N-1);
cobegin for i:=1 to N do filosofo[I](I); coend;
end.

ProCon’12: I.6: Sincronización basada en memoria compartida J.M. Drake, M. Aldea

17

Cena de filósofos chinos (2)

process type TipoFilosofo(nombre: Natural);
derecho=nombre;
izquierdo=nombre