Sistemas

Operativos
UNIDAD 3
EXCLUSIÓN MUTUA Y SINCRONIZACIÓN
CON SEMÁFOROS

SISTEMAS OPERATIVOS - SEMÁFOROS

… ya sabemos que …
Sección Crítica
Es la zona de código (de un proceso) donde se accede a los recursos compartidos (con otros procesos)
y que no puede ser ejecutada cuando otro proceso esté en la misma sección crítica.

Dos zonas de código (en procesos distintos) diremos que son la misma sección crítica
si acceden a los mismos recursos compartidos (a todos o a algunos)

SISTEMAS OPERATIVOS - SEMÁFOROS

… ya sabemos que …
Sección Crítica
Es la zona de código (de un proceso) donde se accede a los recursos compartidos (con otros procesos)
y que no puede ser ejecutada cuando otro proceso esté en la misma sección crítica.

Dos zonas de código (en procesos distintos) diremos que son la misma sección crítica
si acceden a los mismos recursos compartidos (a todos o a algunos)

Exclusión Mutua
Es el requisito que garantiza que dos procesos, que comparten secciones críticas, no
pueden ejecutar simultáneamente dentro de ellas.

SISTEMAS OPERATIVOS - SEMÁFOROS

… ya sabemos que …
Sección Crítica
Es la zona de código (de un proceso) donde se accede a los recursos compartidos (con otros procesos)
y que no puede ser ejecutada cuando otro proceso esté en la misma sección crítica.

Dos zonas de código (en procesos distintos) diremos que son la misma sección crítica
si acceden a los mismos recursos compartidos (a todos o a algunos)

Exclusión Mutua
Es el requisito que garantiza que dos procesos, que comparten secciones críticas, no
pueden ejecutar simultáneamente dentro de ellas.

Soluciones para garantizar la Exclusión Mutua

Soportadas por el Hardware
• Instrucciones hardware atómicas (Test & Set, Exchange)
• Inhabilitación de Interrupciones
Soportadas por el Sistema Operativo y lenguajes de programación
• Semáforos
• Monitores
• Paso de Mensajes

SISTEMAS OPERATIVOS - SEMÁFOROS

Índice
• Concepto de Semáforo
• Implementación por parte del Sistema Operativo
• Tipos de Semáforos
• Binarios/Enteros
• Fuertes/Débiles
• Exclusión mutua con Semáforos
• El problema del Productor Consumidor con Buffer Ilimitado
• Paso a paso  Con semáforos binarios
• Los “roles” de los semáforos
• Con semáforos Enteros
• Conclusiones y estrategias
• El problema del Productor Consumidor con Buffer Limitado
• Un problema de examen
• Barreras

SISTEMAS OPERATIVOS - SEMÁFOROS

Concepto de Semáforo
• Es un mecanismo basado en señales entre procesos para poder sincronizarse.
• El semáforo lo crea el sistema operativo a petición de un proceso y se puede compartir.
• Los procesos pueden enviar y recibir señales a y del semáforo

P1 P2

S
OK
Ocupado!

SISTEMAS OPERATIVOS - SEMÁFOROS

Concepto de Semáforo
• Es un mecanismo basado en señales entre procesos para poder sincronizarse.
• El semáforo lo crea el sistema operativo a petición de un proceso y se puede compartir.
• Los procesos pueden enviar y recibir señales a y del semáforo

P1 P2
Gracias!
OK
S

SISTEMAS OPERATIVOS - SEMÁFOROS

Concepto de Semáforo
• Es un mecanismo basado en señales entre procesos para poder sincronizarse.
• El semáforo lo crea el sistema operativo a petición de un proceso y se puede compartir.
• Los procesos pueden enviar y recibir señales a y del semáforo

Sobe un semáforo sólo se pueden hacer tres operaciones.

• Para inicializar el semáforo llamamos a init(S,valor)
• Para recibir una señal (vía el semáforo S) llamamos a wait(S)
• Para transmitir una señal (vía el semáforo S) llamamos a signal(S)

init, wait y signal son llamadas al sistema

• El semáforo lo gestiona el S.O. por eso hay que hacer llamadas al sistema.

P1 P2 P3

wait(S)
S

P2 P3 Todo semáforo tiene asociada una cola

Cola de procesos bloqueados en S donde se bloquean los procesos

SISTEMAS OPERATIVOS - SEMÁFOROS

Concepto de Semáforo
• Es un mecanismo basado en señales entre procesos para poder sincronizarse.
• El semáforo lo crea el sistema operativo a petición de un proceso y se puede compartir.
• Los procesos pueden enviar y recibir señales a y del semáforo

Sobe un semáforo sólo se pueden hacer tres operaciones.

• Para inicializar el semáforo llamamos a init(S,valor)
• Para recibir una señal (vía el semáforo S) llamamos a wait(S)
• Para transmitir una señal (vía el semáforo S) llamamos a signal(S)

init, wait y signal son llamadas al sistema

• El semáforo lo gestiona el S.O. por eso hay que hacer llamadas al sistema.

P1 P2 P3

signal(S) S

P2 P3 Todo semáforo tiene asociada una cola

Cola de procesos bloqueados en S donde se bloquean los procesos

SISTEMAS OPERATIVOS - SEMÁFOROS

Concepto de Semáforo
• Es un mecanismo basado en señales entre procesos para poder sincronizarse.
• El semáforo lo crea el sistema operativo a petición de un proceso y se puede compartir.
• Los procesos pueden enviar y recibir señales a y del semáforo

• Sobre un semáforo sólo se pueden hacer tres operaciones.

• Para inicializar el semáforo llamamos a init(S,valor)
• Para recibir una señal (vía el semáforo S) llamamos a wait(S)
• Para transmitir una señal (vía el semáforo S) llamamos a signal(S)
• init, wait y signal son llamadas al sistema
• El semáforo lo gestiona el S.O. por eso hay que hacer llamadas al sistema.
• Todo semáforo tiene asociada una cola donde se bloquean los procesos

P1 P2 P3

P3
Cola de procesos bloqueados en S

SISTEMAS OPERATIVOS - SEMÁFOROS

Concepto de Semáforo
Desde el punto de vista del programador:
• Una variable (del sistema) que contiene un valor entero
• sobre el cual sólo se pueden realizar tres operaciones
1. init (crearlo) con un valor entero no negativo ( crea S >=0 )
2. wait decrementa el valor del semáforo ( S = S-1 )
3. signal incrementa el valor del semáforo ( S = S+1 )

Por ejemplo: ¿Cómo se bloquean y desbloquean

los procesos en la cola?
Semaphore S = 0; wait(S) si S queda en negativo ( S<0 )  SE BLOQUEA
S = 0 wait(S)  S = -1 sino  CONTINUA (entraría en la Sección Crítica)
S = -1 signal(S)  S = 0
S = 0 signal(S)  S = 1 signal(S) si S queda <= 0  LIBERAMOS DE LA COLA
S = 1 signal(S)  S = 2 si S > 0 … pues nada, queda incrementado
S = 2 wait(S)  S = 1

SISTEMAS OPERATIVOS - SEMÁFOROS

Concepto de Semáforo
Desde el punto de vista del programador:
• Una variable (del sistema) que contiene un valor entero
• sobre el cual sólo se pueden realizar tres operaciones
1. init (crearlo) con un valor entero no negativo ( crea S >=0 )
2. wait decrementa el valor del semáforo ( S = S-1 )
3. signal incrementa el valor del semáforo ( S = S+1 )

Desde el punto de vista del proceso: (se ve más fácil)

Por ejemplo: ¿Cómo se bloquean y desbloquean

