Domenico Cotroneo » 12.Problemi di cooperazione nel modello ad ambiente globale

Problemi di cooperazione nel modello ad ambiente globale

Sommario

• Il problema produttore/consumatore
  • Soluzione con buffer singolo
  • Soluzione con coda circolare
  • Soluzione con un pool di buffer e vettore di stato
• Il problema lettori/scrittori
  • Soluzione con starvation degli scrittori
  • Soluzione con starvation di entrambi

Il problema produttore/consumatore

Due categorie di processi:

1. produttori, che scrivono un messaggio su di una risorsa condivisa;
2. consumatori, che prelevano il messaggio dalla risorsa condivisa.

Vincoli

• Il produttore non può produrre un messaggio prima che qualche consumatore abbia letto il messaggio precedente.
• Il consumatore non può prelevare alcun messaggio fino a che un produttore non l’abbia depositato.

Prod-Cons con un unico buffer

I vincoli imposti da un problema di tipo Produttore-Consumatore,nel caso che il buffer sia unico e che vi siano un solo produttore ed un solo consumatore, sono i seguenti:

• il produttore non può produrre un messaggio se il consumatore non ha consumato il messaggio precedente;
• il consumatore non può prelevare un messaggio se prima il produttore non l’ha depositato.

Prod-Cons con un unico buffer

Per la sincronizzazione dei processi produttore e consumatore si utilizzano due semafori:

1. SPAZIO_DISP: semaforo bloccato da un produttore prima di una produzione sbloccato da un consumatore in seguito ad un consumo (VALORE INIZIALE: 1);
2. MSG_DISP: semaforo sbloccato da un produttore in seguito ad una produzione e bloccato da un consumatore prima del consumo (VALORE INIZIALE: 0).

Prod-Cons con un unico buffer

Il messaggio prodotto consiste di un valore di tipo long, rappresentativo della data di sistema (ottenuto mediante la chiamata gettimeofday(2)) .

Una siffatta soluzione permette di differenziare i valori prodotti dai vari processi produttori.
La produzione ed il consumo avvengono rispettivamente all’interno delle procedure

void Produttore(msg*,int);
void Consumatore(msg *,int);

all’interno delle quali si effettuano anche le operazioni di Wait_Sem e Signal_Sem necessarie.

Prod-Cons con un unico buffer

//Procedure Consumatore

void Consumatore(msg *ptr_sh,int mutex){

msg mess;

Wait_Sem(mutex,MSG_DISP);
mess=*ptr_sh;
printf("Messaggio letto: \n",mess);
Signal_Sem(mutex,SPAZIO_DISP);

}

Prod-Cons con un unico buffer

//Procedure Produttore

void Produttore(msg*ptr_sh,int mutex){

// Produzione del valore
struct timeval t1;
struct timezone t2;
gettimeofday(&t1,&t2);
msg val =t1.tv_usec;

Wait_Sem(mutex,SPAZIO_DISP);
printf ("Produzione in corso...");
*ptr_sh=val;
Signal_Sem(mutex,MSG_DISP);

}

Prod-Cons con una coda

La coda è implementata mediante i seguenti campi:

• buffer[DIM] – array di elementi di tipo msg (tipo del messaggio depositato dagli scrittori) contenente i valori prodotti;
• testa – tipo intero. Si riferisce alla posizione del primo elemento libero in testa; in altre parole rappresenta il primo elemento disponibile per la memorizzazione del messaggio prodotto. L’elemento di testa è buffer[testa-1];
• coda – tipo intero. L’elemento puntato si riferisce alla posizione dell’elemento di coda della coda. In altre parole l’elemento di coda è buffer[coda].

Anche le variabili testa e coda devono essere condivise!!

Prod-Cons con una coda

Per la sincronizzazione dei processi sono stati utilizzati due semafori, SPAZIO_DISP e NUM_MESS, che indicano rispettivamente la presenza di spazio disponibile in coda per la produzione di un messaggio e il numero di messaggi presenti in coda.

SPAZIO_DISP ha valore iniziale DIM (dimensione della coda).

NUM_MESS ha valore iniziale 0.

Prod-Cons con una coda

void Produttore(int* testa, msg* buffer, int sem) {


Wait_Sem(sem, SPAZIO_DISP);
// Produzione di valore_prodotto . . .
buffer[(testa)]=valore_prodotto;
testa=++(testa) % DIM; //gestione circolare
Signal_Sem(sem, NUM_MESS); //nelem=nelem+1


}

Prod-Cons con una coda

void Consumatore(int* coda, msg* buffer, int sem){


msg mess;
Wait_Sem(sem, NUM_MESS);
// Consumo
mess=buffer[coda];
(coda)=++(coda) %DIM; // gestione circolare
printf("Messaggio letto: <%d>\n",mess);
Signal_Sem(sem, SPAZIO_DISP); // nelem=nelem-1


}

