PDF de programación - Comunicación y sincronización con datos comunes

ditdit

UPM

Comunicación y 
sincronización

con datos comunes

Juan Antonio de la Puente

DIT/UPM

Transparencias basadas en el capítulo 8 del libro de A. Burns y A. Wellings Real­Time Systems and Programming Languages, 3ª edición (2001)

Objetivos

u Comprender los problemas relacionados con la 

comunicación entre procesos concurrentes 

u Revisar los mecanismos de sincronización que se utilizan 

para la comunicación mediante datos compartidos entre 
tareas 

u Estudiar la forma de realizar este tipo de comunicación 

en Ada

STRL ­ Datos comunes ­ 20/03/07

©2001­2002 Juan Antonio de la Puente

 2

Comunicación y sincronización

u Raras veces los procesos de un sistema son 

independientes unos de otros
– A menudo cooperan para un fin común o compiten por la utilización 

de recursos.

u Para ello es necesario realizar operaciones de 
comunicación y sincronización entre procesos
– dos procesos se comunican cuando hay una transferencia de 

información de uno a otro

– dos procesos están sincronizados cuando hay restricciones en el 

orden en que ejecutan algunas de sus acciones

Los dos conceptos están relacionados

u Hay diferentes formas de abordar el problema:

– datos comunes 
– mensajes.

STRL ­ Datos comunes ­ 20/03/07

©2001­2002 Juan Antonio de la Puente

 3

Comunicación con datos comunes

u En un sistema monoprocesador, la forma más directa de 

comunicación entre dos o más procesos consiste en 
compartir datos
– un proceso escribe una variable compartida, el otro la lee

u Sin embargo, el acceso incontrolado a variables comunes 

puede producir resultados anómalos
– se dice que hay una condición de carrera cuando el resultado de la 
ejecución depende del orden en que se intercalan las instrucciones 
de dos o más procesos

– se trata de una situación anómala que hay que evitar

STRL ­ Datos comunes ­ 20/03/07

©2001­2002 Juan Antonio de la Puente

 4

Ejemplo

Incrementar 
contador
LDA contador
INC
STA contador

T1

T2

contador=0

Incrementar 
contador
LDA contador
INC
STA contador

u El resultado final puede ser 1 ó 2

– Depende de las velocidades relativas de los procesos
– Para evitar condiciones de carrera hay que asegurar que las 

operaciones con variables comunes se ejecutan de forma atómica  
(indivisible)

STRL ­ Datos comunes ­ 20/03/07

©2001­2002 Juan Antonio de la Puente

 5

Exclusión mutua

u Una secuencia de instrucciones que se debe ejecutar de 

forma indivisible se denomina sección crítica
– las operaciones de dos secciones críticas respecto a la misma 

variable no se deben entremezclar

u La forma de sincronización que se usa para proteger una 

sección crítica se llama  exclusión mutua
– supondremos que el acceso a una celda de memoria es atómico

(hay exclusión mutua entre operaciones que sólo hacen un acceso 
a memoria)

STRL ­ Datos comunes ­ 20/03/07

©2001­2002 Juan Antonio de la Puente

 6

Sincronización condicional

u Cuando una acción de un proceso solo se puede ejecutar 

si otro proceso está en determinado estado o ha 
ejecutado ciertas acciones, hace falta un tipo de 
sincronización denominada sincronización condicional

u Ejemplo: Productor y consumidor con tampón limitado

productor

put

tampón

get

consumidor

– no se debe hacer Put cuando el tampón está lleno.
– no se debe hacer Get cuando el tampón está vacío
– además, hay exclusión mutua en el acceso al tampón

STRL ­ Datos comunes ­ 20/03/07

©2001­2002 Juan Antonio de la Puente

 7

Espera ocupada

u Una forma de realizar la exclusión mutua es usar un 

indicador compartido
– Se puede hacer si el acceso al indicador sea atómico
(por ejemplo, mediante una instrucción test­and­set )

while Test_and_Set(Flag) loop
null;
end loop;
-- sección crítica
Flag := False;

– Si no, hay que usar algoritmos complejos

u Es un método poco eficiente y complicado
u No es fácil imponer un orden de acceso cuando hay varios 

procesos esperando

STRL ­ Datos comunes ­ 20/03/07

©2001­2002 Juan Antonio de la Puente

 8

Suspensión síncrona

u Una solución más eficiente consiste en disponer de un 

indicador que permita que un proceso se detenga o 
continúe su ejecución de forma atómica
– la atomicidad se asegura en el núcleo de multiprogramación

u Ejemplo

if not Flag then
suspend;
end if;
-- sección crítica
Flag := False;

– ¡tiene una condición de carrera!

u Es mejor para sincronización condicional

STRL ­ Datos comunes ­ 20/03/07

©2001­2002 Juan Antonio de la Puente

 9

Estados de un proceso

terminado

esperando

terminación pupilo

suspendido

inexistente

creado

iniciándose

ejecutable

esperando
inicio hijo

STRL ­ Datos comunes ­ 20/03/07

©2001­2002 Juan Antonio de la Puente

 10

Semáforos

u Un semáforo es una variable que toma valores enteros no 

negativos

u Además de asignarle un valor inicial, sólo se pueden 

hacer dos operaciones con un semáforo S
– Down:  Si S > 0, decrementa S en 1 

Si S £  0, la tarea se suspende hasta que S > 0
– Up: 
Incrementa S en 1
Down y Up son indivisibles