los procesos en la cola?
Semaphore S = 0; wait(S) Si puedo entrar, Paso, sino me Bloqueo
S = 0 wait(S)  S = -1
S = -1 signal(S)  S = 0
S = 0 signal(S)  S = 1
S = 1 signal(S)  S = 2 signal(S) Yo Sigo, y si hay alguien bloqueado se Desbloquea
S = 2 wait(S)  S = 1

SISTEMAS OPERATIVOS - SEMÁFOROS

 S = S-1  wait(S) Si puedo entrar, Paso, sino me Bloqueo
Concepto de Semáforo si queda S<0

S = S+1  signal(S) Yo Sigo, y si hay alguien bloqueado se Desbloquea

¿Inicializamos S=0 o a S=1? ¿Para que sirve inicializar S>0?

Si inicializamos a 0 entonces el primer wait(S)  S = -1  Se bloquea
¡No pasa ni el primero que llegue!

Si inicializamos a 1 entonces el primer wait(S)  S =0  Pasa

¡Sólo pasa el primero! el segundo wait(S)  S= -1  Se bloquea

Si inicializamos a 3 entonces el primer wait(S)  S =2  Pasa

¡Pasan los 3 primeros! el segundo wait(S)  S= 1  Pasa
¡El cuarto se bloquea! el tercer wait(S)  S=0  Pasa
el cuarto wait(S)  S=-1  Se Bloquea

Falta uno para

de uno en usarlo !!!
uno !!!

SISTEMAS OPERATIVOS - SEMÁFOROS

 S = S-1  wait(S) Si puedo entrar, Paso, sino me Bloqueo
Concepto de Semáforo si queda S<0

S = S+1  signal(S) Yo Sigo, y si hay alguien bloqueado se Desbloquea

 S = S-1  wait(S) Si puedo entrar, Paso, sino me Bloqueo
Implementación si queda S<0

S = S+1  signal(S) Yo Sigo, y si hay alguien bloqueado se Desbloquea

Es una estructura con

un valor (contador) y una cola
Dos operaciones, wait y signal

wait decrementa
y si <0 Bloquea
sino, Pasa

signal incrementa
Si queda alguien lo Desbloquea

La Lista de Listos del SO es donde

están los procesos que están
preparados para tomar la CPU
 S = S-1  wait(S) Si puedo entrar, Paso, sino me Bloqueo
Implementación si queda S<0

S = S+1  signal(S) Yo Sigo, y si hay alguien bloqueado se Desbloquea

Es una estructura con

un valor (contador) y una cola
Dos operaciones, wait y signal

wait decrementa
y si <0 Bloquea
sino, Pasa

signal incrementa
Si queda alguien lo Desbloquea
¿Qué pasa en el sistema
cuando un proceso se bloquea?

Que el planificador de procesos

selecciona uno de la Lista de Listos
y le asigna el procesador
Tipos de Semáforos
• SEMÁFOROS “GENERALES” o “CON CONTADOR” o “ENTEROS”
• SEMÁFOROS “BINARIOS”

SISTEMAS OPERATIVOS - SEMÁFOROS

Tipos de Semáforos
• SEMÁFOROS “GENERALES” o “CON CONTADOR” o “ENTEROS”
• SEMÁFOROS “BINARIOS”

El valor del semáforos solo

puede ser 0 o 1

wait
si es 1 lo pone a 0 y Pasa
sino lo deja en 0 y Bloquea al proceso

signal
Si la cola está vacía lo pone a 1
sino Desbloquea a uno de la cola
(y Pasa)

SISTEMAS OPERATIVOS - SEMÁFOROS

Tipos de Semáforos
• SEMÁFOROS FUERTES
• SEMÁFOROS DÉBILES
Te toca
SEMÁFORO FUERTE SEMÁFORO DÉBIL
a ti
S S

P3 P2 P0 P7 P3 P2 P0 P7
Cola de procesos bloqueados en S Cola de procesos bloqueados en S

Planificación de la Cola Planificación de la Cola

FIFO mediante alguna política
(First In – First Out) de planificación

Los habituales en la Pueden causar Inanición

mayoría de los S.O. La Inanición
Es un problema en sistemas multitarea, donde a
Están libres de Inanición un proceso o un hilo de ejecución se le deniega
siempre el acceso a un recurso compartido.
Sin este recurso, la tarea sigue bloqueada y
no puede ser nunca finalizada.

SISTEMAS OPERATIVOS - SEMÁFOROS

Exclusión mutua con Semáforos
• Tenemos n procesos identificados como P(1), P(2) … P(n) u otros distintos Q …
• Todos necesitan acceder a los mismos recursos
• Cada proceso tiene una sección crítica que accede a los recursos

Claves para cumplir la exclusión mutua

• Declarar un semáforo s compartido para
Q regular el acceso a la sección crítica común

En cada proceso:

• Ejecuta wait(s) antes de entrar

en la sección crítica
• Ejecuta signal(s) al salir
de la sección crítica
• La inicialización depende del problema
,Q(1),Q(2));
• s=1 si sólo puede entrar un proceso a la vez
• s=m si pueden entrar m procesos a la vez
• s=0 si algún otro proceso habilita el paso a
todos los procesos (levanta la barrera)

SISTEMAS OPERATIVOS - SEMÁFOROS

 El problema del Productor-Consumidor
Hay uno o más procesos generando algún tipo de datos (registros, caracteres, objetos,
etc.) y colocándolos en un buffer. Hay un único consumidor que está extrayendo datos
del buffer. El sistema debe garantizar que se impida la superposición de operaciones
sobre los datos.
Es decir, sólo un agente (productor o consumidor), puede acceder al mismo tiempo.
… no nos dicen nada acerca del tamaño del buffer… pensemos que es infinito

SISTEMAS OPERATIVOS - SEMÁFOROS

 El problema del Productor-Consumidor
Hay uno o más procesos generando algún tipo de datos (registros, caracteres, objetos,
etc.) y colocándolos en un buffer. Hay un único consumidor que está extrayendo datos
del buffer. El sistema debe garantizar que se impida la superposición de operaciones
sobre los datos.
Es decir, sólo un agente (productor o consumidor), puede acceder al mismo tiempo.
… no nos dicen nada acerca del tamaño del buffer… pensemos que es infinito

/* program productor-consumidor*/ //Morris Lester Szyslak (Moe) //Homer Jay Simpson (Homer)
int n; //Número de elementos producidos
void productor(int n){ void consumidor(int n){
while (true){ while (true){
producir(); extraer();
añadir(); n--;
n++; consumir();
} }
} }
n es compartida !!!
pero tengo que
proteger también las
acciones de añadir y
de extraer
es decir,
Los accesos al buffer

void main(){
n=0;
paralelos(productor(1),productor(2), consumidor(1));
}
 El problema del Productor-Consumidor
Hay uno o más procesos generando algún tipo de datos (registros, caracteres, objetos,
etc.) y colocándolos en un buffer. Hay un único consumidor que está extrayendo datos
del buffer. El sistema debe garantizar que se impida la superposición de operaciones
sobre los datos.
Es decir, sólo un agente (productor o consumidor), puede acceder al mismo tiempo.
… no nos dicen nada acerca del tamaño del buffer… pensemos que es infinito

/* program productor-consumidor*/ //Morris Lester Szyslak (Moe) //Homer Jay Simpson (Homer)
int n; //Número de elementos producidos
BinSemaphore s=1; void productor(int n){ void consumidor(int n){
while (true){ while (true){
producir(); wait(s);
extraer();
añadir();
wait(s); n--;extraer();
n++;añadir(); n--;
consumir();
} n++; } signal(s);
} signal(s); } consumir();
} }
} }

void main(){
n=0; wait
paralelos(productor(1),productor(2), consumidor(1)); si es 1 lo pone a 0 y Pasa
} si es 0 lo deja en 0 y Bloquea al proceso

