Problema del produttore-consumatore

Un classico esempio di problema di sincronizzazione tra unità di esecuzione è il problema del produttore-consumatore.

Definizione: problema del produttore-consumatore

Il problema del produttore-consumatore (conosciuto anche con il nome di problema del buffer limitato o, in inglese, bounded-buffer problem) è un problema di sincronizzazione dei processi in cui due processi, un produttore $P$ (in inglese producer) e un consumatore $C$ (in inglese consumer), condividono un buffer $\text{buffer}$ comune di dimensione fissata $\text{BUFFER\_SIZE}$.

I compiti dei due processi sono i seguenti:

• il produttore deve generare dati e depositarli nel buffer in continuo, assicurando di non generarne di nuovi se il buffer è pieno e
• il consumatore utilizzerà i dati prodotti, rimuovendoli di volta in volta dal buffer, assicurando di non cercarne se il buffer è vuoto.

Produttore e consumatore condividono le seguenti variabili:

• Come già detto, un buffer $\text{buffer}$ comune di dimensione fissata $\text{BUFFER\_SIZE}$, realizzato come un array circolare.
• Un indice $\text{in}$ che indica la successiva posizione libera nel $\text{buffer}$.
• Un indice $\text{out}$ che indica la prima posizione piena nel $\text{buffer}$.

Il $\text{buffer}$ quindi

• è vuoto se $\text{in == out}$ ed
• è pieno se $\text{((in + 1) \% BUFFER\_SIZE) == out}$ per definizione dell’array circolare.

Il produttore ha una variabile locale $\text{next\_produced}$ contenente il nuovo elemento da produrre e, finché il $\text{buffer}$ è pieno, non fa niente, effettuando una busy waiting; una volta che si libera, inserisce l’elemento $\text{next\_produced}$ nel $\text{buffer}$ alla posizione $\text{in}$ e aggiorna il valore di questo indice:

item next_produced;
while (true) {
	// Produzione di un elemento in next_produced
	while (((in + 1) % BUFFER_SIZE) == out); // Busy waiting
	buffer[in] = next_produced;
	in = (in + 1) % BUFFER_SIZE;
}

Viceversa, il consumatore ha una variabile locale $\text{next\_consumed}$ contenente il nuovo elemento da consumare e, finché il $\text{buffer}$ è vuoto, non fa niente, effettuando una busy waiting; una volta che si riempie, preleva l’elemento $\text{next\_consumed}$ dal $\text{buffer}$ alla posizione $\text{out}$ e aggiorna il valore di questo indice:

item next_consumed;
while (true) {
	while (in == out); // Busy waiting
	next_consumed = buffer[out];
	out = (out + 1) % BUFFER_SIZE;
	// Consumazione dell'elemento in next_consumed
}

Questa soluzione consentiva la presenza contemporanea di non più di $\text{BUFFER\_SIZE - 1}$ elementi a causa della definizione dell’array circolare. Si supponga di voler modificare l’algoritmo per rimediare a questa carenza e sfruttare anche l’ultimo elemento: una possibilità consiste nell’aggiungere una variabile intera $\text{counter}$, inizializzata a $\text{0}$, che si incrementa ogniqualvolta s’inserisce un nuovo elemento nel $\text{buffer}$ e si decrementa ogniqualvolta si preleva un elemento dal $\text{buffer}$. Il codice per il produttore si può modificare come segue:

item next_consumed;
int counter = 0;
while (true) {
	// Produzione di un elemento in next_produced
	while (counter == BUFFER_SIZE); // Busy waiting
	buffer[in] = next_produced;
	in = (in + 1) % BUFFER_SIZE;
	counter++;
}

Il codice per il consumatore, invece, si può modificare come segue:

item next_consumed;
int counter;
while (true) {
	while (counter == 0); // Busy waiting
	next_consumed = buffer[out];
	out = (out + 1) % BUFFER_SIZE;
	counter--;
	// Consumazione dell'elemento in next_consumed
}

Questi due processi possono manipolare concorrentemente la variabile $\text{counter}$, creando così una race condition. Questa problematica può essere risolta attraverso meccanismi di sincronizzazione.