PDF de programación - Semáforos

Semáforos

http://www.dc.fi.udc.es/ai/~soto/sist_oper/Semaforos.html

SEMAFOROS


1. DEFINICIONES

1.1. Semáforo general
1.2. Semáforo binario
1.3. Semáforo con cola de procesos bloqueados
1.4. Semáforo con espera activa (busy-wait)
1.5. Consecuencias de las anteriores definiciones

2. USOS DE LOS SEMAFOROS

2.1. Solucion al problema de la sección crítica

2.1.1. Solución con semáforos para 2 procesos
2.1.2. Solución con semáforos para n procesos

2.2. Implementación de un grafo de precedencia con semáforos

3. IMPLEMENTACIÓN DE LOS SEMÁFOROS

3.1. Implementaciones de semáforos con espera activa

3.1.1. Implementación del semáforo binario
3.1.2. Aproximaciones a la implementación del semáforo general
3.1.3. Implementación de Hemmendinger
3.1.4. Implementación de Kearns
3.1.5. Implementación mediante inhabilitación de interrupciones

3.2. Implementación con espera inactiva



1. DEFINICIONES

A continuación se presentan diversas definiciones de semáforos.

1.1. SEMÁFORO GENERAL

Un semáforo general S es una variable entera, inicializada a un valor no negativo, y a la que, aparte de su
inicialización, sólo se puede acceder por medio de dos operaciones atómicas P y V.



P(S)



V(S)

if S > 0 then S = S – 1
else suspender la ejecución del proceso


if hay procesos suspendidos en este semáforo
then despertar a uno de ellos
else S = S + 1



S es una variable compartida por los procesos.
La operación V despierta a uno de los procesos suspendidos pero no indica a cual.
Estas operaciones se realizan de forma atómica y esto tiene sus implicaciones:


· No hay modificación ni acceso simultáneo al semáforo.
· No hay posibilidad de entrelazado de instrucciones entre el chequeo del valor de S y su

posible modificación en una operación P o V.

· P y V son secciones críticas; pues son trozos de código donde se accede a variables

compartida



1 de 21

22/12/2007 21:48

Semáforos



http://www.dc.fi.udc.es/ai/~soto/sist_oper/Semaforos.html

1.2. SEMÁFORO BINARIO

Es un semáforo general pero sólo puede tomar valores 0 y 1.
En este caso las operaciones P y V se redefinen de la siguiente forma:



P(S)


V(S)


if S > 0 then S = S - 1
else suspender la ejecución del proceso

if hay procesos suspendidos en este semáforo
then despertar a uno de ellos
else S = 1



2 de 21

22/12/2007 21:48

Semáforos



http://www.dc.fi.udc.es/ai/~soto/sist_oper/Semaforos.html

1.3. SEMÁFORO CON COLA DE PROCESOS

BLOQUEADOS


En la definición de semáforo general no se especifica en que orden se despiertan los procesos
suspendidos, en este caso los procesos suspendidos se mantienen en una cola FIFO y se despiertan en el
orden en que fueron suspendidos



P(S)


V(S)

if S > 0 then S=S-1
else suspender la ejecución del proceso. // El proceso se inserta
al final de la cola FIFO

if hay procesos suspendidos en este semáforo
then despertar al que está al principio de la cola FIFO
else S=S+1



Se puede modificar la gestión utilizando una pila, un árbol, una cola con prioridades ... etc.


3 de 21

22/12/2007 21:48

Semáforos



http://www.dc.fi.udc.es/ai/~soto/sist_oper/Semaforos.html

1.4. SEMÁFORO CON ESPERA ACTIVA (BUSY-WAIT)



El proceso que no completa la operación P (por no ser positivo el valor del semáforo en el momento de
realizarla) no lo hace porque se mantiene en un bucle, de ahí que se denomine de espera activa.



P(S)


V(S)

loop // lazo
if S > 0 then
S=S-1;
exit; // sale del lazo
end if;
end loop;

S=S+1;


Comentarios:

· Dado que un bucle no puede ser atómico, consideraremos que no hay entrelazado de instrucciones

entre el chequeo del valor de S y posible decremento: if atómico. Posible entrelazado entre ciclos del
lazo.

· Incremento atómico de S en V(S)

4 de 21

22/12/2007 21:48

Semáforos



http://www.dc.fi.udc.es/ai/~soto/sist_oper/Semaforos.html

1.1. CONSECUENCIAS DE LAS ANTERIORES

DEFINICIONES


Consecuencias de interés que se derivan



1) S >= 0

2) S = S0 + NV - NP



Se deriva de la definición. Dado que el
semáforo está inicializado a un valor no
negativo y que la operación P solo disminuye
su valor cuando éste es mayor que 0 la
consecuencia es evidente.

Donde:


NV es el número de operaciones V
ejecutadas sobre S
NP es el número de operaciones P
completadas sobre S
S0 es el valor inicial del semáforo S



Si no hay procesos suspendidos la demostración es trivial

Si hay procesos suspendidos el valor del semáforo será 0 y el número de procesos que han completado una
operación P será el valor inicial del semáforo más el número de operaciones V realizadas.


5 de 21