signal
Si la cola está vacía lo pone a 1
sino Desbloquea a uno de la cola
(y continúa)
 El problema del Productor-Consumidor
Hay uno o más procesos generando algún tipo de datos (registros, caracteres, objetos,
etc.) y colocándolos en un buffer. Hay un único consumidor que está extrayendo datos
del buffer. El sistema debe garantizar que se impida la superposición de operaciones
sobre los datos.
Es decir, sólo un agente (productor o consumidor), puede acceder al mismo tiempo.
… no nos dicen nada acerca del tamaño del buffer… pensemos que es infinito
¿Y si el consumidor llega primero? ¿Y si el consumidor va más rápido?
/* program productor-consumidor*/ //Morris Lester Szyslak (Moe) //Homer Jay Simpson (Homer)
int n; //Número de elementos producidos
BinSemaphore s=1; void productor(int n){ void consumidor(int n){
while (true){ while (true){
producir(); wait(s);
extraer();
añadir();
wait(s); n--;extraer();
n++;añadir(); n--;
consumir();
} n++; } signal(s);
} signal(s); } consumir();
} }
} }

void main(){
n=0; wait
paralelos(productor(1),productor(2), consumidor(1)); si es 1 lo pone a 0 y Pasa
} si es 0 lo deja en 0 y Bloquea al proceso

signal
Si la cola está vacía lo pone a 1
sino Desbloquea a uno de la cola
(y continúa)
¿Semáforos? … Un juego de Rol
Podemos pensar que :
los semáforos juegan dos roles distintos

• Un rol MUTEX , para garantizar la exclusión

mutua, protegiendo la sección crítica
Clancy Wiggum

• Un rol SINCRO , para sincronizar los procesos

(ajustar su velocidad relativa, “que se lleven bien”)
Nedwar ( Ned ) Flanders

SISTEMAS OPERATIVOS - SEMÁFOROS

 El problema del Productor-Consumidor
Hay uno o más procesos generando algún tipo de datos (registros, caracteres, objetos,
etc.) y colocándolos en un buffer. Hay un único consumidor que está extrayendo datos
del buffer. El sistema debe garantizar que se impida la superposición de operaciones
sobre los datos.
Es decir, sólo un agente (productor o consumidor), puede acceder al mismo tiempo.
… no nos dicen nada acerca del tamaño del buffer… pensemos que es infinito

/* program productor-consumidor*/ //Morris Lester Szyslak (Moe) //Homer Jay Simpson (Homer)
int n; //Número de elementos producidos
BinSemaphore s=1; //MUTEX void productor(int n){ void consumidor(int n){
BinSemaphore retardo=0; //SINCRO while (true){ wait(retardo);
while (true){
producir(); while (true){
wait(s);
wait(s); wait(s);
extraer();
añadir(); extraer();
n--;
n++; n--;
signal(s);
if (n==1)
signal(s); signal(s);
consumir();
} signal(retardo) } consumir();
} signal(s); } }
} }
}

void main(){
n=0; wait
paralelos(productor(1),productor(2), consumidor(1)); si es 1 lo pone a 0 y Pasa
} si es 0 lo deja en 0 y Bloquea al proceso

signal
Si la cola está vacía lo pone a 1
sino Desbloquea a uno de la cola
(y continúa)
 El problema del Productor-Consumidor
Hay uno o más procesos generando algún tipo de datos (registros, caracteres, objetos,
etc.) y colocándolos en un buffer. Hay un único consumidor que está extrayendo datos
del buffer. El sistema debe garantizar que se impida la superposición de operaciones
sobre los datos.
Es decir, sólo un agente (productor o consumidor), puede acceder al mismo tiempo.
… no nos dicen nada acerca del tamaño del buffer… pensemos que es infinito

/* program productor-consumidor*/ //Morris Lester Szyslak (Moe) //Homer Jay Simpson (Homer)
int n; //Número de elementos producidos
BinSemaphore s=1; //MUTEX void productor(int n){ void consumidor(int n){
BinSemaphore retardo=0; //SINCRO while (true){ wait(retardo);
producir(); while (true){
wait(s); wait(s);
añadir(); extraer();
n++; n--;
if (n==1) signal(s);
signal(retardo) consumir();
signal(s); } if (n==0)
} } wait(retraso);
} }
}

void main(){
n=0; wait
paralelos(productor(1),productor(2), consumidor(1)); si es 1 lo pone a 0 y Pasa
} si es 0 lo deja en 0 y Bloquea al proceso

signal
Si la cola está vacía lo pone a 1
sino Desbloquea a uno de la cola
(y continúa)
 El problema del Productor-Consumidor
Hay uno o más procesos generando algún tipo de datos (registros, caracteres, objetos,
etc.) y colocándolos en un buffer. Hay un único consumidor que está extrayendo datos
del buffer. El sistema debe garantizar que se impida la superposición de operaciones
sobre los datos.
Es decir, sólo un agente (productor o consumidor), puede acceder al mismo tiempo.
… no nos dicen nada acerca del tamaño del buffer… pensemos que es infinito

/* program productor-consumidor*/ //Morris Lester Szyslak (Moe) //Homer Jay Simpson (Homer)
int n; //Número de elementos producidos
BinSemaphore s=1; //MUTEX void productor(int n){ void consumidor(int n){
BinSemaphore retardo=0; //SINCRO while (true){ wait(retardo);
producir(); while (true){
wait(s); wait(s);
añadir(); extraer();
n++; n--;
if (n==1) signal(s);
signal(retardo) consumir();
signal(s); if (n==0)
} wait(retraso);
} }
}

void main(){
n=0; wait
paralelos(productor(1),productor(2), consumidor(1)); si es 1 lo pone a 0 y Pasa
} si es 0 lo deja en 0 y Bloquea al proceso

signal
Si la cola está vacía lo pone a 1
sino Desbloquea a uno de la cola
(y continúa)
 El problema del Productor-Consumidor
Hay uno o más procesos generando algún tipo de datos (registros, caracteres, objetos,
etc.) y colocándolos en un buffer. Hay un único consumidor que está extrayendo datos
del buffer. El sistema debe garantizar que se impida la superposición de operaciones
sobre los datos.
Es decir, sólo un agente (productor o consumidor), puede acceder al mismo tiempo.
Instrucción Productor Consumidor s n retraso
1 1 0 0 /* program productor-consumidor*/
2 wait(s) 0 0 0 int n; //Número de elementos producidos
3 añadir() 0 0 0
BinSemaphore s=1; //MUTEX
4 n++ 0 1 0
if (n==1) BinSemaphore retardo=0; //SINCRO
5 0 1 1
signal(retraso)
6 signal(s) 1 1 1
7 producir() 1 1 1
8 wait(retraso) 1 1 0 //Morris Lester Szyslak (Moe) //Homer Jay Simpson (Homer)
9 wait(s) 0 1 0
10 extraer(); 0 1 0
11 n--; 0 0 0
void productor(int n){ void consumidor(int n){
12 signal(s) 1 0 0 while (true){ wait(retardo);
13 consumir(); 1 0 0 producir(); while (true){
14 wait(s) 0 0 0 wait(s); wait(s);
15 añadir() 0 0 0
16 n++ 0 1 0
añadir(); extraer();
if (n==1) n++; n--;
17 0 1 1
signal(retraso) if (n==1) signal(s);
18 signal(s) 1 1 1 signal(retardo) consumir();
if (n==0)
19 1 1 1 signal(s); if (n==0)
wait(retraso)
20 wait(s) 0 1 1 } wait(retraso);
21 extraer(); 0 1 1 } }
22 n--; 0 0 1 }
23 signal(s) 1 0 1
24 consumir(); 1 0 1
if (n==0)
25 1 0 0
wait(retraso) void main(){ wait
26 wait(s) 0 0 0 n=0; si es 1 lo pone a 0 y Pasa
27 extraer(); 0 0 0
paralelos(productor(1),productor(2), consumidor(1)); si es 0 lo deja en 0 y Bloquea al proceso
28 n--; 0 -1 0
29 signal(s) 1 -1 0
}
signal
Si la cola está vacía lo pone a 1
sino Desbloquea a uno de la cola
(y continúa)
 El problema del Productor-Consumidor