Prod-Cons con una coda

Con questa soluzione il produttore e il consumatore non accedono mai contemporaneamente alla stessa posizione della coda dei messaggi

… tuttavia va bene solo nel caso in cui si ha 1 processo produttore e 1 processo consumatore!

Più Produttori e più Consumatori con una coda

Nell’ipotesi in cui vi siano più produttori e più consumatori che accedono allo stesso buffer, le operazioni di deposito e prelievo devono essere eseguite rispettivamente in mutua esclusione, ed essere quindi programmate come sezioni critiche.

A tal fine, bisogna introdurre due nuovi semafori:

• MUTEX_R per le operazioni di lettura;
• MUTEX_W per le operazioni di scrittura;
• entrambi inizializzati a 1.

Più Produttori e più Consumatori con una coda

void Produttore(int* testa, msg* buffer, int sem) {


Wait_Sem(sem, SPAZIO_DISP);
Wait_Sem(sem, MUTEX_W);
// Produzione di valore_prodotto . . .
buffer[(testa)]=valore_prodotto;
testa=++(testa) % DIM; // gestione circolare
Signal_Sem(sem, MUTEX_W);
Signal_Sem(sem, NUM_MESS); // nelem=nelem+1


}

Più Produttori e più Consumatori con una coda

void Consumatore(int* coda, msg* buffer, int sem){


msg mess;
Wait_Sem(sem, NUM_MESS); Wait_Sem(sem, MUTEX_R);
// Consumo
mess=buffer[coda];
(coda)=++(coda) %DIM; // gestione circolare
printf("Messaggio letto: <%d> \n",mess);
Signal_Sem(sem, MUTEX_R);
Signal_Sem(sem, SPAZIO_DISP); // nelem=nelem-1


}

Prod-Cons con un pool di buffer

La soluzione precedente penalizza produttori o consumatori “veloci” in presenza di produttori o consumatori “lenti” (evento che può accadere, ad esempio, quando i messaggi prodotti hanno dimensione diversa).

Soluzione: utilizzo di un pool di buffer gestito mediante un vettore ausiliario di STATO

Una volta che un processo acquisisce il suo buffer, può procedere in concorrenza agli altri.

Prod-Cons con un pool di buffer

I vincoli imposti sono i seguenti:

• un produttore non può produrre un messaggio se il buffer è pieno;
• un consumatore non può prelevare un messaggio se il buffer è vuoto.

La gestione del pool di buffer avviene mediante due vettori:

• buffer[DIM] – array di elementi di tipo msg (tipo del messaggio depositato dai produttori) contenente i valori prodotti;
• stato[DIM]- array di elementi di tipo intero. Il valore i-simo, stato[i], può assumere i seguenti tre valori:
  • VUOTO – la cella buffer[i] non contiene alcun valore prodotto;
  • PIENO – la cella buffer[i] contiene un valore prodotto e non ancora consumato;
  • IN_USO – il valore della cella buffer[i] contiene un valore in uso da un processo attivo, consumatore o produttore.

Prod-Cons con un pool di buffer

Per la gestione della mutua esclusione nell’accesso al buffer di stato, si possono utilizzare due mutex, MUTEXP e MUTEXC, uno per i produttori e uno per i consumatori, entrambi inizializzati a 1.

I soliti due semafori, SPAZIO_DISP e MSG_DISP, usati per la sincronizzazione delle operazioni di produzione e consumo, con SPAZIO_DISP inizializzato a DIM (o al numero di produttori, se minore o uguale a DIM), e MESS_DISP inizializzato a 0.

Prod-Cons con un pool di buffer

void Produttore(int* stato, msg* buffer, int sem) {


int indice = 0;
Wait_Sem(sem, SPAZIO_DISP); // attende spazio

Wait_Sem(sem, MUTEXP); // Blocca altri prod
// determina l'indice del primo elemento VUOTO
while ((indice <=DIM)&&(stato[indice]!=VUOTO))

 indice++;


stato[indice]=IN_USO; // la cella è in uso
Signal_Sem(sem, MUTEXP); // Sblocca altri prod

// Produzione di valore_prodotto . . .
buffer[indice]=valore_prodotto;

stato[indice]=PIENO; // la cella è piena
Signal_Sem(sem, MSG_DISP); // segnala i cons


}

Prod-Cons con un pool di buffer

