Semaforos y Monitores

Semáforos y Monitores
Soluciones al problema de exclusión
mutua

Lámina 1

Roberto Gómez C.

El problema del productor/consumidor
• Dos procesos comparten un almacen (
p
p
(buffer) de
)
tamaño fijo.
– productor: coloca información en el almacen (buffer)
– consumidor: obtiene información del almacen

• Problema:
– productor desea colocar algo en el almacen lleno
– consumidordesea obtener en el almacen vació

• S l ió
Solución
– irse a dormir cuando el almacen este lleno (productor) o
cuando se encuentre vacio (consumidor)
Lámina 2

Roberto Gómez C.

Planteamiento de la solución
• Dos variables compartidas por los procesos:
– cont: número elementos en el almacen (buffer)
t ú
l
t
l l
(b ff )
– N: número máximo elementos (tamaño buffer)

•Actividades productor:
– verificar si count = N
• si es verdad => a dormir
• si no es verdad => añadir un elemento

• Actividades consumidor:
– verificar si count = 0
• si es verdad => a dormir
• si no es verdad => quitar un elemento

Lámina 3

Roberto Gómez C.

Primitivas de la solución
• Dos primitivas de comunicación son usadas
entre los procesos que bloquean el CPU.
• Primitivadormir (sleep)
– provoca el bloqueo de quien hizo la llamada
– será suspendido hasta que alguien lo despierte

• Primitiva despertar (wakeup)
– despierta al proceso que invocó una primitiva sleep
– tiene un parámetro: el proceso a despertar

Lámina 4

Roberto Gómez C.

Solución problema productor/consumidor
#define N 100

/* Número de espacios en el almacen (buffer) */

int cont =0;

/* Número de elementos en el almacen (buffer) */

void productor( )
{
while (TRUE) {

/* ciclo infinito

*/

produce_elem(&elemento);

/* genera el siguiente elemento

*/

if (cont == N)

/* si el almacen (buffer) esta lleno

*/

/* entonces se duerme

*/

_
(
)
intro_elem(elemento);

/* colocar elemento en almacen

*/

cont = cont+1

/* incrementa conta.elementos alma.

*/

if (cont == 1)

/* estaba vacio el almacen (buffer)

*/

sleep();

wakeup(consumidor);
k (
id )
}
Lámina 5

}

Roberto Gómez C.

Solución problema productor/consumidor
void consumidor( )
{
while (TRUE) {

/* ciclo infinito

*/

/* si el almacen (buffer) esta vacío
i l l
(b ff ) t
í

*/

/* entonces se duerme

*/retira_elem(&elemento);

/* retira elemento del almacen

*/

cont = cont - 1;

/* decrementa conta. elementos alma */

if (cont == N-1)

/* estaba lleno el almacen (buffer)

*/

/* consume el elemento

*/

if (cont == 0)
( t
sleep();

wakeup(productor);
consume_elem(elemento);
}
}

Lámina 6

Roberto Gómez C.

Problemas de la solución
• Almacen vacío
Productor
P d t

ConsumidorC
id
Consumidor lee count (count = 0)
if (cont == 0) => verdad

Prod. introduce elemento en almacen
Incrementa cont
if (cont == 1) => verdad
wakeup(consumidor);
/* cons no esta dormido, señal se pierde */
sleep()
producira elementos hasta que se
llene el almacen y se ira a dormir
sleep()
Lámina 7

AMBOS DORMIRAN POR SIEMPRE

Roberto Gómez C.

Posible solución
• Añadir unbit de espera de despertar
• Sin embargo si se tienen dos o más procesos un
solo bit no es suficiente.
suficiente

Lámina 8

Roberto Gómez C.

Los semáforos
• Definidos por Dijkstra en 1965
– Dijkstra, E. W., Cooperating
sequential processes, `Programming
Languages Genuys, F (ed )
Languages', Genuys F. (ed.),
Academic Press, 1965

• Variable protegida cuyo valor solo
p
g
ypuede ser accesado y alterado por dos operaciones:
P(S) y V(S)
• Nombres provienen del holandes proberen (probar) y
verhogen (incrementar).

Lámina 9

Roberto Gómez C.

Algo sobre Dijkstra
"In his later career, he seems to personify almost perfectly the
In
career
class of computer scientist who is inclined to never touch a
computer, to do his best to keep his students from touching...