Hay uno o más procesos generando algún tipo de datos (registros, caracteres, objetos,
etc.) y colocándolos en un buffer. Hay un único consumidor que está extrayendo datos
del buffer. El sistema debe garantizar que se impida la superposición de operaciones
sobre los datos.
Es decir, sólo un agente (productor o consumidor), puede acceder al mismo tiempo.
Instrucción Productor Consumidor s n retraso
1 1 0 0 /* program productor-consumidor*/ ¡¡¡¡ Las consultas a elementos
2 wait(s) 0 0 0 int n; //Número de elementos producidos
3 añadir() 0 0 0
BinSemaphore s=1; //MUTEX compartidos deben estar
4 n++ 0 1 0
5
if (n==1)
0 1 1
BinSemaphore retardo=0; //SINCRO también protegidas por un
6
signal(retraso)
signal(s) 1 1 1
MUTEX !!!!
7 producir() 1 1 1
8 wait(retraso) 1 1 0 //Morris Lester Szyslak (Moe) //Homer Jay Simpson (Homer)
9 wait(s) 0 1 0
10 extraer(); 0 1 0
11 n--; 0 0 0
void productor(int n){ void consumidor(int n){
12 signal(s) 1 0 0 while (true){ wait(retardo);
13 consumir(); 1 0 0 producir(); while (true){
14 wait(s) 0 0 0 wait(s); wait(s);
15 añadir() 0 0 0
añadir(); extraer();
16 n++ 0 1 0
if (n==1) n++; n--;
17 0 1 1
signal(retraso) if (n==1) signal(s);
18 signal(s) 1 1 1 signal(retardo) consumir();
consumir();
if (n==0)
19 1 1 1 signal(s); if (n==0)
wait(retraso)
20 wait(s) 0 1 1 } wait(retraso);
21 extraer(); 0 1 1 } Mientras consumíamos se nos ha }
22 n--; 0 0 1 colado un productor que nos ha }
23 signal(s) 1 0 1 cambiado la n
24 consumir(); 1 0 1 y la consultamos después para
if (n==0)
25 1 0 0 ver si sincronizamos…
wait(retraso) void main(){ wait
26 wait(s) 0 0 0 n=0; si es 1 lo pone a 0 y Pasa
27 extraer(); 0 0 0
paralelos(productor(1),productor(2), consumidor(1)); si es 0 lo deja en 0 y Bloquea al proceso
28 n--; 0 -1 0
29 signal(s) 1 -1 0
}
signal
Si la cola está vacía lo pone a 1
sino Desbloquea a uno de la cola
(y continúa)
 El problema del Productor-Consumidor
Hay uno o más procesos generando algún tipo de datos (registros, caracteres, objetos,
etc.) y colocándolos en un buffer. Hay un único consumidor que está extrayendo datos
del buffer. El sistema debe garantizar que se impida la superposición de operaciones
sobre los datos.
Es decir, sólo un agente (productor o consumidor), puede acceder al mismo tiempo.
Instrucción Productor Consumidor s n retraso
1 1 0 0 /* program productor-consumidor*/
2 wait(s) 0 0 0 int n; //Número de elementos producidos
3
4
añadir()
n++
0
0
0
1
0
0
BinSemaphore s=1; //MUTEX
BinSemaphore retardo=0; //SINCRO
¿cómo lo arreglamos?
if (n==1)
5 0 1 1
signal(retraso)
6 signal(s) 1 1 1
7 producir() 1 1 1
8 wait(retraso) 1 1 0 //Morris Lester Szyslak (Moe) //Homer Jay Simpson (Homer)
9 wait(s) 0 1 0
10 extraer(); 0 1 0
11 n--; 0 0 0
void productor(int n){ void consumidor(int n){
12 signal(s) 1 0 0 while (true){ wait(retardo);
13 consumir(); 1 0 0 producir(); while (true){
14 wait(s) 0 0 0 wait(s); wait(s);
15 añadir() 0 0 0
16 n++ 0 1 0
añadir(); extraer();
if (n==1) n++; n--;
17 0 1 1
signal(retraso) if (n==1) signal(s);
18 signal(s) 1 1 1 signal(retardo) consumir();
if (n==0)
19 1 1 1 signal(s); if (n==0)
wait(retraso)
20 wait(s) 0 1 1 } wait(retraso);
21 extraer(); 0 1 1 } }
22 n--; 0 0 1 }
23 signal(s) 1 0 1
24 consumir(); 1 0 1
if (n==0)
25 1 0 0
wait(retraso) void main(){ wait
26 wait(s) 0 0 0 n=0; si es 1 lo pone a 0 y Pasa
27 extraer(); 0 0 0
paralelos(productor(1),productor(2), consumidor(1)); si es 0 lo deja en 0 y Bloquea al proceso
28 n--; 0 -1 0
29 signal(s) 1 -1 0
}
signal
Si la cola está vacía lo pone a 1
sino Desbloquea a uno de la cola
(y continúa)
 El problema del Productor-Consumidor
Hay uno o más procesos generando algún tipo de datos (registros, caracteres, objetos,
etc.) y colocándolos en un buffer. Hay un único consumidor que está extrayendo datos
del buffer. El sistema debe garantizar que se impida la superposición de operaciones
sobre los datos.
Es decir, sólo un agente (productor o consumidor), puede acceder al mismo tiempo.
Instrucción Productor Consumidor s n retraso
1 1 0 0 /* program productor-consumidor*/
2 wait(s) 0 0 0 int n; //Número de elementos producidos
3 añadir() 0 0 0
BinSemaphore s=1; //MUTEX
4 n++ 0 1 0
if (n==1) BinSemaphore retardo=0; //SINCRO
5 0 1 1
signal(retraso)
6 signal(s) 1 1 1
7 producir() 1 1 1
8 wait(retraso) 1 1 0 //Morris Lester Szyslak (Moe) //Homer Jay Simpson (Homer)
9 wait(s) 0 1 0
10 extraer(); 0 1 0
11 n--; 0 0 0
void productor(int n){ void consumidor(int n){
12 signal(s) 1 0 0 while (true){ wait(retardo);
13 consumir(); 1 0 0 producir(); while (true){
14 wait(s) 0 0 0 wait(s); wait(s);
15 añadir() 0 0 0
16 n++ 0 1 0
añadir(); extraer();
if (n==1) n++; n--;
17 0 1 1
signal(retraso) if (n==1) signal(s);
18 signal(s) 1 1 1 signal(retardo) consumir();
if (n==0)
19 1 1 1 signal(s); wait(s)
wait(retraso)
20 wait(s) 0 1 1 } if (n==0)
21 extraer(); 0 1 1 } signal(s)
22 n--; 0 0 1 wait(retraso);
23 signal(s) 1 0 1 }
24 consumir(); 1 0 1
if (n==0)
}
25 1 0 0
wait(retraso) void main(){
26 wait(s) 0 0 0 n=0; wait
27 extraer(); 0 0 0 si es 1 lo pone a 0 y Pasa
paralelos(productor(1),productor(2), consumidor(1));
28 n--; 0 -1 0 si es 0 lo deja en 0 y Bloquea al proceso
29 signal(s) 1 -1 0
}
signal
Si la cola está vacía lo pone a 1
sino Desbloquea a uno de la cola
(y continúa)
 El problema del Productor-Consumidor
