1

CAPITOLO 17 – PROBLEMI DEL PRODUTTORE/CONSUMATORE v1 PRODUTTORE/CONSUMATORE Il problema del produttore/consumatore è uno dei problemi più comuni di concorrenza tra processi. Il problema presenta uno o più produttori che generano dati (record, caratteri) i quali vengono inseriti all’interno di un buffer e un consumatore che preleva gli elementi dal buffer uno alla volta. La mutua esclusione è necessaria per impedire la sovrapposizione delle operazioni effettuate dal produttore e dal consumatore sul buffer. Il problema del produttore/consumatore

Il primo approccio alla risoluzione del problema del produttore/consumatore considera un buffer infinito presentato come un array di elementi. Le funzioni produttore e consumatore utilizzano la variabile globale in che indica la posizione corrente all’interno del buffer. La funzione del produttore può generare elementi ed introdurli nel buffer senza limiti di velocità. Il produttore chiama la funzione produce che crea un nuovo elemento v il quale viene posto nella cella di posizione in all’interno del buffer ed incrementa in di una unità. La funzione del consumatore utilizza il puntatore out che individua la prima cella piena da consumare all’interno del buffer. Il consumatore deve sempre verificare che il produttore sia più avanti di lui all’interno del buffer e dunque che in sia maggiore di out, in tal caso il consumatore potrà prelevare un elemento puntato da out, incrementare out e consumare l’elemento tramite la funzione consuma. La mutua esclusione tra i due processi è garantita attraverso l’uso di un semaforo s, mentre il semaforo ritardo è utilizzato per impedire che produttore e consumatore operino sulla stessa cella. Inoltre è introdotta la variabile n=in-out che contiene il numero di celle piene del buffer. Soluzione non corretta del problema produttore/consumatore con l’uso di semafori binari nel caso di buffer infinito

program produttore_consumatore;

var n: integer;

s: semaforo (:=1); (*binario*)

ritardo: semaforo (:=0); (*binario*)

procedure produttore;

begin

repeat produci;

waitB(s);

aggiungi;

n:=n+1;

if n=1 then signalB(ritardo);

signalB(s)

forever

end;

procedure consumatore;

begin

waitB(ritardo);

repeat

waitB(s);

prendi un elemento;

n:=n-1;

signalB(s);

type semaforo = record contatore: integer; coda: list of process end; var s: semaforo; wait (s) : s.contatore := s.contatore - 1 if s.contatore < 0 then begin metti questo processo in s.coda; blocca questo processo end; signal (s) : s.contatore := s.contatore +1; if s.contatore £ 0 then begin togli un processo P da s.coda; metti P in stato di Ready end;

2

consuma;

if n=0 then waitB(ritardo)

forever

end;

begin (*programma principale*)

n:=0;

parbegin

produttore; consumatore parend

end.

La slide illustra una soluzione al problema del produttore/consumatore utilizzando semafori binari nel caso di buffer infinito. Sono definiti ed inizializzati il semaforo s che controlla l’accesso al buffer da parte del produttore o del consumatore e il semaforo ritardo che permette di dire se il buffer è vuoto ed occorre produrre oppure permette di vedere se il buffer è pieno e si può consumare. Il produttore produce un nuovo elemento e si accerta di poter depositare lo stesso nel buffer effettuando la primitiva waitB sul semaforo s. Dopo aver ottenuto l’accesso, esegue l’aggiunta dell’elemento al buffer ed incrementa il valore della variabile n. Se n è uguale ad 1 significa che precedentemente il buffer era vuoto e deve conservare l’informazione che ora è pieno e che pertanto un consumatore può correttamente accedere, allo scopo effettua una signal sul semaforo ritardo. Infine è effettuata una signalB(s) per consentire sia a successivi produttori che consumatori di poter accedere al buffer. All’interno della procedura del consumatore, questo effettua una waitB sul semaforo ritardo per attendere che venga prodotto il primo elemento. Una volta presente l’elemento nel buffer lo preleva, decrementa di una unità n e con la signalB sul semaforo s permette l’accesso da parte di un altro produttore o consumatore. In seguito l’elemento è consumato ed avviene il controllo su n che se è uguale a zero significa che il buffer è vuoto ed è necessario dunque una waitB sul semaforo ritardo per attendere che venga prodotto un nuovo elemento. Questa soluzione è non corretta. OSSERVAZIONE

Questo programma così come è fatto non funziona e per convincersene basta osservare che: c’è una situazione in cui una esecuzione ritardata della linea di codice contenente il 2° waitB (ritardo) del consumatore darebbe come risultato un prelievo da una cella vuota.