22/12/2007 21:48

Semáforos



http://www.dc.fi.udc.es/ai/~soto/sist_oper/Semaforos.html

2. USOS DE LOS SEMAFOROS


Veremos dos utilidades de los semáforos:


1) Solución al problema de la sección crítica
2) Medio de implementar cualquier grafo de precedencia mediante la sentencia concurrente



2.1. SOLUCION AL PROBLEMA DE LA SECCIÓN

CRÍTICA


Las soluciones vistas hasta el momento (soluciones software) consistían en codificar adecuadamente las
secciones de entrada y de salida en el código de cada proceso Pi



begin
repeat
Sección de entrada
Sección crítica
Sección de salida
Sección restante
until false
end


Requerimiento a las soluciones

§ Exclusión mutua
§ Progreso
§ Espera limitada


Soluciones ya vistas:

Soluciones software

Para 2 procesos (Peterson) y n procesos (Lamport)

Soluciones con instrucciones hardware especiales

Para 2 procesos y n procesos (Burns)

Características de las soluciones vistas:

-Dificultades de conseguir soluciones que cumplan los tres requerimientos (secciones de entrada y
salida de difícil programación)

-Espera activa

6 de 21

22/12/2007 21:48

Semáforos

http://www.dc.fi.udc.es/ai/~soto/sist_oper/Semaforos.html

2.1.1. SOLUCIÓN CON SEMÁFOROS PARA 2 PROCESOS

Consideremos la siguiente solución con semáforos para el acceso a una sección crítica por dos procesos:



Código de P1
begin
repeat
P(S)
Sección crítica de P1
V(S)
Sección restante de P1
until false
end



Variables compartidas

S=1 // Inicialización



Código de P2
begin
repeat
P(S)
Sección crítica de P2
V(S)
Sección restante de P2
until false
end


Comprobación de la satisfacción de las tres condiciones:

Exclusión mutua
No puede haber más de un proceso en la sección crítica
Sea #SC número de procesos en la sección crítica.
#SC=NP-NV ya que por construcción de la solución estarán en la sección crítica los procesos que hayan
completado la operación P pero no hayan hecho todavía la operación V
Recordando que para todo semáforo tenemos que S = S0 + NV – NP
Llegamos a que #SC=So-S
y como el semáforo esta inicializado a 1
#SC=1-S,
Como S>=0
Llegamos a que #SC<=1 lo que demuestra que hay exclusión mutua (el número de procesos en la sección
crítica es siempre menor o igual que 1

Progreso
La opción de entrar en la sección crítica solo la tiene uno de los que solicita entrar y además es imposible
el interbloqueo (ambos procesos suspendidos en P(S) y ninguno en la sección crítica) ya que tendriamos:

S = 0
#SC = 0
S = 0 y #SC = 0

Por haber procesos suspendidos y
Ya que ninguno está en la sección crítica
Imposible por (e3)


Espera limitada
Supongamos que P1 quiere entrar en la sección crítica y P2 está en la sección crítica. Veremos que es
imposible que P2 entre de nuevo hasta que lo haya hecho P1:
Si P1 está suspendido, S = 0 y P2 en su sección crítica. Cuando P2 sale, ejecuta V(S) y despierta el
proceso suspendido (dejando S=0). Despierta P1 y P1 entra, P2 no podrá entrar hasta que lo haya hecho P1
Vemos que la condición de espera limitada no se satisfaría si el semáforo fuese con espera activa, ya que
sería posible que P2 saliese de su sección restante ejecutase V(S) (dejando S=1) y volviese a entrar


7 de 21

22/12/2007 21:48

Semáforos

http://www.dc.fi.udc.es/ai/~soto/sist_oper/Semaforos.html

2.1.2. SOLUCIÓN CON SEMÁFOROS PARA N PROCESOS

La forma de la solución se generaliza para N procesos



S = 1 // Inicialización

Código de Pi

begin
repeat
P(S)
Sección crítica de Pi
V(S)
Sección restante de Pi
until false
end


§ Satisface las exigencias de exclusión mutua y progreso
§ La satisfacción de espera limitada depende del tipo de semáforo
§ Para un semáforo con espera activa no se satisface el requerimiento de espera limitada

Se demuestra viendo que es posible la postergación indefinida de un proceso. Considérese la siguiente
secuencia de ejecución:

1. P1 ejecuta P(S) y entra en su sección crítica
2. P2 encuentra S=0 y se queda en el lazo de la operación P (el semáforo es de espera activa).
3. P1 completa un ciclo (protocolo de salida, sección restante, protocolo de entrada) y vuelve a

entrar en la sección crítica

4. P2 encuentra S=0 y se queda en el lazo

Esta secuencia puede repetirse indefinidamente causando la postergación de P2.

§ Para un semáforo con cola de procesos bloqueados se satisface el requerimiento de espera limitada

Suponer P1 bloqueado en S. Habrá como máximo N-1 procesos delante de P1 en la cola d S. P1
entrará en su sección crítica después de un máximo de N-1 ejecuciones de P(S)

§ Para un semáforo con conjunto de procesos bloqueados no se satisface el requerimiento de espera

limitada con N>=3

Se demuestr