Hay uno o más procesos generando algún tipo de datos (registros, caracteres, objetos,
etc.) y colocándolos en un buffer. Hay un único consumidor que está extrayendo datos
del buffer. El sistema debe garantizar que se impida la superposición de operaciones
sobre los datos.
Es decir, sólo un agente (productor o consumidor), puede acceder al mismo tiempo.
Instrucción Productor Consumidor s n retraso
1 1 0 0 /* program productor-consumidor*/
2 wait(s) 0 0 0 int n; //Número de elementos producidos
3 añadir() 0 0 0
BinSemaphore s=1; //MUTEX
4 n++ 0 1 0
if (n==1) BinSemaphore retardo=0; //SINCRO
5 0 1 1
signal(retraso)
6 signal(s) 1 1 1
7 producir() 1 1 1
8 wait(retraso) 1 1 0 //Morris Lester Szyslak (Moe) //Homer Jay Simpson (Homer)
9 wait(s) 0 1 0
10 extraer(); 0 1 0
11 n--; 0 0 0
void productor(int n){ void consumidor(int n){
12 signal(s) 1 0 0 while (true){ wait(retardo);
13 consumir(); 1 0 0 producir(); while (true){
14 wait(s) 0 0 0 wait(s); wait(s);
15 añadir() 0 0 0
16 n++ 0 1 0
añadir(); extraer();
if (n==1) n++; n--;
17 0 1 1
signal(retraso) if (n==1) signal(s);
18 signal(s) 1 1 1 signal(retardo) consumir();
if (n==0)
19 1 1 1 signal(s); wait(s)
wait(retraso)
20 wait(s) 0 1 1 } if (n==0)
21 extraer(); 0 1 1 } wait(retraso);
22 n--; 0 0 1 signal(s)
23 signal(s) 1 0 1 }
24 consumir(); 1 0 1
if (n==0)
}
25 1 0 0
wait(retraso) void main(){
26 wait(s) 0 0 0 n=0; wait
27 extraer(); 0 0 0 si es 1 lo pone a 0 y Pasa
paralelos(productor(1),productor(2), consumidor(1));
28 n--; 0 -1 0 si es 0 lo deja en 0 y Bloquea al proceso
29 signal(s) 1 -1 0
}
signal
Si la cola está vacía lo pone a 1
sino Desbloquea a uno de la cola
(y continúa)
 El problema del Productor-Consumidor
Hay uno o más procesos generando algún tipo de datos (registros, caracteres, objetos,
etc.) y colocándolos en un buffer. Hay un único consumidor que está extrayendo datos
del buffer. El sistema debe garantizar que se impida la superposición de operaciones
sobre los datos.
Es decir, sólo un agente (productor o consumidor), puede acceder al mismo tiempo.
Instrucción Productor Consumidor s n retraso
1 1 0 0 /* program productor-consumidor*/
2 wait(s) 0 0 0 int n; //Número de elementos producidos
3 añadir() 0 0 0
BinSemaphore s=1; //MUTEX
4 n++ 0 1 0
if (n==1) BinSemaphore retardo=0; //SINCRO
5 0 1 1
signal(retraso)
6 signal(s) 1 1 1
7 producir() 1 1 1
8 wait(retraso) 1 1 0 //Morris Lester Szyslak (Moe) //Homer Jay Simpson (Homer)
9 wait(s) 0 1 0
10
11
extraer();
n--;
0
0
1
0
0
0
¿¿¡¡ UN WAIT DENTRO
void productor(int n){ DE UNA
void consumidor(int n){
12
13
signal(s)
consumir();
1
1
0
0
0
0
while (true){
producir();
SECCIÓN CRITICA!!??
wait(retardo);
while (true){
14
15
wait(s)
añadir()
0
0
0
0
0
0
wait(s); Peor aún  INTERBLOQUEO
añadir();
wait(s);
extraer();
16 n++ 0 1 0
if (n==1) n++; n--;
17 0 1 1
signal(retraso) if (n==1) signal(s);
18 signal(s) 1 1 1 signal(retardo) consumir();
if (n==0)
19 1 1 1 signal(s); wait(s)
wait(retraso)
20 wait(s) 0 1 1 } if (n==0)
21 extraer(); 0 1 1 } wait(retraso);
22 n--; 0 0 1 signal(s)
23 signal(s) 1 0 1 }
24 consumir(); 1 0 1
if (n==0)
}
25 1 0 0
wait(retraso) void main(){
26 wait(s) 0 0 0 n=0; wait
27 extraer(); 0 0 0 si es 1 lo pone a 0 y Pasa
paralelos(productor(1),productor(2), consumidor(1));
28 n--; 0 -1 0 si es 0 lo deja en 0 y Bloquea al proceso
29 signal(s) 1 -1 0
}
signal
Si la cola está vacía lo pone a 1
sino Desbloquea a uno de la cola
(y continúa)
 El problema del Productor-Consumidor
Hay uno o más procesos generando algún tipo de datos (registros, caracteres, objetos,
etc.) y colocándolos en un buffer. Hay un único consumidor que está extrayendo datos
del buffer. El sistema debe garantizar que se impida la superposición de operaciones
sobre los datos.
Es decir, sólo un agente (productor o consumidor), puede acceder al mismo tiempo.
Instrucción Productor Consumidor s n retraso
1 1 0 0 /* program productor-consumidor*/
2 wait(s) 0 0 0 int n; //Número de elementos producidos ¡¡¡ Utilizando variables locales que nadie
3 añadir() 0 0 0
BinSemaphore s=1; //MUTEX más podrá cambiar y que me recuerdan el
4 n++ 0 1 0
if (n==1) BinSemaphore retardo=0; //SINCRO valor de la compartida para cuando
5
signal(retraso)
0 1 1 necesite consultarlo !!!!
6 signal(s) 1 1 1
7 producir() 1 1 1
8 wait(retraso) 1 1 0 //Morris Lester Szyslak (Moe) //Homer Jay Simpson (Homer)
9 wait(s) 0 1 0
10 extraer(); 0 1 0
11 n--; 0 0 0
void productor(int n){ void consumidor(int n){
12 signal(s) 1 0 0 while (true){ int m; //local mía, privada
wait(retardo);
13 consumir(); 1 0 0 producir(); while
wait(retardo);
(true){
14 wait(s) 0 0 0 wait(s); while
wait(s);
(true){
15 añadir() 0 0 0
16 n++ 0 1 0
añadir(); wait(s);
extraer();
if (n==1) n++; n--;
extraer();
17 0 1 1
signal(retraso) if (n==1) signal(s);
n--;
18 signal(s) 1 1 1 signal(retardo) m=n; // me guardo el valor
consumir();
if (n==0)
19 1 1 1 signal(s); if
signal(s);
(n==0)
wait(retraso)
20 wait(s) 0 1 1 } consumir();
wait(retraso);
21 extraer(); 0 1 1 } } if (m==0) //consulto mi valor
22 n--; 0 0 1 } wait(retraso);
23 signal(s) 1 0 1 }
24 consumir(); 1 0 1
if (n==0)
}
25 1 0 0
wait(retraso) void main(){
26 wait(s) 0 0 0 n=0; wait
27 extraer(); 0 0 0 si es 1 lo pone a 0 y Pasa
paralelos(productor(1),productor(2), consumidor(1));
28 n--; 0 -1 0 si es 0 lo deja en 0 y Bloquea al proceso
29 signal(s) 1 -1 0
}
signal
Si la cola está vacía lo pone a 1
sino Desbloquea a uno de la cola
(y continúa)
 ¿Conclusión?