Il programma illustrato non funziona poiché in presenza di una esecuzione ritardata della linea di codice del consumatore contenente il 2° waitB(ritardo) produce come risultato il prelievo da una cella vuota. Infatti se nella procedura del consumatore durante la funzione consuma il produttore produce un nuovo elemento ed incrementa n, la funzione consumatore non esegue la waitB(ritardo) poiché n risulterà uguale ad 1 dunque si attiverà un successivo processo consumatore che effettuerà un prelievo da una cella vuota assegnando il valore -1 ad n.

Analisi del fallimento

La slide illustra parte della sequenza di esecuzione del programma di mutua esclusione per il problema del produttore/consumatore riportando per ogni istruzione eseguita i valori assegnati al semaforo s, alla variabile n e al semaforo ritardo. Si può osservare come durante il 1° ciclo produttore sia prodotto un elemento che viene inserito nel buffer, durante il 2° ciclo, consumatore, e quindi l’esecuzione di consuma, l’istruzione di controllo if n=0 then waitB(ritardo) supponiamo che non viene eseguita, parte allora il 3° ciclo consumatore.

3

Analisi del fallimento

Supponiamo che con il 4° ciclo consumatore venga eseguita l’istruzione precedentemente bloccata, che pur essendo ora eseguita per effetto del cambiamento delle condizioni non ha l’effetto desiderato. Un successivo ciclo consumatore fa giungere all’assurdo di ottenere n=-1 per cui il consumatore tenta di prelevare da una cella vuota. Analisi del fallimento

La diapositiva riassume sinteticamente i cicli innanzi esposti, con i valori di s, n e ritardo, dalla loro inizializzazione alla loro configurazione finale che riporta un caso errato.

4

Considerazioni sul fallimento dell'algoritmo presentato

Questa diapositiva riporta quanto innanzi descritto. Soluzione corretta del produttore/consumatore semafori binari

program produttore_consumatore; var n: integer; s: semaforo (:=1); (*binario*) ritardo: semaforo (:=0); (*binario*) procedure produttore; begin repeat produci; waitB(s); aggiungi; n:=n+1; if n=1 then signalB(ritardo); signalB(s) forever end; procedure consumatore; var m: integer; (*variabile locale*); begin waitB(ritardo); repeat waitB(s); prendi un elemento; n:=n-1; m:=n; signalB(s); consuma; if m=0 then waitB(ritardo) forever end; begin (*programma principale*) n:=0; parbegin produttore; consumatore parend end.

La causa del malfunzionamento dell’algoritmo presentato nelle slide precedenti risiede nel fatto che viene utilizzata una variabile globale n sulla quale agiscono entrambe le procedure produttore e consumatore. La soluzione al problema si ottiene con l’introduzione della variabile locale m all’interno della procedura consumatore. A tale variabile viene passato il valore di n dopo il suo decremento, questo permette al consumatore di eseguire la primitiva wait anche se il produttore ha modificato il valore di n durante l’esecuzione di consuma da parte del consumatore.

5

Soluzione con semafori generici program produttore_consumatore; var n: semaforo (:=0); s: semaforo (:=1); procedure produttore; begin repeat produci; wait(s); aggiungi; signal(s); signal(n) forever end; procedure consumatore; begin repeat wait(n); wait(s); prendi un elemento; signal(s); consuma forever end; begin (*programma principale*) parbegin produttore; consumatore parend end.

Una soluzione più lineare al problema del produttore/consumatore si ottiene utilizzando i semafori generici detti anche semafori a contatore. La variabile intera n viene sostituita da un semaforo il cui contatore contiene il numero delle celle piene del buffer. La procedura del produttore produce un nuovo elemento, successivamente attraverso wait(s) ottiene l’accesso esclusivo al buffer, aggiunge l’elemento e con signal(s) libera l’accesso agli altri processi, infine eseguendo una signal(n) incrementa il numero delle celle piene del buffer. La procedura del consumatore con una wait(n) si accerta che il buffer sia vuoto e con wait(s) accede alla sezione critica per prelevare un elemento dal buffer successivamente libera l’accesso per consentire ad altri di accedere, esce dalla sezione critica ed infine consuma.

IL CASO DI BUFFER CIRCOLARE

Nella slide è riportata un’immagine di buffer di dimensione limitata. Il buffer è immaginato come un sistema circolare in cui i valori di in e out sono espressi modulo la dimensione del buffer.

6

IL PRODUTTORE E IL CONSUMATORE PER UN BUFFER LIMITATO

Nella slide sono riportate le funzioni del produttore e del consumatore per l’utilizzo di un buffer limitato, utilizzando i valori di in e out posti inizialmente a zero ed espressi in modulo n che indica la dimensione del buffer. Il produttore produce l’elemento dopo di che sino a quando (in+1) è uguale ad out fa nulla ( attesa attiva), successivamente deposita l’elemento nel buffer e incrementa il puntatore in. Il consumatore invece finché n è uguale ad out fa nulla e quando questa condizione è negata legge l’elemento contenuto nella cella puntata da out e lo consuma avendo cura di incrementare modularmene il puntatore out. Soluzione del problema del produttore/consumatore con buffer limitato utilizzando i semafori

