Sem A For 3

Programación Concurrente

SEMÁFOROS

octubre de 2006

Fernando Cuartero

1

Problemas resolubles con semáforos „

El problema de la exclusión mutua Los semáforos binarios pueden ser utilizados para asegurar la ejecución de tareas concurrentes en exclusión mutua

„

El problema de la exclusión mutua débil Existen a lo sumo k>1 tareas concurrentes en ejecución solapada

„

Número de llamadas limitado Supongamos p1 y p2 dos procedimientos tales que en un determinado momento, el número de llamadas invocadas a los mismos (denotado #p1 y #p2) tiene una propiedad invariante. Por ejemplo abs(#p1 - #p2) < k para algún k. (Problema del buffer acotado)

octubre de 2006

Fernando Cuartero

2

Semáforos binarios Un “semáforo binario” es una variable que toma valores 0 o 1, y que sólo puede ser accedida por dos procedimientos predeterminados con los siguientes efectos: wait(s) (1) si s=0 entonces se suspende la ejecución hasta que se ejecute una operación signal (2) si s=1 entonces s := 1

signal(s) (1) si alguna llamada wait está suspendida, se selecciona una llamada suspendida para su reanudación (2) si no hay llamadas suspendidas entonces s:= 1

Nota: wait(s) puede denotarse con P(s) y signal(s) con V(s) octubre de 2006

Fernando Cuartero

3

Semáforos binarios

Un semáforo está formado por un valor numérico y una colección de procesos en espera

octubre de 2006

Fernando Cuartero

4

Semáforos binarios Implementación type semaforo is record valor: integer; L: Lista Procesos end;

wait (s)

s.valor:=s.valor-1; if s.valor<0 then L.agregar(proceso); bloquear; end if;

octubre de 2006

signal (s)

s.valor:=s.valor +1; if s.valor<= 0 then L.sacar(proceso); despertar(proceso): end if;

Fernando Cuartero

5

Semáforos binarios Solución al problema de la exclusión mutua semaforo mutex := 1 cobegin PROCESO 1 PROCESO 2 corend PROCESO 1 repeat sección no crítica 1 wait(mutex) sección crítica 1 signal(mutex) forever octubre de 2006

PROCESO 2 repeat sección no crítica 2 wait(mutex) sección crítica 2 signal(mutex) forever Fernando Cuartero

6

Semáforos binarios Solución al problema de la exclusión mutua „ „ „ „

Sea #CS el número de tareas en ejecución en sección crítica La seguridad del sistema se satisface si #CS + s = 1 Por definición de semáforo binario, tenemos s ≤ 1 Entonces #CS = 1 – s ≤ 1

octubre de 2006

Fernando Cuartero

7

Semáforos binarios Propiedad invariante de los semáforos Sea el semáforo s, entonces se satisface

s = valor inicial + #V(s) - #P(s) ≤ 1

octubre de 2006

Fernando Cuartero

8

Semáforos binarios Solución al problema de la exclusión mutua Otras propiedades „

El programa no puede entrar en deadlock Si existe deadlock, ambos procesos están bloqueados en el wait, lo que es imposible

„

No existe inanición (starvation) Si un proceso está suspendido, es porque el semáforo está a 0, pero sólo es posible si el otro proceso está en sección crítica. Entonces, la sección se abandonará y se ejecutará el signal.

octubre de 2006

Fernando Cuartero

9

Semáforos generales Un “semáforo general” es una variable que toma valores 0, 1, 2, ... y que sólo puede ser accedida por dos procedimientos predeterminados con los siguientes efectos: P(s) (1) si s=0 entonces se suspende la ejecución hasta que se ejecute una operación signal (2) si s>0 entonces s := s-1

V(s) (1) si alguna llamada wait está suspendida, se selecciona una llamada suspendida para su reanudación (2) si no hay llamadas suspendidas entonces s:= s+1

octubre de 2006

Fernando Cuartero

10

Semáforos generales Propiedad invariante de los semáforos Sea el semáforo general s, entonces se satisface

s = valor inicial + #V(s) - #P(s)

octubre de 2006

Fernando Cuartero

11

Tipos de semáforos „

Semáforos con conjunto de bloqueo Si existen procesos inactivos, el signal despierta uno de ellos no especificado

„

Semáforos con cola de bloqueo La política de activación de procesos es una cola FIFO

„

Semáforos con espera activa La inactivación de procesos se implementa mediante bucles de espera

„

Semáforos fuertemente equitativos Si existe un número ilimitado se llamadas a signal, todo proceso inactivo tiene garantizada su activación

„

Semáforos débilmente equitativos Lo anterior sólo es cierto si se alcanza un valor positivo en el semáforo

octubre de 2006

Fernando Cuartero

12

Tipos de semáforos „ „ „

„ „

Un semáforo con espera activa puede sufrir de starvation Un semáforo con cola de bloqueo NO puede sufrir de starvation Un semáforo con conjunto de bloqueo puede sufrir de starvation, para un número de procesos superior a 2 Un semáforo con cola de bloqueo es fuertemente equitativos Un semáforos con espera activa NO es débilmente equitativo P1 ejecuta el wait y entra en sección crítica P2 encuentra S=0 y entra en un bucle P1 sale de la región crítica, pone S a 1, vuelve a ejecutar el wait y vuelve a entrar en la región crítica P2 encuentra S=0 y entra en un bucle

octubre de 2006

Fernando Cuartero

13

Aplicación de los semáforos

Los semáforos son útiles para „ Sincronización de procesos „ Garantizar la exclusión mutua „ Para gestionar correctamente los recursos compartidos

octubre de 2006

Fernando Cuartero

14

Aplicación de los semáforos Sincronización

„

„

Para realizar una tarea, un proceso debe esperar hasta que otro anterior haya completado su actividad Ejemplo: Problema del productor-consumidor octubre de 2006

Fernando Cuartero

15

Aplicación de los semáforos Exclusión mutua

„ „

Supongamos que dos procesos desean escribir en la pantalla Es necesario garantizar la exclusión mutua para garantizar una salida correcta octubre de 2006

Fernando Cuartero

16

Aplicación de los semáforos Exclusión mutua

procedure EXAMPLE is SCREEN : SEMAPHORE; task ONE; task body ONE is begin loop WAIT (SCREEN); PUT_LINE (“Tarea 1"); SIGNAL (SCREEN); end loop; end ONE;

octubre de 2006

task TWO; task body TWO is begin loop WAIT (SCREEN); PUT_LINE (“Tarea 2"); SIGNAL (SCREEN); end loop; end TWO; begin INIT (SCREEN, 1); end EXAMPLE;

Fernando Cuartero

17

Aplicación de los semáforos Gestión de recursos

„

„ „

Debemos asegurar que no son utilizados más recursos que los disponibles Es una generalización de la exclusión mutua (un solo recurso) Ejemplo: Aparcamiento de vehículos octubre de 2006

Fernando Cuartero

18

Aplicación de los semáforos Gestión de recursos (parking)

procedure EXAMPLE is SPACES : SEMAPHORE; task type CAR (START, PARK : DURATION); task body CAR (START, PARK : DURATION) is begin delay (START); WAIT (SPACES); delay (PARK); SIGNAL (SPACES); end CAR;

octubre de 2006

Fernando Cuartero

CAR_1 : CAR (5.0, 10.0); CAR_2 : CAR (10.0, 12.0); CAR_3 : CAR (8.0, 10.0); begin INIT(SPACES, 2); end EXAMPLE;

19

Aplicación de los semáforos Gestión de recursos (parking)

IDEAS „ „ „

„

Se define un semáforo para cada colección de recursos Se inicializa el semáforo con el total de recursos disponibles Se invoca a wait cada vez que se solicita la asignación de un recurso Se invoca a signal cuando se libera el recurso

octubre de 2006

Fernando Cuartero

20

Implementación de semáforos package Semaphore_Package is type Semaphore is private; type Binary_Semaphore is private; function Init(N: Integer) return Semaphore; procedure Wait (S: Semaphore); procedure Signal(S: Semaphore); function Init(N: Integer) return Binary_Semaphore; procedure Wait (S: Binary_Semaphore); procedure Signal(S: Binary_Semaphore); Bad_Semaphore_Initialization: exception; end Semaphore_Package;

octubre de 2006

Fernando Cuartero

21

El problema del Productor-Consumidor Hasta ahora hemos estudiado una abstracción del problema de la sincronización Estudiaremos problemas en la comunicación Supongamos dos tipos de procesos: Productores y Consumidores

octubre de 2006

Fernando Cuartero

22

El problema del Productor-Consumidor Productores: Procesos que crean elementos de datos mediante un procedimiento interno (Produce), estos datos deben ser enviados a los consumidores. Consumidores: Procesos que reciben los elementos de datos creados por los productores, y que actúan en consecuencia mediante un procedimiento interno (Consume) Ejemplos: Impresoras, teclados, etc.

octubre de 2006

Fernando Cuartero

23

El problema del Productor-Consumidor

Problema: El productor envía un dato cada vez, y el consumidor consume un dato cada vez. Si uno de los dos procesos no está listo, el otro debe esperar. octubre de 2006

Fernando Cuartero

24

El problema del Productor-Consumidor Solución: Es necesario introducir un buffer en el proceso de transmisión de datos Buffer Productor

Consumidor

El buffer puede ser infinito. No obstante esto no es realista

octubre de 2006

Fernando Cuartero

25

El problema del Productor-Consumidor

Extrae Coloca

Datos almacenados

Posición de los punteros

Dirección de movimiento de los punteros

Alternativa: Buffer acotado en cola circular

octubre de 2006

Fernando Cuartero

26

El problema del Productor-Consumidor Algoritmo de funcionamiento del buffer acotado Productor

Consumidor

Proceso

octubre de 2006

Proceso

Almacena dato en el buffer

Extrae dato del buffer

Avanza el puntero cabeza un espacio

Avanza el puntero cola un espacio

Fernando Cuartero

27

El problema del Productor-Consumidor Problemas: El productor puede enviar un dato a un buffer lleno El consumidor puede extraer un dato de un buffer vacío

ES NECESARIO PREVENIR ESTAS SITUACIONES ANÓMALAS

octubre de 2006

Fernando Cuartero

28

El problema del Productor-Consumidor Algoritmo de funcionamiento del buffer acotado Productor

Consumidor

Proceso

Proceso

Pausa

Lleno?

Pausa

Si!

Vacío?

No!

No!

Almacena dato en el buffer

Extrae dato del buffer

Avanza el puntero cabeza un espacio

octubre de 2006

Si!

Avanza el puntero cola un espacio

Fernando Cuartero

29

El problema del Productor-Consumidor ¿Cómo saber si el buffer está vacío o lleno? „ „ „

„

Una condición será un semáforo inicializado a un cierto valor Necesitamos dos condiciones: lleno y vacío Para añadir un dato al buffer, es necesario comprobar (wait) la condición lleno. SI se efectúa la operación con éxito se realiza un signal sobre la condición vacío Para eliminar un dato del buffer, es necesario comprobar (wait) la condición vacío. SI se efectúa la operación con éxito se realiza un signal sobre la condición lleno

octubre de 2006

Fernando Cuartero

30

El problema del Productor-Consumidor ESQUEMA DE FUNCIONAMIENTO proceso Productor

proceso Consumidor

begin repeat producir elemento protocolo de entrada insertar el elemento en el buffer protocolo de salida forever end

begin repeat protocolo de entrada extraer un elemento del buffer protocolo de salida consumir el elemento forever end

octubre de 2006

Fernando Cuartero

31

El problema del Productor-Consumidor ESQUEMA DE FUNCIONAMIENTO • Uso de 2 semáforos • Vacios controla que la cola no esté llena. Inicializado a N • Llenos controla que la cola no esté vacía. Inicializado a 0 proceso Productor begin repeat producir elemento wait (vacios) insertar el elemento en el buffer signal (llenos) forever end octubre de 2006

proceso Consumidor begin repeat wait (llenos) extraer un elemento del buffer signal (vacios) consumir el elemento forever end Fernando Cuartero

32

El problema del Productor-Consumidor ESQUEMA DE FUNCIONAMIENTO • Controlar exclusión mutua • Uso de 3 semáforos. Añadir mutex proceso Productor begin repeat producir elemento wait (vacios) wait (mutex) insertar el elemento en el buffer signal (mutex) signal (llenos) forever end octubre de 2006

proceso Consumidor begin repeat wait (llenos) wait (mutex) extraer un elemento del buffer signal (vacios) signal (mutex) consumir el elemento forever end Fernando Cuartero

33

El problema del Productor-Consumidor IMPLEMENTACIÓN CON SEMAFOROS GENERALES with Semaphore_Package; use Semaphore_Package; task Producer; procedure PCS is

task Consumer1;

N: constant Integer := 100; B: array(0..N-1) of Integer; In_Ptr, Out_Ptr: Integer := 0; Llenos: Vacios: Mutex:

task Consumer2; begin null; end PCS;

Semaphore := Init(0); Semaphore := Init(N); Semaphore := Init(1);

octubre de 2006

Fernando Cuartero

34

El problema del Productor-Consumidor task body Producer is I: Integer := 0; begin loop I := I + 1; Producir; if I mod 40 = 0 then delay 1.0; end if; Wait(Vacios); Wait(Mutex); B(In_Ptr) := I; In_Ptr := (In_Ptr + 1) mod N; Signal(Mutex); Signal(Llenoss); end loop; end Producer; octubre de 2006

Fernando Cuartero

35

El problema del Productor-Consumidor task body Consumer1 is I: Integer; begin loop Wait(Llenos); Wait(Mutex); I := B(Out_Ptr); Out_Ptr := (Out_Ptr + 1) mod N; Signal(Mutex); Signal(Vacios); Consumir; end loop; end Consumer1;

octubre de 2006

task body Consumer2 is I: Integer; begin loop Wait(Llenos); Wait(Mutex); I := B(Out_Ptr); Out_Ptr := (Out_Ptr + 1) mod N; Signal(Mutex); Signal(Vacios); Consumir; end loop; end Consumer2;

Fernando Cuartero

36

El problema del Productor-Consumidor Propiedades del buffer acotado „ „

„

Sea #E el número de mensajes en el buffer Sean #inptr y #outptr el número de actualizaciones a los punteros in_ptr y out_ptr de entradas y salidas en el buffer En cada momento, al final de un proceso productor o consumidor se satisface „ „ „

#inptr > #outptr #E = #inptr - #outptr #E = MAX - spaces

octubre de 2006

Fernando Cuartero

37

El problema del Productor-Consumidor IMPLEMENTACIÓN CON SEMAFOROS BINARIOS with Semaphore_Package; use Semaphore_Package; task Producer; task Consumer1; task Consumer2;

procedure PCBS is N: constant Integer := 10; B: array(0..N-1) of Integer; In_Ptr, Out_Ptr: Integer := 0; Count: Integer := 0;

begin null; end PCBS;

Mutex : Binary_Semaphore := Init(1); Vacios, Llenos : Binary_Semaphore := Init(0);

octubre de 2006

Fernando Cuartero

38

El problema del Productor-Consumidor

task body Producer is I: Integer := 0; Local: Integer := 0; begin loop I := I + 1; Producir; if I mod 40 = 0 then delay 1.0; end if; if Local = N then Wait(Vacios); end if; Wait(Mutex); B(In_Ptr) := I;

octubre de 2006

Count := Count + 1; Local := Count; Signal(Mutex); if Local = 1 then Signal(Llenos); end if; In_Ptr := (In_Ptr + 1) mod N; end loop; end Producer;

Fernando Cuartero

39

El problema del Productor-Consumidor task body Consumer1 is I: Integer; Local: Integer := 0; begin loop if Local = 0 then Wait(Llenos); end if; Wait(Mutex); I := B(Out_Ptr); Count := Count - 1; Local := Count; Signal(Mutex); if Local = N-1 then Signal(Vacios); end if; Out_Ptr := (Out_Ptr + 1) mod N; Consumir 1; end loop; end Consumer1; octubre de 2006

task body Consumer2 is I: Integer; Local: Integer := 0; begin loop if Local = 0 then Wait(Llenos); end if; Wait(Mutex); I := B(Out_Ptr); Count := Count - 1; Local := Count; Signal(Mutex); if Local = N-1 then Signal(Vacios); end if; Out_Ptr := (Out_Ptr + 1) mod N; Consumir 2; end loop; end Consumer2;

Fernando Cuartero

40

Problemas de los semáforos „

Considerar el siguiente código de un consumidor WAIT (LLENOS); WAIT (MUTEX); EXTRAER DATO DEL BUFFER; SIGNAL (MUTEX); SIGNAL (VACIOS);

¿Qué pasa si se invierte el orden de las operaciones wait?

octubre de 2006

Fernando Cuartero

41

Problemas de los semáforos „

Confusión de propósito Los semáforos se usan para varias tareas: Sincronización, Exclusión mutua, o asignación de recursos sin una indicación clara de su uso.

„

Escasa capacidad semántica El uso de las operaciones no es ilustrativo percibidas aisladamente

„

Propensión a errores Una simple alteración del orden de operaciones conduce fácilmente a una situación de deadlock

„

Acoplamiento innecesario Un par wait-signal de un semáforo puede estar intimamente relacionado con otro par sin una conexión obvia

„

Confusión en un número elevado La interacción de dos semáforos ya es complicada, la interacción de varios de ellos es un auténtico problema

octubre de 2006

Fernando Cuartero

42

El problema del barbero dormilón • Problema planteado por Dijkstra en 1971

• Una peluquería en la que hay un barbero, una silla de peluquero y N sillas para que se sienten los clientes en espera, si es que los hay. • Si no hay clientes presentes, el barbero se sienta en su silla de peluquero y se duerme. • Cuando llega un cliente, éste debe despertar al barbero dormilón. • Si llegan más clientes mientras el barbero corta el cabello de un cliente, se sientan (si hay sillas desocupadas) o salen de la peluquería (si todas las sillas están ocupadas). • Programar al barbero y los clientes. octubre de 2006

Fernando Cuartero

43

El problema del barbero dormilón

octubre de 2006

Fernando Cuartero

44

El problema del barbero dormilón • Problema: 1 barbero y N sillas de espera • Si un cliente entra y no hay sillas, se va • Semáforos: • clientes: número de clientes en espera sin contar el que está en la silla del peluquero • barberos: número de barberos inactivos (1 o 0) • mutex: exclusión mutua • Variable compartida: • esperando: número de clientes esperando • Inicialmente: • clientes=0 barberos=0 exmut=1 esperando=0

octubre de 2006

Fernando Cuartero

45

El problema del barbero dormilón Proceso Barbero begin loop Wait (clientes); Wait (mutex); esperando := esperando - 1; Signal (barberos); Signal (Mutex); Corta el pelo; end loop; end Consumer1;

octubre de 2006

Proceso Cliente begin loop if PELOLARGO then Wait (mutex); if esperando < SILLAS then esperando := esperando + 1; Signal (clientes); Signal (mutex); Wait(barberos); Corta el pelo; else Signal (mutex); end if; end if; end loop; end Cliente;

Fernando Cuartero

46