• Trabajar con semáforos es altamente complejo en determinados problemas, hay que
analizar bien las posibilidades …. ¿Tengo que probar todas las posibles trazas?

Claves para no tener que hacerlo

• Analizar bien el problema, entiende cómo se deben sincronizar los procesos
• Definir los semáforos MUTEX y SINCRO necesarios (analizar cuántos MUTEX usar)
Si los recursos son los mismos entonces el mismo MUTEX sino creo otro …
• Entender cuáles son los recursos críticos a proteger (funciones, variables… )
• Si accedo a una variable compartida tanto en lectura como en escritura debo protegerlas
• Si accedo en un if tendré que guardarlas en temporales mientras esté en la sección crítica
• Es muy peligroso introducir un wait en una sección crítica
pero no está prohibido, deberé garantizar que alguien rompa el posible interbloqueo

¿Estoy usando los semáforos apropiados?

¿cuáles deben ser binarios?
¿cuáles deben ser enteros?
Enteros vs Binarios
En principio se pueden resolver los problemas con ambos tipos de semáforos

¿Cuál elegir?

• Binarios  MUTEX para secciones críticas que permiten un único proceso

 SINCRO para sincronización
• Enteros  MUTEX cuando se permita entrar a varios procesos en la sección crítica
 SINCRO para sincronización (barreras)

Sincronización por contador.

Si pienso que necesito un contador para sincronizar procesos en función del valor del
contador entonces:
Binarios  Tengo que proteger al contador puesto que ambos procesos lo usan para
saber cómo sincronizar (productor-consumidor con binarios)
Enteros  No es necesario un contador adicional para sincronizar, la sincronización
se puede conseguir con semáforos enteros (incluyen un contador)
Productor-Consumidor (Buffer Infitito, Enteros)

/* program productor-consumidor*/
Semaphore sProd=0; //SINCRO (su contador cuenta los que hay producidos)
BinSemaphore s=1; //MUTEX de acceso al buffer

void productor(int n){ void consumidor(int n){

while (true){ while (true){ Cuando no haya elementos
producir(); wait(sProd);
wait(s); wait(s); producidos se bloqueará
añadir(); extraer();
signal(s); signal(s);
signal(sProd) consumir();
} }
} }
void main(){
n=0;
paralelos(productor(1),productor(2),
consumidor(1));
}

S = S-1  wait(S) Si puedo entrar, Paso, sino me Bloqueo

si queda S<0

S = S+1  signal(S) Yo Sigo, y si hay alguien bloqueado se Desbloquea

SISTEMAS OPERATIVOS - SEMÁFOROS

 Productor-Consumidor con Buffer Limitado
Hay uno o más procesos generando algún tipo de datos (registros, caracteres, objetos,
etc.) y colocándolos en un buffer. Hay un único consumidor que está extrayendo datos
del buffer. El sistema debe garantizar que se impida la superposición de operaciones
sobre los datos.

SISTEMAS OPERATIVOS - SEMÁFOROS

Productor-Consumidor (con Buffer Limitado)

/* program productor-consumidor*/
Semaphore sHuecos=24 //SINCRO (su contador cuenta los huecos que quedan en la caja)
Semaphore sProd=0; //SINCRO (su contador cuenta los que hay producidos)
BinSemaphore s=1; //MUTEX de acceso al buffer

Cuando no haya huecos void productor(int n){ void consumidor(int n){

Cuando no haya
libres se bloqueará while (true){ while (true){
producir(); wait(sProd); elementos producidos se
wait(sHuecos); wait(s); bloqueará
wait(s); extraer();
añadir(); signal(s);
signal(s); signal(sHuecos);
signal(sProd) consumir();
} }
} main(){
void }
n=0;
paralelos(productor(1),productor(2),
consumidor(1));
}

SISTEMAS OPERATIVOS - SEMÁFOROS

Ejercicio: “Los canarios en su jaula”
E2 - ( 2,5 Ptos ) – Una persona tiene en su casa una jaula llena de canarios en la que hay un plato de alpiste y
un columpio. Todos los canarios quieren primero comer del plato y luego columpiarse, sin embargo sólo tres de
ellos pueden comer del plato al mismo tiempo y sólo uno de ellos puede columpiarse. Cuando terminan de
columpiarse, están por la jaula hasta que les vuelve a entrar hambre y se repite su rutina.
Desarrollar una solución con semáforos que coordine la actividad de los canarios.
/* program canarios*/
Semaphore sPlato=3
BinSemaphore sColumpio=1;
void canario (int idcanario){
//El canario siempre hace lo mismo, primero come y luego se columpia en ese orden
while true {
//El canario pretende comer
wait(sPlato) void comer (int idcanario){
comer(idcanario); printf(“El canario %d esta comiendo”, idcanario);
signal(plato) sleep(random); //El canario está un tiempo comiendo
//El canario pretende columpiarse printf(“El canario %d termina de comer”, idcanario)
}
wait(sColumpio)
columpiarse(idcanario);
void columpiarse (int idcanario){
signal(sColumpio) printf(“El canario %d se esta columpiando”,idcanario);
} sleep(random); //El canario está un rato columpiandose
// El canario se pasea por la jaula printf(“El canario %d termina de columpiarse”,idcanario);
pasearse(idcanario); }
}
void pasearse (int idcanario){
sleep(random); //El canario está un tiempo paseando
void main(){ }
parbegin(canario(1),canario(2),….,canario(N));
}

SISTEMAS OPERATIVOS - SEMÁFOROS

 Exclusión Mutua: Barreras con Semáforos
Secuenciación con Semáforos
◦ Se quieren ejecutar dos procesos y se quiere que P2 se ejecute siempre después de P1, y no
sabemos cuando termina P1.
◦ Se utiliza un semáforo para detener a P2 hasta que P1 termine.

PROCESO 1 PROCESO 2
{ {
<codigo proceso 1> wait(p1);
signal(p1); <codigo proceso2>
} }

El semáforo se inicializará a 0
 Exclusión Mutua: Barreras con semáforos
Barreras
◦ Una barrera es el punto en el código tal que ningún proceso lo traspasa hasta que todos los procesos
han llegado a su ejecución.
◦ Si y solo si todos los procesos llegan a la barrera, continúan ejecutándose.
 Exclusión Mutua: Barreras con semáforos
Barreras
◦ Una barrera es el punto en el código tal que ningún proceso lo traspasa hasta que todos los
procesos han llegado a su ejecución.
◦ Si y solo si todos los procesos llegan a la barrera, continúan ejecutándose.
◦ Supongamos 2 procesos: Ambos deben poder detenerse y notificar al otro que han llegado
a la barrera

PROCESO 1 PROCESO 2
…. ….
<codigo proceso 1> <codigo proceso 2>
signal(barrera1); signal(barrera2);
wait(barrera2); wait(barrera1);
<codigo tras la barrera> <codigo tras la barrera>
…. ….
Ambos semáforos se inicializarán a 0
Cada proceso primero notifica que ha llegado a su barrera y
luego espera en la del otro.
Exclusión Mutua: Barreras con Semáforos
Ejercicio:
Implementar una barrera para un numero arbitrario (n) de procesos.
Explicar detalladamente la solución alcanzada.

Solución
◦ Basada en un proceso coordinador que se encarga de retener a todos los procesos
en su barrera hasta que llega el último. Se precisan tantos semáforos como procesos
(incluyendo al proceso coordinador). El coordinador conoce el numero de procesos.

PROCESO Pi PROCESO COORDINADOR

…. {
<codigo proceso i> for (i=0; i<n; i++){
signal(barrera[i]); wait(barrera[i]);
wait(coordinador); }
<codigo tras la barrera> for (i=0; i<n; i++){
…. signal(Coordinador);
}
}
 Exclusión Mutua: SEMAFOROS