void Consumatore(int* stato, msg* buffer, int sem) {


int indice = 0;
Wait_Sem(sem, MSG_DISP); // attende messaggio

Wait_Sem(sem, MUTEXC); // Blocca altri cons
// determina l'indice del primo elemento PIENO
while ((indice <=DIM)&&(stato[indice]!=PIENO))

indice++;


stato[indice]=IN_USO; // la cella è in uso
Signal_Sem(sem, MUTEXC); // Sblocca altri cons

// consumo del messaggio
msg valore_consumato = buffer[indice];

stato[indice]=VUOTO; // la cella è vuota
Signal_Sem(sem, SPAZIO_DISP); // segnala i prod


}

Prod-Cons con un pool di buffer

Con questa soluzione, i produttori (o i consumatori) accedono alla sezione critica gestita da MUTEXP (o MUTEXC) solo per acquisire una cella libera tramite il vettore di stato.

Una volta acquisita la cella, possono procedere concorrentemente nella produzione (o consumo).

I produttori “veloci” potranno terminare prima e segnalare prima i consumatori (e viceversa).

Problema dei Lettori/Scrittori

Due categorie di processi:

• lettori, che leggono un messaggio su di una risorsa condivisa;
• scrittori, che scrivono il messaggio dalla risorsa condivisa.

Vincoli:

1. i processi lettori possono accedere contemporaneamente alla risorsa;
2. i processi scrittori hanno accesso esclusivo alla risorsa;
3. lettori e scrittori si escludono mutuamente dall’uso della risorsa.

Lettori/Scrittori con starvation degli scrittori

Le operazioni di lettura sono “protette” dalle procedure di Inizio_Lettura() e Fine_Lettura(),

Le operazioni di scrittura sono “protette” da Inizio_Scrittura() e Fine_Scrittura().

Un processo lettore attende solo se la risorsa è occupata da un processo scrittore e un processo scrittore può accedere alla risorsa solo se questa è libera.

Questa particolare strategia di sincronizzazione può tuttavia provocare condizioni di attesa indefinita (STARVATION) per i processi scrittori.

Lettori/Scrittori con starvation degli scrittori

Una variable condivisa NUM_LETTORI viene usata per contare il numero di lettori che contemporaneamente accedono alla risorsa.

Solo quando NUM_LETTORI = 0, gli scrittori possono accedere (uno alla volta) alla risorsa.

Si utilizzano 2 semafori:

• MUTEXL per gestire l’accesso alla variabile NUM_LETTORI in mutua esclusione, da parte dei lettori (inizializzato a 1);
• SYNCH per garantire la mutua esclusione tra i processi lettori e scrittori e tra i soli processi scrittori (inizializzato a 1).

Lettori/Scrittori con starvation degli scrittori

void Inizio_Lettura(int sem) {


Wait_Sem(sem, MUTEXL);
Num_Lettori++;
if (Num_Lettori==1) Wait_Sem (sem, SYNCH);
Signal_Sem(sem, MUTEXL);


}

void Fine_Lettura(int sem) {


Wait_Sem(sem, MUTEXL);
Num_Lettori--;
if (Num_Lettori==0) Signal_Sem (sem, SYNCH);
Signal_Sem(sem, MUTEXL);


}

Lettori/Scrittori con starvation degli scrittori

void Inizio_Scrittura(int sem) {


Wait_Sem(sem, SYNCH);


}

void Fine_Scrittura(int sem) {


Signal_Sem(sem, SYNCH);


}

Starvation degli scrittori: mentre uno scrittore è sospeso sul semaforo SYNCH, altri lettori possono accedere alla risorsa, ritardando indefinitamente lo scrittore.

Lettori/Scrittori con starvation di entrambi

Anche per gli scrittori si può ottenere un comportamento analogo, introducendo una variabile NUM_SCRITTORI.

In questo caso occorrono 4 semafori, tutti inizializzati a 1:

• MUTEXL per gestire l’accesso alla variabile NUM_LETTORI in mutua esclusione, da parte dei lettori;
• MUTEXS per gestire l’accesso alla variabile NUM_SCRITTORI in mutua esclusione, da parte degli scrittori;
• MUTEX per gestire l’accesso in mutua esclusione alla risorsa condivisa da parte degli scrittori;
• SYNCH per garantire la mutua esclusione tra i processi lettori e scrittori.

Lettori/Scrittori con starvation di entrambi


void Inizio_Scrittura(int sem) {


Wait_Sem(sem, MUTEXS);
Num_Scrittori++;
if (Num_Scrittori==1) Wait_Sem(sem, SYNCH);
Signal_Sem(sem, MUTEXS);
Wait_Sem(sem, MUTEX)


}

void Fine_Scrittura(int sem) {


Signal_Sem(sem, MUTEX)
Wait_Sem(sem, MUTEXS);
Num_Scrittori--;
if (Num_Scrittori==0) Signal_Sem (sem, SYNCH);
Signal_Sem(sem, MUTEXS);


}