Algoritmo Productor

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 – consumidor deseaobtener 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
Roberto Gómez C.

Lámina 3

Primitivas de la solución
• Dos primitivas de comunicación son usadas entre los procesos que bloquean el CPU. • Primitiva dormir (sleep)
– provoca elbloqueo 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
Roberto Gómez C.

Lámina 4

Solución problema productor/consumidor
#define N 100 int cont = 0; void productor( ) { while (TRUE) { produce_elem(&elemento); if (cont == N) sleep(); _( ) intro_elem(elemento); cont = cont+1 if (cont == 1) wakeup(consumidor); k ( id ) }
Lámina 5

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

/* ciclo infinito

*/ */ */ */ */ */ */

/* genera el siguiente elemento /* si el almacen (buffer) esta lleno /* entonces se duerme /* colocar elemento en almacen /* incrementa conta. elementosalma. /* estaba vacio el almacen (buffer)

}

Roberto Gómez C.

Solución problema productor/consumidor
void consumidor( ) { while (TRUE) { if (cont == 0) ( t sleep(); retira_elem(&elemento); cont = cont - 1; if (cont == N-1) wakeup(productor); consume_elem(elemento); } }
Roberto Gómez C.

/* ciclo infinito /* si el almacen (buffer) esta vacío i l l (b ff ) t í /* entonces se duerme /*retira elemento del almacen /* estaba lleno el almacen (buffer) /* consume el elemento

*/ */ */ */ */ */

/* decrementa conta. elementos alma */

Lámina 6

Problemas de la solución
• Almacen vacío
Productor P d t Consumidor C id Consumidor lee count (count = 0) if (cont == 0) => verdad Prod. introduce elemento en almacen Incrementa cont if (cont == 1) => verdad wakeup(consumidor); /* consno 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 un bit 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 porDijkstra 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 y puede ser accesado y alterado por dos operaciones: P(S) y V(S) • Nombres provienen del holandes proberen (probar) y verhogen (incrementar).
Roberto Gómez C.

Lámina 9

Algo sobre Dijkstra
"Inhis 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 computers, and to present computer science as a branch of pure t dt t t i b h f mathematics. (Yes, this is a caricature.) " "Dijkstra is among the brightest lights in theoretical computer Dijkstra science;...