Problema de los 5 filósofos:
◦ Planteado en 1965 por Dijkstra
◦ Ilustra problemas de exclusión mutua, interbloqueo e inanición
◦ Cada filosofo de vez en cuando se sienta a la mesa para comer.
Para ello necesita coger los
tenedores de su izquierda y derecha.
Cada tenedor es compartido con el
filosofo adyacente.
◦ ¿Cuál es el Recurso crítico?
 Exclusión Mutua: SEMAFOROS
Necesitamos acceder de manera exclusiva a los tenedores, por
tanto, un semáforo para cada tenedor
Un proceso para cada Filosofo
Numero de Filósofos 5:
Hay circularidad en los índices.

------- Filósofo i -------

repeat // Repetir
pensar();
wait(tenedor[i]);
wait(tenedor[i+1 % 5]);
comer();
signal(tenedor[i]);
signal(tenedor[i+1 % 5]);
until false // Indefinidamente ¿Garantiza la exclusión mutua?
¿Es correcta la solución?
 Exclusión Mutua: SEMAFOROS
Una posible solución: Permitir solo 4

------- Filósofos F1, F2, F3, F4, F5 ------

i=5
semaforo permiso=i-1;
semaforo tenedor[i];
repeat // Repetir
pensar();
wait(permiso);
wait(tenedor[i]);
wait(tenedor[i+1 % 5]);
comer();
signal(tenedor[i]);
signal(tenedor[i+1 % 5]);
signal(permiso);
until false // Indefinidamente
 Exclusión Mutua: SEMAFOROS
Una posible solución: Romper la circularidad

------- Filósofos F1, F2, F3, F4 ------

repeat // Repetir
pensar();
wait(tenedor[i]);
wait(tenedor[i+1 % 5]);
comer();
signal(tenedor[i]); ------- Filósofo 5 ------
signal(tenedor[i+1 % 5]); repeat // Repetir
until false // Indefinidamente pensar();
wait(tenedor[1]);
wait(tenedor[5]);
comer();
signal(tenedor[1]);
signal(tenedor[5]);
until false // Indefinidamente
 Exclusión Mutua: SEMAFOROS
Una solución más elaborada: coger los tenedores solo si están
disponibles void coger_tenedores(i){
#define N 5 wait(mutex);
#define IZQ (i+N-1)%N estado[i] = HAMBRIENTO;
#define DCH (i+1)%N test( i);
#define PENSANDO 0 signal(mutex);
#define HAMBRIENTO 1 wait(s[i]);
#define COMIENDO 2 }
typedef int semaphore; void dejar_tenedores(i){
int estado[N]; wait(mutex);
semaphore mutex = 1; estado[i]= PENSANDO;
semaphore s[N]; test(IZQ);
test(DCH);
void filosofo(int i) { signal(mutex);
while(true){ }
pensar(); void test(i){
coger_tenedores(i); if (estado[i]==HAMBRIENTO &&
comer(); estado[IZQ]!=COMIENDO &&
dejar_tenedores(i); estado[DCH]!=COMIENDO) {
} estado[i]=COMIENDO
} signal(s[i]);
}
}
Exclusión Mutua: SEMAFOROS

Lectores – escritores
◦ Existe un recurso común (fichero, base de datos, zona de
memoria, banco de registros del procesador, etc…) al cual acceden
varios procesos para leer y varios procesos para escribir de
manera concurrente. (lectores y escritores respectivamente)
◦ Los lectores pueden acceder concurrentemente entre si, ya que en
ningún caso pueden ocasionar problemas de inconsistencia en los
datos.
◦ Los escritores solo pueden acceder en exclusión mutua con otros
escritores y con los lectores.
◦ Es decir:
1. Cualquier número de lectores puede leer el recurso simultáneamente
2. Sólo puede escribir en el recurso un escritor en cada instante
3. Si un escritor está accediendo al recurso, ningún lector puede leerlo.
Exclusión Mutua: SEMAFOROS

Lectores – escritores: Primera solución

semaphore cri_lec =1; //Controla el acceso a la región crítica de los lectores
semaphore db = 1; //Controla el acceso a la base de datos o recurso compartido.
int cont_lect = 0; //Contador de lectores leyendo la base de datos

void lector (void) { void escritor(void) {

while (true) { while (true) {
wait(cri_lec); preparar_datos();
cont_lect++; wait(db);
if (cont_lect ==1) wait(db); escribir_base_datos();
signal(cri_lec); signal(db);
leer_base_datos(); }
wait(cri_lec); }
cont_lect--;
if (cont_lect ==0) signal(db);
signal(cri_lec); ¿Se puede producir inanición de
}
usar_datos_leidos(); los escritores?, ¿por qué?, ¿Quién
} tiene prioridad?
Exclusión Mutua: SEMAFOROS
Lectores – escritores: Segunda solución
semaphore cri_lec = 1; //Controla el acceso a la región crítica de los lectores
semaphore cri_esc = 1; //Controla el acceso a la región crítica de los escritores
semaphore db = 1; //Controla el acceso a la base de datos o recurso compartido.
semaphore perm_lect = 1; //Permite inhibir las lecturas en el momento que un escritor desee escribir.
semaphore lect = 1; //Encola a los lectores con intención de obtener permiso de lectura
int cont_lect = 0; //Contador de lectores leyendo la base de datos (critico lectores)
int cont_esc = 0; //Contador de escritores con intención de escribir, incluyendo el que escribe.

void lector (void) { void escritor(void) {

while (true) { while (true) {
wait(lect); preparar_datos();
wait(perm_lec); wait(cri_esc);
wait(cri_lec); cont_esc++
cont_lect++;
if (cont_esc == 1) wait(perm_lec);
if (cont_lect ==1) wait(db);
signal(cri_lec); signal(cri_esc);
signal(perm_lect) wait(db);
signal(lect) escribir_base_datos();
leer_base_datos(); signal(db);
wait(cri_lec); wait(cri_esc);
cont_lect--; cont_esc--;
if (cont_lect ==0) signal(db);
if (cont_esc == 0) signal(perm_lec);
signal(cri_lec);
usar_datos_leidos(); signal(cri_esc);
} }
} }
Exclusión Mutua: SEMAFOROS

El barbero dormilón.
En la peluquería hay 1 silla de barbero y n
sillas donde los clientes esperan su turno.
El barbero se echa a dormir si no hay clientes
esperando.
Cuando llega un cliente despierta al peluquero,
si llegan más clientes mientras el peluquero
está cortando el pelo, estos se esperan en las
sillas de espera, si hay sitio, sino, salen del
establecimiento.
Exclusión Mutua: SEMAFOROS
El barbero dormilón.
# define sillas 5 //Número de sillas de espera para clientes
semaphore clientes = 0; //Número de clientes esperando ser atendidos
semaphore barberos = 0; //Número de peluqueros que están ociosos
semaphore mutex = 1; //Para garantizar la exclusión mutua
int clientes_esperando = 0; //Contador de número de clientes esperando
semaphore begincorte=endcorte=0;

void barbero (void) { void cliente (void) {

while (true) { wait(mutex);
wait(clientes); //a dormir si no hay clientes if (clientes_esperando < sillas) {
wait(mutex); clientes_esperando++;
clientes_esperando--; signal(clientes); //despierta al barbero
signal(barberos); //ahora hay un barbero listo signal(mutex);
signal(mutex); wait(barberos); //esperar si el peluquero esta ocupado
cortar_pelo( ); sentarse_y_esperar( );
} }
} else signal(mutex);
}