u Otros nombres comunes para las operaciones de un semáforo son:

– Wait / Signal
– P / V  (passieren / vrijmachen) 
– Secure / Release,

STRL ­ Datos comunes ­ 20/03/07

©2001­2002 Juan Antonio de la Puente

 11

Ejemplo

u Supongamos una definición como la siguiente

(ojo, no está predefinida en Ada)

package Semaphores is
type Semaphore (Initial : Integer := 1)
is limited private;

procedure Down (S : in out Semaphore);
procedure Up (S : in out Semaphore);

private
...
end Semaphores;

u La implementación debe garantizar las propiedades 

de Down y Up

STRL ­ Datos comunes ­ 20/03/07

©2001­2002 Juan Antonio de la Puente

 12

Exclusión mutua con semáforos

Mutex : Semaphore; -- iniciado a 1 por defecto

task T1;
task body T1 is
begin
loop
Wait(Mutex);
-- sección crítica 1
Up(Mutex);
...
end loop;
end T1;

task T2;
task body T2 is
begin
loop
Wait(Mutex);
-- sección crítica 2
Up(Mutex);
...
end loop;
end T2;

Mutex es un semáforo binario

STRL ­ Datos comunes ­ 20/03/07

©2001­2002 Juan Antonio de la Puente

 13

Sincronización condicional

Condition : Semaphore(0);

task T1; -- espera

task body T1 is
begin
loop
S1A;
Down(Condition);
S1B;
end loop;
end T1;

task T2; -- avisa
task body T2 is
begin
loop
S2A; -- establece condición
Up(Condition);
S2B;
end loop;
end T2;

S1B no se ejecuta hasta que T2 avisa que se cumple la condición

STRL ­ Datos comunes ­ 20/03/07

©2001­2002 Juan Antonio de la Puente

 14

Productor y consumidor (1)

package Buffer is -- objeto abstracto
procedure Put(X: in Item);
procedure Get(X: out Item);
end Buffer;

package body Buffer is
Size : constant Positive := 32; -- por ejemplo
subtype Index is mod Size;
type Store is array (Index) of Item;

Box : Store;
First, Last : Index := Index’First;
Mutex : Semaphore(1); -- exclusión mutua
Full; : Semaphore(0); -- elementos ocupados
Empty : Semaphore(Size); -- elementos libres

STRL ­ Datos comunes ­ 20/03/07

©2001­2002 Juan Antonio de la Puente

 15

Productor y consumidor (2)

procedure Put (X : in Item) is

begin
Down(Empty);
Down(Mutex);
Box(Last) := X;
Last := Last + 1;
Up(Mutex);
Up(Full);
end Put;

procedure Get (X : out Item) is

begin
Down(Full);
Down(Mutex);
X := Box(First);
First := First + 1;
Up(Mutex);
Up(Empty);
end Get;
end Buffer;

STRL ­ Datos comunes ­ 20/03/07

©2001­2002 Juan Antonio de la Puente

 16

Problemas de los semáforos

u Es fácil cometer errores

– Un solo Down o Up mal colocado puede hacer que el programa 

funcione incorrectamente

Ejemplos:

Up(S); ... Up(S);             
Down(S);   ... Down(S);
Up(S); ... Down(S);

­­ no hay exclusión mutua
­­ interbloqueo
­­ depende

u Es mejor usar mecanismos más abstractos y fiables

– regiones críticas
– monitores
– objetos protegidos

STRL ­ Datos comunes ­ 20/03/07

©2001­2002 Juan Antonio de la Puente

 17

Interbloqueo (deadlock)

u Dos procesos están interbloqueados si cada uno de 
ellos espera un condición o un recurso que depende 
del otro

X,Y : Semaphore;

task T1;
task body T1 is
begin
loop
Down(X);
Down(Y);
-- usar recursos
Up(Y));
Up(X);
end loop;
end T1;

task T2;
task body T2 is
begin
loop
Down(Y);
Down(X);
-- usar recursos
Up(X);
Up(Y);
end loop;
end T2;

STRL ­ Datos comunes ­ 20/03/07

©2001­2002 Juan Antonio de la Puente

 18

Interbloqueos, bloqueos “vivos” 

e inanición

u Se pueden evitar los interbloqueos asignando los recursos 

de forma ordenada
– no siempre es posible

u Se puede intentar asignar los recursos de forma más 

flexible
– pueden aparecer otros problemas:

» bloqueo “vivo”  (livelock)
»
» inanición (starvation)
»

nunca

los procesos se ejecutan, pero ninguno consigue recursos

los procesos se ejecutan, pero algunos no consiguen el recurso 

STRL ­ Datos comunes ­ 20/03/07

©2001­2002 Juan Antonio de la Puente

 19

Regiones críticas condicionales

u 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
– se identifica la variable compartida a la que se accede en una 

sección crítica

u La sincronización condicional se consigue mediante 

guardas  en las regiones críticas
– solo se puede entrar en la región crítica cuando la guarda es 

verdadera

Ejemplo (ojo, no es Ada):

V : shared T;
...
region V when condición is
...
end region;

STRL ­ Datos comunes ­ 20/03/07

©2001­2002 Juan Antonio de la Puente

 20

Productor y consumidor (1)

package body Buffer is

Size : constant Positive := 32; -- por ejemplo
subtype Index is mod Size;
subtype Count is Natural range 0..Size;
type Store is array (Index) of Item;

type Buffer_Type is
record
Box : Store;
First, Last : Index := Inde