Sincronización

Universidad Nacional de San Antonio Abad del Cusco

PROGRAMACION CONCURRENTE Y PARALELA

MECANISMOS DE COMUNICACION Y SINCRONIZACION

1

Indice
Definición de los semáforos Exclusión mutua con semáforos Sincronización condicional con semáforos Programas Ejemplo con Semáforos Evaluación de los semáforos

2

SEMAFOROS
Es un mecanismo introducido por Dijkstra y su aplicación permitecontrolar el acceso exclusivo a recursos compartidos Su aplicación tambien permite la sincronización entre procesos Esta formado de un contador y una cola asociada de procesos o hilos en espera Las operaciones básica sobre el contador son Wait o P y Signal o V

3

Semaforo
Atributos •Cola •Contador Operaciones •Wait ó P •Signal ó V

4

SEMAFOROS
Atributos:




Cola: cola deprocesos en espera asociada al semáforo. Es cola es la cola que maneja el sistema operativo. (implicita) Contador (S): es un entero positivo P(S) / wait(S): si S > 0  decrece el valor de S en 1 (S:=S-1) si S = 0  se retrasa/aplaza el proceso hasta que S > 0 (y entonces se decrementa su valor) V(S) / signal(S): incrementa en 1 el valor del semáforo (S:=S+1)

Operaciones:




Las operacioneswait y signal son atómicas (indivisibles). En un programa con semáforo se cumplen dos relaciones:
 

S >= 0 S = S0 + #signals - #waits (S0 es el valor inicial del semáforo)
5

SEMAFOROS
wait(S):
if S > 0 then S:= S–1; else bloquear este proceso en S;  espera bloqueada

signal(S):
if hay procesos bloqueados en S then desbloquear uno de ellos; else S:=S+1;

6

Semaforos
Tipos


General: 0,1,2,3,4,5,…………n Binario ; 0,1

¿Qué pasa si se intenta hacer un operación signal sobre un semaforo binario con valor 1?
 

no tiene efecto se genera un error y se aborta el proceso que ejecuta el signal

7

Justicia y semáforos
Semáforo totalmente justo (strongly fair semaphore): FIFO.


Un proceso bloqueado será siempre desbloqueado (siempre que se realizansuficientes operaciones signal).

Semáforo debilmente justo (weakly fair semaphore): aleatorio.


Un proceso puede permanecer bloqueado permanentemente (incluso si se realizan infinitas operaciones signal).

La propiedad de vivacidad(liveness) dependerá de la implementación de los semáforos.

8

Exclusión mutua con semáforos
Resolver la exclusión mutua entre dos procesos es trivial: losprotocolos de entrada y salida se implementan mediante operaciones wait y signal, respectivamente, sobre un semáforo binario. El valor inicial del semáforo será 1, indicando que el recurso esta libre. Hilo P1 inicio mientras verdad hacer inicio {sección no crítica} wait(mutex) {sección crítica} signal(mutex) fin fin Hilo P2 inicio mientras verdad hacer inicio {sección no crítica} wait(mutex) {seccióncrítica} signal(mutex) fin fin

9

Ejemplos: Problema de Productores Consumidores

10

11

12

13

14

15

16

17

PROCESO consumidores; PROCESO productores VAR cdato : dato; VAR pdato : dato; inicio inicio mientras true hacer mientras true hacer inicio inicio wait(consumir); wait(producir); wait(cs); pdato := producir(); cdato:= buffer[sal]; wait(ps); sal := (salmod MAX) + 1; buffer[ent]:= pdato; signal(cs); ent := (ent mod MAX) + 1; signal(producir); signal(ps); consumir(cdato); signal(consumir); fin fin fin; (* Consumidores *) fin; (* Productores *) Inicio {programa principal} CONS MAX = .. ; (* Cap. Buffer *) TYPE dato: .. ; (* Tipo de datos*) VAR buffer :array[1..MAX]of dato; producir, consumir:semaforo; ps, cs: semaforo; ent, sal: integer;iniciar(ps,1); iniciar(cs,1); iniciar(consumir,0); iniciar(poducir,MAX); ent:=1; sal:=1; {ejecutar concurrentemente} productores; consumidores fin. (* principal *) 18

Evaluación de los semáforos
Simples y facilmente implementables Bajo nivel de abstracción  Difícil su uso fiable Herramienta de programación no estructurada Difícil localizar fallos y mantener el programa  No adecuado para sistemas...