void cortar_pelo(void) { void sentarse_y_esperar(void) {

wait(begincorte); sentarse();
cortarpelo(); signal(begincorte);
signal(fincorte); wait(fincorte);
} }
Exclusión Mutua: SEMAFOROS
El puente sobre el Amazonas
Sobre el amazonas se ha construido un puente de un único carril para minimizar su coste.
Desde cada extremo del puente no se divisa el otro extremo del puente por lo que no se
puede saber si hay coches entrando o dentro del puente cuando se intenta pasar.
En los extremos del puente existe una luz roja que indica si se puede pasar o no. Cuando un
coche se encuentra la luz apagada podrá entrar al puente. Unos sensores detectarán este
hecho y encenderán la luz en el otro extremo, pero se mantiene apagada la luz del extremo
por donde entró el coche. Cuando el último coche salga por el otro extremo, la luz se apagará
automáticamente en dicho extremo.
Plantear la solución para que puedan pasar los coches sin colisiones utilizando semáforos,
decidir cuantos, su tipo y los valores de inicialización.
• No gestionar la inanición ni prioridades
• Los coches no se averían en el puente
• Se cuenta con una función para cruzar el puente.
• Cruzar(A,B)  Cruza de la orilla A a la B
• Cruzar(B,A)  Cruza de la orilla B a la A
Exclusión Mutua: SEMAFOROS
El puente sobre el Amazonas
semaphore mutexA = 1; //Exclusión mutua para el contador de coches de la orilla A
semaphore mutexB = 1; //Exclusión mutua para el contador de coches de la orilla B
semaphore puente = 1; //Sincroniza el paso por el puente en un sentido u otro
int cochesA=cochesB = 0; //Contadores de numero de coches en cada orilla

CODIGO DE LA ORILLA A CODIGO DE LA ORILLA B

void orillaA (void) { void orillaB (void) {
while (true) { while (true) {
wait(mutexA); wait(mutexB);
cochesA++; cochesB++;
if (cochesA==1) if (cochesB==1)
wait(puente) wait(puente)
signal(mutexA); signal(mutexB);
cruzar(A,B); cruzar(B,A);
wait(mutexA); wait(mutexB);
cochesA--; cochesB--;
if (cochesA==0) if (cochesB==0)
signal(puente); signal(puente);
signal(mutexA); signal(mutexB);
} }
} }
Exclusión Mutua: SEMAFOROS
El puente colgante
En una antigua senda de montaña se ha construido un puente colgante que es capaz de
soportar 450Kg máximo sin riesgo de romperse.
Por la senda pasan excursionistas en ambos sentidos y el peso de cada excursionista más el
de su mochila son diferentes, pero cada uno lo conoce.
Plantear una solución con semáforos que permita que se cruce el puente por el máximo
numero de excursionistas posible siempre que no se ponga en peligro su integridad física.
• Plantear un código que deberían ejecutar cada excursionista (proceso) antes de pasar el
puente (recurso con limite de carga) independientemente del sentido de cruce.
• Indicar claramente que variables y semáforos comparten los procesos y cuales son los
valores iniciales.
• Considerar que cada proceso tiene una variable local llamada mipeso que tiene el peso
del excursionista al que representa más el de su mochila.
Exclusión Mutua: SEMAFOROS
El puente colgante
bool esperando = false //Indica si hay un excursionista esperando a pasar que ya restado su peso
int kilos = 750; //Número de kilos que soporta el puente
semaphore s1=1 //Para parar a los demás excursionistas cuando uno ya detecta que no puede pasar
semaphore mutex=1 //Para la exclusión mutua
semaphore s2=0; //Para colgar al que detecta que no puede pasar

EXCURSIONISTA void CodigoPre(void) { void CodigoPost(void) {

… wait(s1); wait(mutex);
… wait(mutex); kilos+=mipeso;
CodigoPre(); kilos-=mipeso; if (kilos>=0 && esperando){
Cruzar(); if (kilos<0){ esperando=false;
CodigoPost(); esperando=true; signal(s2);
… signal(mutex); }
… wait(s2); signal(mutex);
signal(s1); }
}
else {
signal(mutex); Si uno ya no puede pasar inhabilita a los
signal(s1); que vengan detrás que si pudieran pasar.
} Hasta que no se libere el peso suficiente
}
(el del que espera) nadie más puede
pasar.
Exclusión Mutua: SEMAFOROS
El puente colgante – 2ª Versión
int kilos = 750; //Número de kilos que soporta el puente
semaphore mutex=1 //Para la exclusión mutua
semaphoreb s[100]={0}; //Para colgar a los que detectan que no puede pasar
semaphoreb c=0; //Para dormir al controler
cont_waiting=0; //Para contar los que están esperando a probar si pueden pasar

Ejecución paralela de N excursionistas y 1 controler.

EXCURSIONISTA CONTROLER
void CodigoPre(void) { void CodigoPost(void) { void Controler(void){
mipeso=X; int cruzando=false; wait(mutex); int i;
… while (!cruzando){ kilos+=mipeso; while (true){
… wait(mutex); signal(c); wait(mutex);
CodigoPre(); if (kilos-mipeso<0){ signal(mutex); for (i=0;i<cont_waiting;i++){
Cruzar(); cont_waiting++; } signal(s[i]);
CodigoPost(); signal(mutex); }
… wait(s[cont_waiting]); cont_waiting=0;
… } signal(mutex);
else { wait(c);
kilos-=mipeso; } //while
signal(mutex); }
cruzando=true;
}
}
}
Exclusión Mutua: SEMAFOROS
Ejercicio propuesto
Sea una carretera en la que hay una zona de paso para peatones.

La zona de cruce es suficientemente ancha para que quepan varios coches

dentro, es decir, pueden estar sobre ella varios coches a la vez y por
supuesto varios peatones a la vez.

Los peatones tienen preferencia, de forma que mientras haya peatones

cruzando, los coches se pararan y esperaran a que el último peatón
abandone la zona de cruce.

Los coches podrán pasar mientras no llegue ningún peatón, cuando llegue
uno, se pararán y esperarán a que el peatón abandone la zona de cruce.

Los peatones son desconfiados. Cuando llega un peatón a la zona de

cruce, es el primero que va a pasar y hay coches en la carretera, aunque
tiene prioridad y podría pasar sin dudar, el peatón se cura en salud y se
para hasta que el coche pare, es decir, el peatón para si hay coches y
cuando el coche para le cede el paso al peatón y este cruza.

Una vez que ya hay peatones cruzando, los siguientes peatones ya no

tienen miedo y cruzan sin dudar aunque haya coches en la carretera.
… lo siguiente

• MONITORES

SISTEMAS OPERATIVOS - SEMÁFOROS

… más Info
En la web de la asignatura http://so.momrach.es
• Tenéis un cuaderno con ejercicios de concurrencia resueltos:
• De semáforos
• De monitores
• De paso de mensajes
• Una entrada Semáforos
- Con la explicación y ejemplo funcional de cómo se programan los semáforos en C
- Una librería (funcional) que facilita el uso al estilo de la teoría
• Una entrada Sincronización de Padre-Hijos con semáforos
- Con código funcional en C para sincronizar padre e hijos con semáforos
usando la librería anterior

Stallings – Sistemas Operativos Principios de Diseño e Interioridades (5ª ed.)

• En el punto 5.3 se tratan los semáforos
• En el punto 5.6 se presenta el problema de los Lectores/Escritores

Jesús Carretero – Sistemas Operativos una Visión Aplicada

• En el punto 5.3.2 Explica las Tuberías y cómo se implementa la sección crítica con ellas
Productor-Consumidor con Tuberías
• En el punto 5.3.4 Trata los semáforos y los Lectores/Escritores

SISTEMAS OPERATIVOS - SEMÁFOROS

Fin
UNIDAD 3
EXCLUSIÓN MUTUA Y SINCRONIZACIÓN
CON SEMÁFOROS

SISTEMAS OPERATIVOS - SEMÁFOROS