program bufferlimitato; const dimensione_del_buffer=…; var s: semaforo (:=1); n: semaforo (:=0); e: semaforo (:=dimensione_del_buffer); procedure produttore; begin repeat produci; wait(e); wait(s); aggiungi; signal(s); signal(n) forever end; procedure consumatore; begin repeat wait(n); wait(s); prendi un elemento; signal(s); signal(e); consuma forever end; begin (*programma principale*) parbegin produttore; consumatore parend end.

La slide presenta una soluzione al problema del produttore/consumatore utilizzando i semafori e un buffer di dimensione finita. Il programma prevede la definizione della dimensione del buffer come costante e la definizione di tre variabili di tipo semaforo. Il semaforo s è utilizzato per il controllo dell’accesso del produttore e del consumatore. Il semaforo n è utilizzato per la gestione del numero di celle piene del buffer e come informazione al consumatore che il buffer non è vuoto e quindi che può consumare. Infine il semaforo e è utilizzato per dare informazione circa la presenza o meno di celle vuote nel buffer. Le procedure produttore/consumatore vengono utilizzate dai processi in concorrenza come mostrato nel programma principale tra i costrutti parbegin e parend. La procedura del produttore produce un nuovo elemento, successivamente attraverso wait(e) aspetta che ci siano celle vuote da riempire all’interno del buffer, con wait(s) ottiene l’accesso esclusivo al buffer, aggiunge l’elemento e con signal(s) libera l’accesso agli altri processi, infine eseguendo una signal(n) incrementa il numero delle celle piene del buffer. La procedura del consumatore con una wait(n) si accerta che il buffer sia vuoto e con wait(s) accede alla sezione critica per prelevare un elemento dal buffer successivamente libera l’accesso per consentire ad altri di accedere, con signal(e) segnala la presenza di una cella vuota nel buffer per consentire ad altri processi produttori eventualmente di aggiungere un elemento, esce dalla sezione critica ed infine consuma.

7

Implementazione dei SEMAFORI

Le primitive wait e signal devono essere essenzialmente implementate come primitive atomiche. Una implementazione di tipo atomico può essere fatta senz’altro in hardware o firmware. In alternativa possono essere utilizzati gli algoritmi di Dekker o di Peterson come soluzione software per garantire la mutua esclusione e quindi l’atomicità di queste procedure. Ovviamente al costo di un sovraccarico di elaborazione. Un’ulteriore alternativa è data dall’utilizzo di uno schema hardware come ad esempio l’utilizzo dell’istruzione Test-and-Set. L’utilizzo di questa istruzione introduce la variabile intera s.flag che provoca una forma di attesa attiva ma poichè wait e signal sono operazioni brevi, il tempo di attesa attiva non è elevato. Un’ulteriore approccio è la disabilitazione degli interrupt durante un’operazione di wait o signal, anche in questo caso per la durata breve delle operazioni, il tempo di attesa attiva è ragionevolmente accettabile. Implementazione dei SEMAFORI

Wait(s): repeat {nulla} until testset (s.flag); s.contatore:=s.contatore-1; if s.contatore<0 then begin metti questo processo in s.coda; blocca questo processo (bisogna anche mettere s.flag a 0) end else s.flag:=0; Signal(s): repeat {nulla} until testset (s.flag); s.contatore:=s.contatore+1; if s.contatore≤0 then begin togli un processo P da s.coda; metti il processo P in stato di Ready end; s.flag:=0; a. Istruzione Test-And-Set Wait(s): Disabilita le interruzioni; s.contatore:=s.contatore-1; if s.contatore<0 then begin metti questo processo in s.coda; blocca questo processo e riattiva le interruzioni end else riattiva le interruzioni; Signal(s): Disabilita le interruzioni; s.contatore:=s.contatore+1; if s.contatore≤0 then begin togli un processo P da s.coda; metti il processo P in stato di Ready end; riattiva le interruzioni; a. Interruzioni

Il codice riportato nella presente slide illustra due possibili implementazioni dei semafori utilizzando wait e signal come primitive atomiche. La prima implementazione utilizza l’istruzione Test-And-Set e la variabile intera s.flag. Se s.flag=0 allora la funzione testset restituisce il valore vero e pone s.flag=1 altrimenti restituisce il valore falso e lascia il valore di s.flag inalterato. Il secondo approccio utilizza le interruzioni, anche in questo caso per la durata breve delle operazioni, il tempo di attesa attiva è ragionevolmente accettabile.