Semaforos 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...
Regístrate para leer el documento completo.