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) signal (s)

[Link]:=[Link]-1; [Link]:=[Link] +1;
if [Link]<0 then if [Link]<= 0 then
[Link](proceso); [Link](proceso);
bloquear; despertar(proceso):
end if; end if;

octubre de 2006 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 PROCESO 2
repeat repeat
sección no crítica 1 sección no crítica 2
wait(mutex) wait(mutex)
sección crítica 1 sección crítica 2
signal(mutex) signal(mutex)
forever forever

octubre de 2006 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 TWO;
task body TWO is
task ONE; begin
task body ONE is loop
begin WAIT (SCREEN);
loop PUT_LINE (“Tarea 2");
WAIT (SCREEN); SIGNAL (SCREEN);
PUT_LINE (“Tarea 1"); end loop;
SIGNAL (SCREEN); end TWO;
end loop;
end ONE; begin
INIT (SCREEN, 1);
end EXAMPLE;

octubre de 2006 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;
CAR_1 : CAR (5.0, 10.0);
task type CAR (START, PARK : DURATION); CAR_2 : CAR (10.0, 12.0);
task body CAR (START, PARK : DURATION) is CAR_3 : CAR (8.0, 10.0);
begin
delay (START); begin
WAIT (SPACES); INIT(SPACES, 2);
delay (PARK); end EXAMPLE;
SIGNAL (SPACES);
end CAR;

octubre de 2006 Fernando Cuartero 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

Dirección de
Datos almacenados Posición de los punteros 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 Proceso

Almacena dato Extrae dato

en el buffer del buffer

Avanza el Avanza el
puntero cabeza puntero cola
un espacio un espacio

octubre de 2006 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 Pausa

Si! Si!
Lleno? Vacío?

No! No!

Almacena dato Extrae dato

en el buffer del buffer

Avanza el Avanza el
puntero cabeza puntero cola
un espacio un espacio

octubre de 2006 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 begin
repeat repeat
producir elemento protocolo de entrada
protocolo de entrada extraer un elemento del buffer
insertar el elemento en el buffer protocolo de salida
protocolo de salida consumir el elemento
forever forever
end 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 proceso Consumidor

begin begin
repeat repeat
producir elemento wait (llenos)
wait (vacios) extraer un elemento del buffer
insertar el elemento en el buffer signal (vacios)
signal (llenos) consumir el elemento
forever forever
end end

octubre de 2006 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 proceso Consumidor
begin begin
repeat repeat
producir elemento wait (llenos)
wait (vacios) wait (mutex)
wait (mutex) extraer un elemento del buffer
insertar el elemento en el buffer signal (vacios)
signal (mutex) signal (mutex)
signal (llenos) consumir el elemento
forever forever
end end

octubre de 2006 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; task Consumer2;
B: array(0..N-1) of Integer;
In_Ptr, Out_Ptr: Integer := 0; begin
null;
Llenos: Semaphore := Init(0); end PCS;
Vacios: Semaphore := Init(N);
Mutex: 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 task body Consumer2 is

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

octubre de 2006 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;

procedure PCBS is task Producer;

task Consumer1;
N: constant Integer := 10; task Consumer2;
B: array(0..N-1) of Integer;
In_Ptr, Out_Ptr: Integer := 0; begin
Count: Integer := 0; 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 Count := Count + 1;

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

octubre de 2006 Fernando Cuartero 39

 El problema del
Productor-Consumidor

task body Consumer1 is task body Consumer2 is

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

octubre de 2006 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 Cliente
Proceso Barbero begin
loop
begin if PELOLARGO then
loop Wait (mutex);
Wait (clientes); if esperando < SILLAS then
Wait (mutex); esperando := esperando + 1;
Signal (clientes);
esperando := esperando - 1;
Signal (mutex);
Signal (barberos); Wait(barberos);
Signal (Mutex); Corta el pelo;
else Signal (mutex);
Corta el pelo; end if;
end loop; end if;
end Consumer1; end loop;
end Cliente;

octubre de 2006 Fernando Cuartero 46